big-o notation

• yazılım mühendisliği'nin temel taşıdır, sfenks taşıdır.
  
  zaten önemliydi ama son yıllarda iyice kritik oldu. bulut bilişim üzerinde her cpu cycle'a para veriyoruz, yani en az sistem kaynağı kullanarak (ram, cpu vs.) en verimli sonucu almalıyız. ayrıca iot nedeniyle yaygınlaşan çok küçük donanımlar da (raspberry pi, arduino falan) fazla yüklenmeyi kaldırmıyorlar. kısıtlı kaynaklar ile resmen 80'lere geri dönmüş gibi olduk ama bir yandan da iyi oldu.
  
  bu durumda "big o notation" iyice önem kazandı. yazdığımız kodun karmaşıklığını ve sisteme olan maliyetini ifade ediyor. üzerine pratik yapmak bilinç sahibi olmak için önemli.
  
  özet geç piç diyenler için:
  
  çıktı üretmek için gereken sürenin ya da belleğin girdiye bağlı olarak hangi oranda değiştiğini ifade eder.
  
  yani yazdığımız kodu önce matematik olarak ifade etmemiz gerekiyor. sonrasında big o notation yardımıyla genel karmaşıklığı hesaplayabiliyoruz. karmaşıklık çok çıkınca eğer işini iyi yapıyorsa yazılım müdürü bize "siktir git o kodu düzelt gel" diyor, gidip karmaşıklığı azaltıp tekrar code review'a sokuyoruz.
  
  mesela aşağıdaki döngü n sayısı kadar döneceği için karmaşıklığı o(n)'dir.
  for (i = 0; i<n; i++) console.writeln("zıttırıbıttın mı?");
  
  sık rastlanılan o(n) notasyonlarını küçükten büyüğe sıralayacak olursak:
  
  *** o(1): değişmeyen çıktı maliyeti.
  sistemin girdisi ne olursa olsun çıktı üretme hızı sabittir. sisteme eklediği karmaşıklık yok denecek kadar azdır. determinizmin dibidir.
  örnek: console.writeln(x[i]); // i değeri ne olursa olsun okuma hızı aynı.
  
  ***o(log(n)): girdi boyutundan daha küçük çıktı üretme maliyeti:
  sistemin girdisine göre çıktı üretme maliyeti (süre, kaynak kullanımı vb.) artmakla beraber, bu artış girdinin boyutuna göre her zaman daha azdır.
  bu da sisteme en az yükü getiren karmaşıklıktır. çünkü log(n) fonksiyonu her zaman girdisi olan n'den daha küçük bir sayı döndürür. örneğin log(10) = 1'dir. sistemin girdinin karmaşıklığından her zaman daha az yükle çalışacağını ifade eder. sen ne biçim bir kralsındır.
  f(n) = log(n); // yine çok az maliyetli bir kod.
  
  *** o(n): girdi boyutu oranında birebir değişen çıktı maliyeti
  sisteme getirdiği yük daha fazladır. girdi büyüdükçe sisteme yüklenen yük de artacaktır.
  örneğin for döngüleri buna iyi bir örnektir. döngü n sayısı kadar döndükçe harcayacağı zaman ve kaynak büyüyecektir.
  
  *** o(n * log(n)): girdi boyutu büyüdükçe, girdi boyutuna göre farkı açarak büyüyen çıktı maliyeti
  girdi büyüdükçe, çıktının hesaplanması sürekli daha çok zaman alıyor ancak tam bir üssel büyüme olmuyorsa ifade edilir. basit bir ifadeyle:
  n = 10 iken log(10) = 1
  n = 20 iken log(20) = 1.3
  yani,
  n = 10, 10 * log(10) = 10
  n = 20, 20 * log(20) = 26
  
  n büyüdükçe karmaşıklık farkı arttırarak büyüyor. bu orta düzey bir karmaşıklıktır ve mümkünse optimize edilmelidir.
  
  n kadar dönen bir for döngüsü düşünelim. 1'den n'e kadar dönsün. ancak her adımda kullandığı memory miktarı arttığı için döngünün bir adımını tamamlaması sürekli yavaşlasın ancak yavaşlama üssel büyüyerek gidiyor olmasın. bu o(n * log(n)) bir döngüdür.
  
  *** o(n^2): girdi boyutu büyüdükçe çıktı maliyetinin karesel olarak katlanması
  iğrenç karmaşıklığın ilklerindendir. girdi büyüdükçe çıktı üretmek onun karesi kadar çok sistem kaynağı kullanır. mesela verilen n sayısı kadar alana piksel piksel kare çizen bir uygulama o(n^2)'dir. girdi 2 iken 4 pixel, girdi 8 iken 64 piksel çizmek durumundadır. böyle bir döngüye girmek yerine mesela ekran kartının doğrudan kare çizen bir komutu varsa onu kullanmak kodunuzun karmaşıklığını düşürecek, daha doğrusu karmaşıklığı başka bir kaynağa devredecektir. şimdi o düşünsündür.
  
  *** o(2^n): girdi boyutunda en ufak artışta çıktı maliyetinin bir öncekine göre iki kat büyümesi
  girdi miktarının karesinden de büyük bir büyümedir. girdi çok az büyüse bile çıktıyı oluşturmanın maliyeti abartı büyür. böyle karmaşıklığa sahip algoritmalar ancak traveling salesman gibi zorlu durumların optimize edilmiş halleriyle ortaya çıkar. eğer o kadar büyük bir işin peşinde değilseniz ancak ne yapıp edip o(2^n) kod yazmayı başardıysanız dış dünyaya rezil kepaze olmadan önce oturup kodunuzu optimize etmenizde hayır vardır. örneğin ilişkisel veritabanı sorgusu yaparken anlamsız join'ler o(2^n)'e kolayca yelken açar. özellikle orm'leri sorumsuzca kullanan programcılarda görülür. böyle programcılara karşı sakin sakin konuşurken aniden tokat patlatmak, kızarmış yanağıyla size bakarken kalınan yerden sakin sakin konuşmaya devam etmek hakedilen bir durumdur.
  
  ** *o(n!): girdi boyutunda en ufak artışta çıktı maliyetinin önceki maliyetlerin çok üzerinde büyümesi
  var olan en iğrenç büyüme şekillerinden biridir. her bir girdi için çıktı miktarı aradaki farkı fersahlar fersahlar açarak büyütmüştür. traveling salesman'ın optimize edilmemiş hali o(n!) karmaşıklığı içerir. düşman başınadır.
  
  bu uzun entry'i popüler bir kaç algoritmayı inceleyerek bitirelim:
  
  - bir array üzerinden n'inci elementi doğrudan erişerek almak.
  döngü falan yok. array'in 3'ü elementini istiyorsun sistem onu şak diye alıp getiriyor. karmaşıklık o(1).
  - bir array üzerinde arama yapmak. isimler'den oluşan bir array üzerinde hulusi ve mahmut'u her ismi tek tek gezerek arıyorsun. karmaşıklık o(n). döngüdeki isim sayısı büyüdükçe arama süresi de "o kadar" büyüyor.
  - bubble sort, genel olarak o(n^2)'dir. eleman sayısı büyüdükçe sort etmek için gereken süre üssel olarak artmıştır.
