Big-O, Θ, Ω ve maliyet modeli

Big-O, büyüme hızının asimptotik üst sınırıdır; otomatik olarak “en kötü durum” anlamına gelmez. Önce hangi fonksiyonu sınırladığını söyle: en kötü, ortalama, en iyi veya amortize maliyet. f(n)=3n²+7n+4 için yeterince büyük n'de sabit bir c ile f(n)≤cn² kurabiliriz. Θ(n²), hem üst hem alt sınırın aynı büyüklükte olduğunu belirtir; Ω yalnız alt sınırdır.

Döngülerin iç içe olması tek başına n² kanıtı değildir. İç döngü her turda sabit sayıda çalışıyorsa toplam doğrusal olabilir; iki işaretçi bütün çalışma boyunca yalnız ileri gidiyorsa toplam hareket 2n ile sınırlanabilir. Ardışık işlerde maliyetler toplanır, bağımsız iç içe tekrarlarda çarpılır. log₂ n, arama alanını ikiye bölme sayısını ölçer; asimptotik sınıfta log tabanları sabit çarpanla ayrılır.

Alan maliyetinde girdiyi, çıktıyı ve ek çalışma alanını ayır. Bir algoritma yeni n elemanlı çıktı döndürürken ek alanı O(1) olabilir ancak toplam çıktıyla alanı O(n)'dir. Python büyük tam sayılarında toplama bit uzunluğuna bağlıdır; RAM modeli varsayımını her matematiksel sonuca körlemesine taşıma.

Matematiksel kanıtı gerçekten kurmak

f(n)=3n²+7n+4 için n≥1 olduğunda 7n≤7n² ve 4≤4n² olur. Dolayısıyla f(n)≤14n²: c=14, n₀=1 seçimi O(n²) tanımını sağlar. Aynı zamanda f(n)≥3n²; böylece Θ(n²). O(n³) da doğru bir üst sınırdır ama sıkı değildir. “O(n²), dolayısıyla kesin n² adım” cümlesi yanlıştır.

Bir iç döngü i kez çalışıyorsa toplam 0+1+…+(n−1)=n(n−1)/2'dir. İç döngü her turda ikiye bölünüyorsa yalnız döngü yazımına bakmak yetmez. Örneğin dış döngü n kez, iç döngü log n kez ise Θ(n log n). İki işaretçinin her biri yalnız n kez ileri gittiği sliding-window algoritmasında nested while görünse bile toplam Θ(n) olabilir.

Büyüme	n iki kat olursa yaklaşık iş	Tipik gerekçe
log n	Bir sabit adım daha	Aralık yarıya iner
n	2 kat	Bir tarama
n log n	2 kattan biraz fazla	Logaritmik seviye, doğrusal iş
n²	4 kat	Tüm çiftler
2ⁿ	Kareye yakın değil, 2ⁿ kat artış	Bütün alt kümeler

Bu oranlar asimptotik baskın terim içindir. Gerçek süre allocation, cache, JIT, scheduler ve I/O içerir. Benchmark'ta aynı input dağılımı, warm-up, tekrar sayısı ve environment kaydedilir. 100 elemanda daha hızlı olan algoritma 10 milyon elemanda daha hızlı olmak zorunda değildir.

Üç aşamalı çalışma

Temel: Üç ardışık n döngüsü ile üç iç içe n döngüsünün farkını çıkar. Birincisi Θ(n), ikincisi Θ(n³).

Orta: j her dış turdan sonra sıfırlanmayan ve yalnız artan iki pointer algoritmasında toplam artış sayısını sınırla.

İleri: Büyük tamsayıların çarpımını O(1) sayan RAM analizini bit modeline taşı. Girdi elemanı sayısı ile her elemanın bit uzunluğunu ayrı değişken yap. Model değişince algoritmanın mantığı değişmeden maliyet ifadesi değişebilir.

def triangular_work(n):
    count = 0
    for i in range(n):
        for j in range(i + 1):
            count += 1
    return count
assert triangular_work(4) == 10