Big O Notasyonu
Big O Notasyonu, bir algoritmanın verimliliğini belirlemeye yönelik bir ölçümdür , bir algoritmanın çalışma süresinin üst sınırını temsil eder. Yani algoritmanın en kötü durum karmaşıklığını verir. Big-O Notasyonu, kodunuzun farklı girdi kümelerinde çalışmasının ne kadar sürdüğünü tahmin eder. (NOT: Big- O, algoritmamızın hızını saniyeler cinsinden ifade etmez. İşlem sayısını ve bir algoritmanın ne kadar hızlı büyüdüğünü anlatır. )
Big O notasyonunu, giriş boyutunuz arttıkça kodunuzun ne kadar etkili olduğunu ölçme aracı olarak görebilirsiniz.
Elimizde 100 elemanlı sayıların olduğu bir listemiz olsun. Bu sayılar arasından 37 sayısının yerini bulmaya çalışalım. Bunun için binary search ve simple search yöntemlerinden hangisini seçmeliyiz ?
(Bu arada bu iki yöntemi bilmiyorsanız endişelenmeyin şuanda ana konumuz bunların çalışma mantığı değildir. )
Seçilen algoritmanın hem hızlı hem de doğru olması gerekir. Simple search algoritması, her öğeyi tek tek kontrol ettiği için binary search algoritması daha hızlıdır. Lakin simple search algoritmasının yazılması daha kolaydır ve hata olasılığı daha düşüktür.
Hadi iki algoritmayı da deneyerek 100 elemanlı listedeki hızımızı inceleyelim:
Bir sayıyı kontrol etme süresinin , 1 milisaniye sürdüğünü varsayalım.
Simple search algoritması ile en kötü 100 sayıyı gezmek gerekir ki bu da toplam 100 ms vakit almaktadır.
Binary search algoritması ile bu durum “log2(100)” ms süre eder.
log(100) / log(2) = 6.64385618… ms
Yani yaklaşık olarak 7ms sürer.
( Yukarıdaki işlemi anlamadıysanız hiç kafanıza takmayın ,odaklanmamız gereken konu şuanda bu değil :D Ama merak ettiyseniz binary search algoritmalarının nasıl çalıştığına bir göz atmanızı öneririm. )
Bu ms lik fark size çok da mühim gelmemiş olabilir.
Şimdi, listemiz 100 elemanlı değil de 10.000 elemanlı hatta 1.000.000.000 elemanlı olduğunu varsayarak yürütme zamanlarını hesaplayalım. 🤔
Hesaplanmış halini aşağıdaki grafikte görüntüleyebilirsiniz :
Simple search algoritmamızın çalışması tam 11 günümüzü alacaktı ! Buna karşılık binary search algoritmamız 32 ms de aranılan sayıyı bulacaktı. 😎
Big O Notasyonu , girdiye dayalı olarak algoritmaların performansını veya algoritmaların karmaşıklığını ifade etmenize izin veren asimptotik bir notasyondur.
Big O sayesinde, programcı bir algoritmanın ,
1-en kötü durumunu ,
2-yürütme süresini ,
3-bellek gereksinimlerini daha iyi anlar.
16 KUTULUK IZGARA ÇİZİMİ
Hadi şimdi çok sevdiğim “Grokking Algorithms: An illustrated guide for programmers and other curious people” kitabından bir örnekle konuyu daha çok pekiştirelim. Bu arada bu kitabın linkini kaynakça kısmına bırakacağım. İncelemenizi tavsiye ederim. Efsane güzel bir kitap ❤
Bir kağıda 16 kutuluk ızgara (grid) çizmemiz gerektiğini varsayalım.Aşağıda 2 çeşit çizme yönteminden bahsedeceğim. Sizce hangi algoritmayı seçmek daha mantıklı ?
Algoritma 1:
Birinci yol , her kutuyu teker teker çizmektir. Hadi tekrar hatırlayalım : Big o notasyonu, yapılan işlem sayısını tutmaktadır.
Bu algoritmamızda 1 işlem basamağında, 1 kutu çiziyoruz. 16 kutuluk işlem için 16 adet işlem yapıyoruz.
Sizce bu algoritmanın yürütme zamanı nedir(running time)? (2. Örneğe de değinip cevabı yazacağım .😊 )
Algoritma-2:
Şimdi kağıdı katlayarak bu problemi çözmeye çalışalım. Bir katlama işlemi sırasında 2 adet kutu oluşmaktadır.
Kağıdı tekrar tekrar katlayalım.
4 katlama yaptıktan sonra kağıdı açalım, işte muhteşem bir 16 kutuluk gridimiz hazır!
Bu örnekte 16 kutuluk grid için toplamda 4 katlama işlemi gerçekleştirdik.
Algoritma 1 ‘ in yürütme zamanı : O(n)’dir. (1 kutuyu 1 işlem ile, 16 kutuyu 16 işlem ile çizdik.)
Algoritma 2‘ in yürütme zamanı : O(logn)’dir. (16 kutuyu 4 işlemle oluşturduk : log2 (16) = 4)
Algoritmanın Big-O notasyonunlarını bulma ve karşılaştırma
Big O gösterimini yazarken, girdideki en hızlı büyüyen terime baskın terim denir. Örneğin denklemimiz, g(n) = n² + 5n + 6 olsun. Burada n², n’den daha hızlı büyür o yüzden O(n²) olacaktır.
Big O gösteriminde baskın olmayan terimleri ve sabitleri görmezden gelin. Çünkü input değeri , sonsuza giderken büyümeyi yönetecek olan terim dominant terimdir. Hadi gelin birkaç örnek çözelim.
Örneklere başlamadan önce şu meşhur sıralamayı hatırlamakta fayda olduğunu düşünüyorum :
Örnekler:
- g(n) =9n -> O(n) olarak
- g(n) = 7n² + 6n + 1001 -> O(n²) olarak basitleştirilir.
g(𝑛) = 7𝑛 + 56 -> O(n)
g(𝑛) = 47𝑛 -> O(n)
g(n,m) = 5.n.m+ 3.n + 56-> 3.𝑛.𝑛 + 4𝑛 -> O(𝑛²)
𝑓(𝑛) = 5 𝑛⁰ + 𝑛³ 𝑙𝑜𝑔 (𝑛) + 𝑛𝑙𝑜𝑔 (𝑛) + 0.9 𝑛³ –> O(𝑛³)
Bu yazımda sizlere Big-O Notasyonu temelini anlatmaya çalıştım. Olabildiğince örnekleri detaylı açıkladım çünkü bir sonraki yazımda algoritmalar üzerinden Big-O notasyonu hesaplamaları yapacağız. Umarım yazım sizler için faydalı olmuştur.
Konuyla ilgili sormak istediğiniz soru olursa bana her zaman mesaj atabilirsiniz. 🎈
KAYNAKÇA