• algoritma sorularina yeni baslayanlarda bazi algoritma sorularina
  -
  ayni input, ayni runtime
  bir tat alamiyorum
  allah'im bu nasil complexity
  hesaplayamiyorum
  -
  dizelerini yazdiran notasyon.
• bilgisayar biliminde karmasiklik analizinde kullanilan bir gosterimdir. bu gosterimde sabit katsayilar yok sayilir.
  tam olarak soylenmesi gerekirse bir algoritmanin asimtotik calisma suresinin ust limitidir. bu nedenle bir algoritma o(n2) ise ayni zamanda o(n3)'dur ama her o(n2) olan algoritma o(n) degildir. bundan daha kotu degildir anlamina gelir.
• bir algoritmanın girilen n büyüklügündeki input icin calisma süresini belirtmede kullanılan gösterim bicimi.
  mesela quicksort ortalama o(n)=n log n zamanda calisir...
• hangi arama, hangi siralama algoritmasini kullanmaliyim, benim icin önemli olan kriter zamansa ya da yerse hangisini secmeliyim gibi sorulara efektif yanitlar bulabilmek icin göz önünde bulundurulan, islem karmasikligi gösterimi. surada da bir cheat sheetmevcut: big o notation
• şurda da https://rob-bell.net/…ners-guide-to-big-o-notation/ güzel bişiler var.
• algoritmanin calisma karmasikliginin ust limitini belirler, bu yuzdende aslinda cok iyi bir gosterim sekli degildir. hesaplamasi kolay diye kullanilir.
  matematiksel gosterimi su sekildedir :
  f(n)<= ct(n) => f(n) c o(t(n)) denir.
  
  omega notation diye bir gosterim tarzi daha vardir, bu gosterim tarzi ise algoritmanin karmasikliginin alt limitini belirler.
  matematiksel gosterimi su sekildedir:
  f(n) >= ct(n) => f(n) c omega(t(n)) denir. kusura bakmayin elemanidir isareti ile omega isaretini cikartamadim.
  tabii buda tek basina algoritmanin karmasikligini cok net vermez.
  
  o zaman napalim demisler, bir algoritmanin hem alt limitini hem ust limitini verirsek iste o zaman tam olur demisler ve teta notation cikmis.
  buda
  d.f(n)<=t(n)<=c.f(n) olursa olur
  yani bir nevi omega ile big-oh un kesisim noktasi
• o(n3 + 5n2 + n +56) ile o(n3) e$ittir bu notation'da.
• (bkz: little oh notation)
• bu konuyla ilgili ilk çalı$maları yapanlardan esinlenilerek, bachmann-landau notasyonu olarak da bilinir.