Big O Notation (Büyük O Notasyonu)

Algoritma analizi algoritmanın karakteristiklerini dikkate alarak girdi sayısına bağlı olarak zaman ve bellek kaynaklarının değerlendirilmesi ile ilgilidir. Algoritmaların kıyaslanması için işletim süreleri karşılaştırılabilir fakat farklı kodlama dilleri ve makine gereksinimleri söz konusu olduğundan bu yöntem tercih edilmemektedir.

İkinci çözüm algoritmada kullanılan genel yapıların karşılaştırılması şeklindedir. İşletim zamanı karmaşıklığı 2 şekilde ele alınır. Girdi boyutunun fonksiyonu olarak zaman ele alınır. En yaygın karmaşıklık ölçütü en kötü durum işletim süresi değerlendirilmesidir. Ayrıca algoritmanın değerlendirilmesinde ortalama durum değerlendirmesi ele alınır.

Algoritmik karmaşıklık üstten yakınsamayı ifade eden O notasyonu şeklinde gösteriliri. Örneğin aşağıdaki iki durum polinomial durum karmaşıklığını ifade eder.

1. O(n^3+2n^2-17n+5) -> O(n^3) = 2.sine göre bunun karmaşıklığı daha iyi
2. O(n^4-200n^2+8n-2) ->O(n^4)

Algoritmik karmaşıklığın değerlendirilmesinde aşağıdaki kurallar uygulanmaktadır.

1. Tek satırlık dizi boyutu ile ilişkili olmayan işlemlerin karmaşıklığı sabit zaman karmaşıklığıdır ve O(1) olarak gösterilir.
2. Döngüler genelde dizi boyutu ile ilişkili olduğundan zaman karmaşıklığı O(n) ile gösterilir.
3. İç içe döngülerin karmaşıklığı karmaşıklıkların çarpımı şeklinde hesaplanır. O(nXm)
4. Ardarda gelen döngülerin karmaşıklığı karmaşıklık toplamları şeklinde ifade edilir. O(n) + O(m)
5. If-then-else yapılı karmaşıklık koşullarından daha büyük olanın karmaşıklığı ile ifade edilir. max{ O(n), O(m) }

6. Eğer işlem sırasında dizi yarıya bölünerek işleme tabi tutulursa O(logaN) ile ifade edilir.

7. Karmaşıklık ölçütünde yüksek derece dikkat edilmektedir.
   O(n^2+m) = O(n^2)

Bazı önemli algoritmik karmaşıklıklar aşağıdaki şekilde verilir.

1. O1) sabit zamanlı karmaşıklığı: Örneğin dizinin i. elemanına değer atanması
2. O(n) doğrusal zaman karmaşıklığı: dizinin tüm elemanlarının ekrana yazılması
3. O(log2n) logaritmik zaman karmaşıklığı: sıralı dizi üzerinde ikili arama
4. O(n^2) basit sıralama algoritmaları
5. O(n^3) : Örneğin 3 boyutlu dizi elemanlarının değerlerinin arttırılması(1'er)
6. O(nlogn) hızlı sıralama algoritmaları: ağacın hem sağ hem sol tarafında işlem yapmaktadır(log serach). quick sor ve merge sort algoritmaları
7. O(2^n) alt kümelerin bulunması