Bölüm 1.2: Algoritma Karmaşıklığı

1.2.1Karmaşıklık kavramı

Bir algoritmanın doğru çalışması ilk koşuldur, ama tek koşul değildir. Doğru bir algoritma bin öğelik girdide bir saniyede biterken milyon öğelik girdide günlerce sürebilir. Algoritma seçerken bu yüzden “ne kadar kaynak harcar?” sorusu da sorulur. Bu kesim, sorunun nasıl ölçüleceğini anlatır. Ölçülen şey saniye değil, temel işlem sayısıdır; ilgilenilen şey de bu sayının girdiyle birlikte nasıl büyüdüğüdür.

1.2.1.1Algoritma karmaşıklığı nedir?

Karmaşıklık kuramı (complexity theory), bir algoritmanın çalışırken harcadığı kaynakları inceler. İki kaynak öne çıkar: zaman ve bellek. Her ikisi de girdinin büyüklüğüne bağlıdır. Beş sayıyı sıralamak, beş milyon sayıyı sıralamaktan çok daha kısa sürer. Bu yüzden kaynak kullanımı tek bir sayı olarak değil, girdi boyutunun bir fonksiyonu olarak yazılır.

Girdi boyutu genellikle n ile gösterilir. Dizi işleyen bir algoritmada n dizinin öğe sayısıdır. Dizgi işleyen bir algoritmada karakter sayısı, çizge işleyen bir algoritmada düğüm ve kenar sayısıdır. Zaman ihtiyacı T(n), bellek ihtiyacı S(n) ile gösterilir. Örneğin T(n) = 3n + 3, algoritmanın n boyutlu bir girdide 3n + 3 temel işlem yaptığını söyler.

Analizin amacı saniye ölçmek değildir. Amaç, girdi büyüdükçe kaynak ihtiyacının nasıl büyüdüğünü görmektir. Temel soru şudur: girdi boyutu iki katına çıkarsa çalışma süresi ne olur? Aynı mı kalır, iki katına mı çıkar, dört katına mı, yoksa karesi mi alınır? Şekil 1.2.1 bu sorunun birkaç büyüme sınıfı için cevabını gösterir.

Şekildeki çarpanlar basit bir hesaptan gelir. T(n) = n² ise T(2n) = 4n² = 4 · T(n)'dir. T(n) = n³ ise T(2n) = 8n³'tür. Logaritmada ise log₂(2n) = log₂ n + 1 olduğundan süre yalnız bir adım uzar. Bu tek soru bile algoritmalar arasındaki farkı açıkça ortaya koyar. Girdi bin kat büyüdüğünde kübik bir algoritma bir milyar kat yavaşlar; logaritmik bir algoritma ise yalnız on adım kadar fazla çalışır.

1.2.1.2Süre ölçümü neden yetmez?

Bir algoritmanın hızını öğrenmenin ilk akla gelen yolu, onu çalıştırıp süresini ölçmektir. Java'da bunun için çalıştırmadan önce ve sonra sistem saati okunur, aradaki fark yazdırılır:

long baslangic = System.currentTimeMillis();
dogrusalArama(dizi, 10001);  // 10^8 eleman
long bitis = System.currentTimeMillis();
System.out.println("Geçen süre: "
    + (bitis - baslangic) + " ms");

Kod, 10⁸ öğeli bir dizide doğrusal aramanın kaç milisaniye sürdüğünü ölçer. System.currentTimeMillis() o anki zamanı milisaniye olarak döndürür. İki okuma arasındaki fark, aramanın harcadığı süredir. Bu yönteme deneysel ölçüm denir. Gerçek bir sayı verir; ama bu sayının üç ciddi zayıflığı vardır.

• Sonuç makineye bağlıdır. Aynı kod hızlı bir işlemcide 40 ms, eski bir dizüstü bilgisayarda 200 ms sürebilir. Java'da durum daha da karışıktır. JIT derleyicisi (just-in-time compiler), sık çalışan kodu program çalışırken makine koduna çevirir; bu yüzden aynı ölçüm ilk denemede yavaş, sonrakilerde hızlı çıkar. Önbellek (cache), işletim sisteminin o anki yükü ve çöp toplayıcının ne zaman devreye girdiği de sonucu değiştirir.
• Tek ölçüm geleceği söylemez. 10⁸ öğede 40 ms süren bir arama, 10⁹ öğede ne kadar sürer? Ölçüm bunu söylemez. Algoritma doğrusal büyüyorsa süre on katına çıkar ve 400 ms olur; karesel büyüyorsa yüz katına çıkar ve 4 saniyeyi bulur. Cevap algoritmanın büyüme biçimine bağlıdır ve tek bir ölçüm bu biçimi göstermez.
• Kodun yazılmış olması gerekir. İki tasarımı karşılaştırmak için ikisinin de kodlanması, test edilmesi ve aynı koşullarda ölçülmesi gerekir. Tasarım aşamasında, henüz kod yokken, ölçüm yapılamaz.

Şekil 1.2.2 ikinci zayıflığı somutlaştırır. B makinesi A'dan 2,5 kat yavaştır; ama iki çizgi de doğrudur ve aynı biçimde büyür. Kesikli eğri ise farklı bir algoritmaya aittir ve karesel büyür. Küçük girdilerde bu algoritma iki makinedeki doğrusal algoritmadan da hızlı görünür. n²/4 = 5n eşitliği n = 20'de sağlanır; bu noktadan sonra karesel algoritma yavaş makinedeki doğrusal algoritmayı bile geçer ve fark giderek açılır. Küçük girdilerle yapılan bir ölçüm, burada yanlış algoritmayı seçtirirdi.

Bu zayıflıkların çaresi asimptotik analizdir. Asimptotik analiz, adım sayısını n'nin bir fonksiyonu olarak verir ve yalnız n büyürken ne olduğuna bakar. Makineden bağımsızdır; kod yazmadan, yalnız algoritmanın tarifinden yapılabilir. Deneysel ölçüm değersiz değildir: iki algoritma aynı büyüme sınıfındaysa hangisinin gerçekte daha hızlı olduğunu ancak ölçüm söyler. İki yöntem birbirini tamamlar. Önce analizle doğru büyüme sınıfı seçilir, sonra ölçümle sabit çarpanlar karşılaştırılır.

1.2.1.3Adım sayma ve RAM modeli

Makineden bağımsız bir sayım yapmak için hayalî, basit bir makine düşünülür. Bu makinede her temel işlem tam bir birim zaman alır. Bellekteki her hücreye, adresi ne olursa olsun, aynı sürede erişilir. İşlemler birer birer, sırayla yürür. Bu soyut makineye RAM modeli (random-access machine, rastgele erişimli makine) denir. Gerçek bilgisayarlar böyle çalışmaz: önbellekte bulunan veri, ana bellektekinden kat kat hızlı okunur. Ama model, büyüme sınıfını bulmak için yeterince doğrudur ve hesabı çok kolaylaştırır.

Modeli doğrusal arama üzerinde uygulayalım. Doğrusal arama, dizinin öğelerine baştan sona tek tek bakar. Aranan değer (hedef) bulununca indisini döndürür; dizi biterse −1 döndürür:

for (int i = 0; i < a.length; i++) {
  if (a[i] == hedef)
    return i;
}
return -1;

Sayım için her işlemin kaç kez çalıştığı bulunur. En kötü durumu ele alalım: hedef dizide yoktur, dolayısıyla döngü sonuna kadar döner. Dizinin uzunluğu n olsun.

• i = 0 ataması döngü başlarken bir kez yapılır.
• i < a.length koşulu her turun başında denetlenir. i 0'dan n − 1'e kadar her değerde koşul doğrudur; bu n denetim eder. i = n olduğunda koşul bir kez daha denetlenir ve yanlış çıkar. Toplam n + 1 denetim yapılır.
• a[i] == hedef karşılaştırması her turda bir kez yapılır: n kez.
• i++ her turun sonunda bir kez yapılır: n kez.
• return -1 en sonda bir kez çalışır.

Toplam T(n) = 1 + (n + 1) + n + n + 1 = 3n + 3'tür. Bu sayıda iki tür bilgi vardır. 3 katsayısı ve +3 sabiti, neyin bir adım sayıldığına ve makineye bağlıdır. Dizi erişimi ile karşılaştırma ayrı iki işlem sayılsaydı katsayı 4 olurdu; derleyici koşul denetimini artırmayla birleştirseydi 2 olurdu. Değişmeyen şey, adım sayısının n ile doğru orantılı büyümesidir. Dizi iki katına çıkınca adım sayısı da yaklaşık iki katına çıkar. Asimptotik analiz bu değişmeyen kısmı saklar, ötekini atar: T(n) = Θ(n). Buradaki Θ(n), “n ile aynı hızda büyür” diye okunur; kesin tanımı asimptotik gösterimle birlikte verilir.

1.2.1.4Kod izleme: dogrusalArama

Sayımı küçük bir örnekte adım adım doğrulayalım. Dizi a = [4, 7, 2], hedef 5'tir. 5 dizide olmadığı için en kötü durum oluşur; beklenen adım sayısı 3 · 3 + 3 = 12'dir.

Koşul dört kez denetlenmiştir (n + 1 = 4), karşılaştırma ve artırma üçer kez yapılmıştır. Toplam 12 adım, 3n + 3 formülünün n = 3 için verdiği değerdir. Her öğe için sabit sayıda, üç işlem harcanmıştır: bir koşul denetimi, bir karşılaştırma ve bir artırma. Öğe sayısı arttıkça bu üçlü tekrarlanır; süre bu yüzden doğrusal büyür. Şekil 1.2.3 izlemenin son anını gösterir.

1.2.1.5En iyi, en kötü ve ortalama durum

Doğrusal aramanın adım sayısı yalnız n'ye bağlı değildir. Aynı uzunluktaki iki dizide hedefin yeri farklıysa adım sayısı da farklıdır. Hedef ilk hücredeyse arama hemen biter; hiç yoksa bütün dizi taranır. Bu yüzden “doğrusal arama kaç adım sürer?” sorusunun tek bir cevabı yoktur. Soru, hangi girdiden söz edildiği belirtilerek sorulmalıdır. Bunun için üç ölçü kullanılır.

Üç ölçünün değeri aynı değildir. En kötü durum en çok kullanılanıdır, çünkü bir garanti verir: algoritma hiçbir girdide bundan uzun sürmez. Gerçek zamanlı bir sistemde, bir uçağın kontrol yazılımında ya da bir web sunucusunda bu garanti önemlidir. En iyi durum bir alt sınır verir, ama tek başına pek bilgi taşımaz. Hemen her algoritma bazı şanslı girdilerde hızlıdır. Ortalama durum pratikte en gerçekçi tahmini verebilir; ama hesaplamak için girdilerin hangi olasılıkla geldiğini bilmek gerekir. Bu bilgi çoğu zaman yoktur ve varsayılan dağılım yanlışsa sonuç da yanlıştır.

Ortalama durum hesabındaki (n + 1)/2 sonucu, Gauss'un toplam formülünden gelir: 1 + 2 + … + n = n(n + 1)/2. Aynı formül döngü analizinde de sık geçer. Ortalama ile en kötü durum arasındaki 1/2 çarpanı, asimptotik analizde atılan türden bir sabittir. Bu yüzden doğrusal aramanın ortalama ve en kötü durumu aynı sınıfa düşer. Her algoritmada böyle değildir: hızlı sıralama ortalamada Θ(n log n), en kötü durumda ise Θ(n²) sürer.

1.2.1.6Alan karmaşıklığı

Zaman kadar önemli ikinci kaynak bellektir. Alan karmaşıklığı genellikle ek bellek (auxiliary space) için verilir. Girdinin kendisi sayılmaz, çünkü her algoritma girdiyi bir yerde tutmak zorundadır; asıl merak edilen, algoritmanın bunun üstüne ne kadar bellek istediğidir. Bir diziyi tek bir toplam değişkeniyle toplayan algoritma, dizi ne kadar uzun olursa olsun yalnız birkaç değişken kullanır. Ek belleği Θ(1)'dir.

Özyinelemeli kodda gözden kaçan bir bellek kalemi vardır. Bir metot çağrıldığında, parametreleri, yerel değişkenleri ve dönüş adresi için çağrı yığınında (call stack) bir çerçeve (stack frame) açılır. Metot bitince çerçeve kaldırılır. Özyinelemeli bir fonksiyon kendini çağırdıkça çerçeveler üst üste biner. Aynı anda yığında bulunan en çok çerçeve sayısı, özyinelemenin derinliğidir. Ek bellek en az bu derinlik kadardır.

Tablo 1.2.4 önemli bir gerçeği gösterir: zaman ve bellek farklı hızlarda büyüyebilir. Kendini iki kez n − 1 ile çağıran f3 fonksiyonu üstel sayıda (2ⁿ − 1) çağrı yapar. Buna karşın belleği yalnız doğrusaldır. Sebep, çağrıların aynı anda değil sırayla yürümesidir. f3(n) önce soldaki f3(n − 1)'i çağırır ve bu çağrının bütün alt çağrıları bitip çerçeveleri kalkmadan sağdakine geçmez. Yığında herhangi bir anda yalnız bir zincir bulunur: f3(n), f3(n − 1), …, f3(1). Bu zincirin uzunluğu n'dir.

Aynı düşünce f4 için de geçerlidir. f4'te girdi her çağrıda yarıya indiği için zincir n, n/2, n/4, …, 1 biçimindedir ve uzunluğu yaklaşık log₂ n + 1'dir. Örneğin f4(16) çalışırken yığında en çok 5 çerçeve bulunur (16, 8, 4, 2, 1).

1.2.2Asimptotik gösterim

Adım sayısı 3n + 3 çıktığında katsayıların atılıp yalnız “doğrusal” bilgisinin saklanacağı söylendi. Bu “atma” işleminin kuralları kesin olmalıdır; yoksa iki kişi aynı koda farklı sınıflar verebilir. Asimptotik gösterim (asymptotic notation) bu kuralları koyar. “Asimptotik” sözcüğü, n sonsuza giderken olanla ilgilenildiğini anlatır. Küçük girdilerdeki davranış ve sabit çarpanlar bilerek göz ardı edilir. Üç gösterim kullanılır: üst sınır için O, alt sınır için Ω, sıkı sınır için Θ.

O gösterimi algoritmalardan çok önce, 19. yüzyılın sonunda sayılar kuramında ortaya çıktı. Paul Bachmann 1894'te kullandı, Edmund Landau yaygınlaştırdı. Donald Knuth 1976'da yazdığı kısa bir makalede Ω ve Θ'yı bugünkü anlamlarıyla tanımladı ve üçünün algoritma analizinde birlikte kullanılmasını önerdi. Bugün bütün algoritma kitapları bu tanımları kullanır.

1.2.2.1Büyük O

Büyük O bir üst sınır bildirir. “f(n) = O(g(n))” ifadesi, yeterince büyük her n için f'nin g'nin bir sabit katını aşmadığını söyler. İki ayrıntı önemlidir. Birincisi, sabit kat serbesttir: g'yi 4 ya da 100 ile çarpmak serbesttir. İkincisi, küçük n'ler önemsizdir: eşitsizliğin bir eşik değerinden sonra sağlanması yeter.

Tanımda iki sabit vardır ve ikisinin de görevi ayrıdır. c, sabit çarpanları yutar. 3n² ile n² arasındaki 3 katlık fark, c = 3 seçilerek ortadan kalkar. n₀ ise küçük girdileri dışarıda bırakır. n² + 100 fonksiyonu n = 1'de 2n²'den büyüktür; ama n ≥ 10 olunca küçük kalır. Tanım yalnız n₀'dan sonrasıyla ilgilendiği için baştaki bu farklar sonucu etkilemez.

Bir örnek: f(n) = 3n² + 5n + 2 fonksiyonu O(n²)'dir. Gerçekten c = 4 seçilirse her n ≥ 6 için 3n² + 5n + 2 ≤ 4n² sağlanır. Bu sabitlerin nasıl bulunduğu biraz aşağıda adım adım gösterilir. Şekil 1.2.5 durumu grafikte gösterir.

Büyük O bir üst sınır olduğu için gevşek de olabilir. 3n² + 5n + 2, O(n²) olduğu gibi O(n³) ve O(2ⁿ)'dir de; bu ifadelerin hepsi doğrudur. Ama bilgi değerleri aynı değildir. “Bu algoritma O(2ⁿ) sürer” cümlesi, karesel bir algoritma için doğru ama yanıltıcıdır. Analizde genellikle bulunabilen en küçük üst sınır verilir.

Gösterimdeki eşittir işareti de yanlış anlaşılmaya açıktır. f(n) = O(g(n)) aslında “f, g'nin sabit katıyla üstten sınırlanan fonksiyonlar kümesine aittir” demektir. Bu yüzden ifade tek yönlüdür. n = O(n²) doğrudur; ama buradan “O(n²) = n” sonucu çıkmaz. Bazı kitaplar bu nedenle f(n) ∈ O(g(n)) yazar.

1.2.2.2Büyük Omega ve büyük Teta

Üst sınırın tersi alt sınırdır. Bir algoritmanın “en az şu kadar” süreceğini söylemek için Ω (büyük Omega) kullanılır. İki sınır aynı fonksiyonda buluşursa büyüme hızı kesin olarak bilinir; bunu da Θ (büyük Teta) anlatır.

Tablonun son sütunu kullanışlı bir benzetmedir: O, “küçük ya da eşit”; Ω, “büyük ya da eşit”; Θ, “eşit” gibi davranır. Benzetme şu temel ilişkiyi de hatırlatır: bir sayı hem ≤ g hem ≥ g ise g'ye eşittir. Aynı biçimde

f = Θ(g) ⇔ f = O(g) ve f = Ω(g).

Θ, iki sabit kat arasına sıkıştırmak demektir. Şekil 1.2.6 bunu 3n² + 5n + 2 üzerinde gösterir: fonksiyon, n ≥ 6 için 3n² ile 4n² arasında kalır. Bu yüzden Θ(n²)'dir. Aynı fonksiyon O(n³) olduğu hâlde Θ(n³) değildir. c · n³ biçimindeki her alt eğri, c ne kadar küçük seçilirse seçilsin, bir noktadan sonra fonksiyonu geçer. Çünkü f(n)/n³ oranı n büyüdükçe sıfıra gider.

Büyüme sınıfı ile durum kavramı burada bir kez daha ayrılmalıdır. Doğrusal arama için şu cümlelerin hepsi doğrudur: en kötü durum süresi Θ(n)'dir; en iyi durum süresi Θ(1)'dir; bütün girdiler için süre O(n) ve Ω(1)'dir. Ama “doğrusal arama Θ(n)'dir” cümlesi, hangi durumdan söz edildiği belirtilmezse eksiktir. Eklemeli sıralama da benzerdir: en kötü durumda Θ(n²), sıralı girdide Θ(n) sürer; bütün girdiler için tek bir Θ yazılamaz. Birleştirme sıralaması ise her girdide Θ(n log n) sürer; onun için durum belirtmeden Θ yazmak doğrudur.

1.2.2.3Sabitleri bulmak

Bir sınırı kanıtlamak, tanımdaki sabitleri somut olarak bulmak demektir. Yöntem her seferinde aynıdır: bir c seçilir, eşitsizlik çözülür ve hangi n'den sonra sağlandığı bulunur. Sabitler tek değildir; geçerli herhangi bir çift kanıt için yeter.

Sabitlerin tek olmadığını görmek için başka bir seçim yapılabilir. c₂ = 10 seçilirse n = 1'de bile 3 + 5 + 2 = 10 ≤ 10 olur. Ayrıca her n ≥ 1 için 5n ≤ 5n² ve 2 ≤ 2n² olduğundan 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² yazılabilir. Bu kanıt kökü hesaplamayı gerektirmez: her terim en büyük kuvvetle sınırlanır, katsayılar toplanır. Büyük c, küçük n₀ demektir; küçük c ise daha büyük bir eşik gerektirir.

Aynı yöntem doğrusal bir fonksiyona da uygulanır. 2n + 10 = O(n) olduğunu göstermek için c = 3 seçilirse 2n + 10 ≤ 3n eşitsizliği n ≥ 10 için sağlanır: c = 3, n₀ = 10. Terimleri tek tek sınırlama yöntemiyle 2n + 10 ≤ 2n + 10n = 12n yazılır; bu da c = 12, n₀ = 1 verir.

Bir sınırın yanlış olduğunu göstermek de mümkündür. Bunun için hiçbir sabit çiftinin işe yaramadığı kanıtlanır; genellikle çelişkiyle. n² = O(n) olduğunu varsayalım. O hâlde bir c ve n₀ için her n ≥ n₀'da n² ≤ c · n, yani n ≤ c olmalıdır. Oysa n, n₀'dan ve c'den büyük seçilebilir, örneğin n = max(n₀, ⌈c⌉ + 1). Bu n için n ≤ c bozulur. Varsayım çelişkiye götürdüğü için yanlıştır: n² ≠ O(n).

1.2.2.4Hesap kuralları

Her seferinde sabit aramak zahmetlidir. Tanımlardan çıkan birkaç kural, sınıfı çoğu zaman doğrudan okumayı sağlar.

• Sabit çarpanlar atılır. c · f(n) = Θ(f(n)); örneğin 5n = Θ(n) ve n²/3 = Θ(n²). Sabit çarpan tanımdaki c'ye gömülür.
• Düşük dereceli terimler atılır. Bir polinomda en büyük kuvvetli terim kalır: 4n³ + 100n² + 7 = Θ(n³). n büyüdükçe 100n², 4n³'ün yanında önemsizleşir; n = 1000'de kırkta biri kadardır.
• Toplam kuralı: ardışık kod. Arka arkaya çalışan iki kod parçasının toplam süresi, büyük olanın süresidir: O(f) + O(g) = O(max(f, g)). Önce Θ(n) süren bir döngü, sonra Θ(n²) süren bir döngü çalışırsa toplam Θ(n²)'dir.
• Çarpım kuralı: iç içe kod. n kez dönen bir döngünün içinde O(g) süren bir iş varsa toplam O(n · g)'dir. Kural, iç işin her turda aynı olduğunu varsayar. İç işin süresi dış döngünün sayacına bağlıysa çarpım yerine toplam hesaplanır.
• Logaritmanın tabanı önemsizdir. Taban değiştirme formülüne göre log_a n = log_b n / log_b a'dır. İki taban arasındaki fark yalnız sabit bir çarpandır. Bu yüzden O(log₂ n) = O(log₁₀ n) = O(log n) yazılır ve taban çoğu zaman belirtilmez.
• Üstel ifadelerde taban önemlidir. 3ⁿ = O(2ⁿ) yanlıştır. 3ⁿ/2ⁿ = 1,5ⁿ oranı sonsuza gider; hiçbir sabit çarpan bu farkı kapatamaz. Logaritmanın tersine, üstel tabanlar birbirine sabit çarpanla dönüşmez.

Bu kuralların sonucunda sık geçen fonksiyonlar kesin bir büyüme sırasına dizilir:

1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!

Buradaki “<” işareti, soldakinin sağdakine göre ihmal edilebilir hâle geldiğini anlatır: büyük n'de oran sıfıra gider. Örneğin log n / √n oranı, başta yavaş da olsa, sıfıra yaklaşır.

1.2.2.5Yaygın büyüme sınıfları

Algoritmaların çok büyük bir bölümü birkaç büyüme sınıfından birine düşer. Bir algoritmanın hangi sınıfta olduğu, girdi büyüdükçe nasıl davranacağını hemen söyler. Tablo 1.2.7 bu sınıfları en hızlıdan en yavaşa doğru sıralar. Son sütun, bölümün altı örnek fonksiyonunun hangi sınıfa düştüğünü gösterir.

Tablodaki “iki katına çıkınca” sütunu, sınıfların farkını sezdirmenin en kısa yoludur. Logaritmik algoritmada girdi iki katına çıkınca yalnız bir adım eklenir; ikili arama bu yüzden bir milyar öğede bile otuz kadar karşılaştırmayla biter. Karekökte çarpan √2 ≈ 1,41'dir. Log-doğrusalda çarpan 2'den biraz fazladır: 2n log(2n) = 2n log n + 2n. Üstel sınıfta durum bambaşkadır: 2²ⁿ = (2ⁿ)² olduğu için süre karesine çıkar. Saniyede 10⁹ işlem yapan bir bilgisayarda 1 saniye süren 2ⁿ adımlık bir hesap (n ≈ 30), girdi iki katına çıkınca 36 yıl kadar sürer.

Sınıflar arasında önemli bir çizgi daha vardır. n^k biçimindeki sınıflara polinom zamanlı denir; bunlar genelde “verimli” sayılır. Üstel ve faktöriyel sınıflar ise “verimsiz” sayılır; küçük girdilerin ötesinde pratikte çalıştırılamazlar. Bu ayrım kaba bir kuraldır (n¹⁰⁰ polinomdur ama hiç de verimli değildir), yine de algoritma tasarımında yol gösterir.

Tablonun “Bölümde” sütunundaki f6 için bir not gerekir. f6'nın O(log n) olduğu doğrudur, ama bu sınır sıkı değildir. f6'nın gerçek sınıfı, logaritmadan bile çok daha yavaş büyüyen log* n'dir. Bu ilginç fonksiyon döngü analizi kesiminde ayrıntısıyla incelenir.

1.2.2.6Büyüme eğrileri ve sayılar

Sınıfların sırası grafikte de görülür. Şekil 1.2.7 beş fonksiyonu n = 1 ile 20 arasında çizer. Küçük n'de eğriler birbirine yakındır; hatta n = 4'te n² ile 2ⁿ eşittir (ikisi de 16). n = 5'ten sonra 2ⁿ öne geçer ve hızla uzaklaşır. 2ⁿ eğrisi n ≈ 6,6'da 100'ü aşar; n² ancak n = 10'dan sonra aşar. n log₂ n doğrusala yakın kalır, log₂ n ise neredeyse yataydır.

Grafikteki fark, sayılarla bakıldığında daha da çarpıcıdır. Tablo 1.2.8, saniyede 10⁹ temel işlem yapan bir bilgisayarda her sınıfın ne kadar süreceğini gösterir. Değerler, işlem sayısının 10⁹'a bölünmesiyle hesaplanmıştır.

Tablo iki şey söyler. Birincisi, polinom sınıflar bir milyon öğede bile makul kalır; karesel algoritma 17 dakika, kübik algoritma ise otuz yılı aşar. İkincisi, üstel ve faktöriyel sınıflar çok küçük girdilerde bile çalıştırılamaz hâle gelir. n = 100 için 2ⁿ adım, evrenin yaşının (yaklaşık 1,4 · 10¹⁰ yıl) üç bin katı kadar sürer.

Sunumdaki etkileşimli hesaplayıcı aynı tabloyu istenen n için üretir; “n × 2” düğmesi girdiyi ikiye katlar. Düğmeye basıldığında n sütunu 2, n² sütunu 4, n³ sütunu 8 katına çıkar; log₂ n yalnız 1 artar, 2ⁿ ise karesini alır. Buradan çıkan ders şudur: on kat hızlı bir bilgisayar sabit bir çarpan kazandırır, daha iyi bir algoritma ise büyüme sınıfını değiştirir. n² yerine n log n süren bir algoritma, n = 10⁶'da 17 dakikalık işi 20 milisaniyeye indirir; hiçbir donanım iyileştirmesi bu kadar kazandırmaz.

1.2.3Döngü analizi

Döngüsüz ve özyinelemesiz bir kod parçası sabit sayıda işlem yapar; süresi Θ(1)'dir. Süreyi girdiye bağlayan şey döngüler ve özyinelemedir. Bu kesim döngüleri ele alır. Yöntem tek cümleyle söylenebilir: her döngünün kaç tur döndüğü bulunur, iç içe döngülerde de bu tur sayıları toplanır. Yöntem üç örnek fonksiyon üzerinde uygulanır: tek döngülü f1, iç döngüsünün sınırı dış sayaca bağlı olan f2 ve sayacı alışılmadık hızla büyüyen f6.

Bölümün altı örnek fonksiyonunda ortak bir hile vardır: fonksiyonlar, yaptıkları iş kadar artan bir x sayacını döndürür. Böylece dönüş değeri adım sayısının kendisi olur. Analizle bulunan formül, fonksiyon çalıştırılıp dönüş değerine bakılarak doğrudan denetlenebilir. Bu notta verilen bütün dönüş değerleri ve çağrı sayıları Java ile çalıştırılarak elde edilmiştir.

1.2.3.1f1: tek döngü

public int f1(int n) {
  int x = 0;
  for (int i = 0; i < n; i++) {
    x++;
  }
  return x;
}

Kod üç parçadan oluşur.

• İlk değer verme: int x = 0; satırı x'e 0 atar. Bu tek bir işlemdir, girdiye bağlı değildir: O(1).
• Döngü: for (int i = 0; i < n; i++) başlığında i 0'dan başlar, her turda bir artar ve n − 1'e kadar ilerler. 0, 1, …, n − 1 değerleri n tanedir; döngü n tur döner.
• Gövde: x++; her turda bir kez çalışır ve sabit süreli bir işlemdir: O(1).

Çarpım kuralına göre n kez dönen bir döngü, her turda O(1) iş yapıyorsa toplam iş n · O(1) = O(n)'dir. Döngünün dışındaki ilk değer verme ve return sabit işlerdir; toplam kuralına göre sonucu değiştirmezler:

T(n) = O(1) + n · O(1) = Θ(n)

Gövde tam n kez çalıştığı için alt sınır da n'dir; sonuç bu yüzden Θ ile yazılır. Fonksiyon x = n döndürür: f1(16) = 16, f1(32) = 32. Dönüş değeri adım sayısının kendisidir ve girdi iki katına çıkınca iki katına çıkar. Doğrusal büyümenin işareti budur.

1.2.3.2Kod izleme: f1(4)

f1'in n = 4 için çalışmasını izleyelim. Her satırda koşulun değeri ve x'in yeni değeri yazılır.

Koşul beş kez denetlenmiştir (n + 1), gövde dört kez çalışmıştır (n). Bu sayılar doğrusal aramadaki sayımla aynı biçimdedir. Gövde tam n kez çalıştığı için Θ(n) sonucu izlemede de görülür. Şekil 1.2.8 izlemenin son durumunu gösterir.

1.2.3.3f2: iç içe döngü

public int f2(int n) {
  int x = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i * i; j++) {
      x++;
    }
  }
  return x;
}

f2'de iki döngü iç içedir. Dış döngü f1'deki gibidir: i 0'dan n − 1'e kadar ilerler, n tur döner. İç döngünün sınırı ise sabit değildir. j, 0'dan i · i − 1'e kadar ilerler; yani iç döngü, dış döngünün o anki turunda i² kez döner. i = 0'da iç döngü hiç dönmez, i = 1'de bir kez, i = 2'de dört kez, i = 3'te dokuz kez döner.

İç döngünün tur sayısı i'nin güncel değerine bağlı olduğu için çarpım kuralı doğrudan uygulanamaz. “Dış döngü n tur, iç döngü n tur, toplam n · n” demek yanlıştır, çünkü iç döngü her turda farklı sayıda döner. Doğru yol, her dış tur için iç döngünün tur sayısını yazıp bunları toplamaktır:

T(n) = 0² + 1² + 2² + … + (n − 1)² = Σ_i=0ⁿ⁻¹ i²

1.2.3.4Kod izleme: f2(4) ve f2(5)

f2(4) çağrısında dış döngü dört tur döner (i = 0, 1, 2, 3). Tablo 1.2.10 her dış turdan sonra x'in değerini gösterir. Değerler Java ile çalıştırılarak doğrulanmıştır.

i = 0 turu ilginçtir: iç döngünün koşulu j < 0 · 0, yani 0 < 0'dır ve ilk denetimde yanlış çıkar. İç döngü hiç dönmez, ama dış tur yine de sayılır. Sonuç 0 + 1 + 4 + 9 = 14'tür. Şekil 1.2.9 turları satır satır kutularla gösterir: i. satırda i² kutu vardır.

Bir adım daha büyük girdide örüntü daha belirgin olur. f2(5)'te dış döngü bir tur daha döner ve i = 4'te iç döngü 16 kez çalışır. Toplam 0 + 1 + 4 + 9 + 16 = 30'dur. Şekil 1.2.10 her dış turu bir çubukla gösterir. Çubukların yüksekliği i²'dir ve toplam alan fonksiyonun yaptığı x++ sayısıdır. Son çubuk tek başına toplamın yarısından fazlasını oluşturur: son turlar baskındır.

1.2.3.5Toplamı hesaplamak

Ardışık karelerin toplamı için kapalı bir formül vardır:

Σ_i=0ⁿ⁻¹ i² = (n − 1) · n · (2n − 1) / 6 = (2n³ − 3n² + n) / 6

Formül küçük değerlerle denetlenebilir. n = 5 için 4 · 5 · 9 / 6 = 30 bulunur; bu, izlemedeki toplamdır. n = 4 için 3 · 4 · 7 / 6 = 14 bulunur. Açılmış biçimde baskın terim 2n³/6 = n³/3'tür. Sabit 1/3 ve düşük dereceli terimler atılınca sonuç çıkar:

T(n) = Θ(n³)

Tablodaki iki sütun n büyüdükçe birbirine yaklaşır. n = 4'te oran 14/21 ≈ 0,67 iken n = 32'de 10 416/10 923 ≈ 0,95'tir. Düşük dereceli −3n²/6 terimi küçük n'de etkilidir, büyük n'de önemini yitirir. Kübik büyümenin bir işareti de ikiye katlama testidir. n, 16'dan 32'ye çıkınca dönüş değeri 10 416 / 1 240 = 8,4 katına çıkar. Bu sayı 2³ = 8'e yakındır; n büyüdükçe oran 8'e daha da yaklaşır.

Bu kesimdeki sonuç genel bir kuralın örneğidir: Σ_i<n i^k = Θ(n^k+1). İç döngünün tur sayısı dış sayacın k. kuvvetiyse toplam iş bir derece yükselir. Kural, toplamın bir integrale benzemesinden gelir: ∫₀ⁿ x^k dx = n^k+1/(k + 1). f2 için k = 2'dir ve integral n³/3 verir; açık formüldeki baskın terimle aynıdır.

1.2.3.6Döngü kalıpları ve toplam formülleri

Döngü analizinde birkaç kalıp tekrar tekrar karşımıza çıkar. Her biri bilinen bir seriye indirgenir: aritmetik seri, kareler toplamı ya da geometrik seri. Tablo 1.2.12 bu kalıpları toplar. Tur sayıları n = 16 ve n = 20 için Java ile sayılarak denetlenmiştir.

Tablonun üçüncü satırı, f2'nin bir derece düşük kardeşidir. İç döngü i kez döner; toplam 0 + 1 + … + (n − 1) = n(n − 1)/2'dir. Bu sayı n · n'nin yaklaşık yarısıdır; sabit çarpan farkı olduğu için sınıf yine Θ(n²)'dir. Seçmeli ve eklemeli sıralamanın karesel olmasının sebebi bu kalıptır.

Beşinci satır çarpımsal bir döngüdür. i her turda iki katına çıkar: 1, 2, 4, 8, …. k turdan sonra i = 2^k olur. Döngü 2^k < n iken sürer; k ≥ log₂ n olunca durur. Tur sayısı bu yüzden ⌈log₂ n⌉'dir. n = 16'da i 1, 2, 4, 8 değerlerini alır ve 4 tur döner; n = 1000'de 1'den 512'ye kadar 10 tur döner. Sayacı sabit bir oranla büyüyen ya da küçülen her döngü logaritmiktir.

Altıncı satırda dış döngü logaritmik, iç döngü doğrusaldır. İç döngünün sınırı dış sayaca bağlı değildir; her turda tam n kez döner. Bu yüzden çarpım kuralı uygulanır: (⌊log₂ n⌋ + 1) · n. n = 16 için dış döngü i = 16, 8, 4, 2, 1 değerlerinde 5 tur döner; toplam 5 · 16 = 80'dir.

Yedinci satır şaşırtıcıdır. Görünüşte yapısı bir öncekine benzer: logaritmik bir dış döngü ve onun içinde bir iç döngü. Ama iç döngünün sınırı i'dir ve i hızla büyür. Toplam, bir geometrik seridir:

1 + 2 + 4 + … + 2^k = 2^k+1 − 1 < 2n

Burada 2^k, n'den küçük en büyük ikinin kuvvetidir; bu yüzden 2^k+1 < 2n olur. Dış döngü log n kez dönse de toplam iş doğrusaldır. n = 16'da 1 + 2 + 4 + 8 = 15 tur yapılır. Geometrik serinin özelliği budur: toplamı son terimi belirler, son terim de öncekilerin hepsinin toplamından büyüktür.

// birinci parça
for (int i = 1; i < n; i *= 2)
  for (int j = 0; j < i; j++)
    x++;

// ikinci parça
for (int i = n; i > 0; i /= 2)
  for (int j = 0; j < n; j++)
    x++;

1.2.3.7f6: kaydırmalı döngü

public static int f6(int n) {
  int x = 0;
  // 1 << i, 2^i ile aynıdır (taşma yok sayılır)
  for (int i = 0; i < n; i = 1 << i) {
    x++;
  }
  return x;
}

f6'nın döngüsü ilk bakışta çarpımsal döngüye benzer, ama güncellemesi farklıdır.

• İlk değer: int i = 0; sabit süreli bir atamadır.
• Koşul: i < n, her turun başında i'nin n'den küçük olup olmadığını denetler.
• Güncelleme: i = 1 << i. Sola kaydırma işleci <<, 1 sayısının bitlerini i basamak sola kaydırır. İkili tabanda 1'i i basamak sola kaydırmak, onu 2ⁱ ile çarpmaktır. Sonuç 2ⁱ'dir ve tek bir işlemde, sabit sürede hesaplanır.

Kritik nokta şudur: güncelleme i = 2 * i değil, i = 2i'dir. Çarpımsal döngüde i her turda iki katına çıkar. f6'da ise i'nin kendisi üs olur. Bu, i'yi çok daha hızlı büyütür: 4 değeri bir sonraki turda 8 değil, 2⁴ = 16 olur. 16 da 32 değil, 2¹⁶ = 65 536 olur.

1.2.3.8Kod izleme: f6(20)

Döngü yalnız beş tur döner. i'nin aldığı değerler 0, 1, 2, 4, 16'dır; bir sonraki değer 65 536 olduğu için döngü biter. Şekil 1.2.11 bu zinciri gösterir. Aynı döngü n = 65 536'da da beş tur döner; n üç bin kat büyüdüğü hâlde tur sayısı değişmez.

1.2.3.9f6 gerçekte kaç tur döner?

f6'nın i değerleri, ikinin kuvvetlerinden oluşan bir kule gibi büyür:

0 → 2⁰ = 1 → 2¹ = 2 → 2² = 4 → 2⁴ = 16 → 2¹⁶ = 65 536 → 2^{65 536}

Son değer, 19 729 basamaklı bir sayıdır. Evrendeki atom sayısının yaklaşık 10⁸⁰ olduğu tahmin edilir; bu sayının yanında 10⁸⁰ çok küçük kalır. Hiçbir gerçek girdi bu kadar büyük olamayacağına göre f6, akla gelebilecek her n için en çok altı tur döner.

Bu döngü için sık görülen bir akıl yürütme şöyledir: “k turdan sonra i ≥ 2^k olur; döngü 2^k ≥ n olunca durur; öyleyse k ≈ log₂ n ve süre O(log n).” Akıl yürütme, i = 2 * i döngüsü için doğrudur. f6'da da sonuç yanlış değildir, çünkü i en az iki katına çıktığı için tur sayısı log₂ n'yi aşamaz. Ama bu sınır sıkı değildir. f6'da k turdan sonra i, k − 1 katlı bir kuledir ve tur sayısı çok daha yavaş büyüyen bir fonksiyonla verilir.

f6'nın tur sayısı tam olarak log* n + 1'dir. Bu eşitlik n = 1'den 70 000'e kadar her değer için bir Python betiğiyle denetlenmiştir. log* n, akla gelebilecek her girdide 5'i geçmez: log* 65 536 = 4'tür ve 5'e ulaşmak için n'nin 65 536'yı aşması gerekir. Değeri 6 olan en küçük sayı ise 2^{65 536}'dan büyüktür. Pratikte sabit gibi davranan bu fonksiyon, birleşim-bul (union-find) veri yapısının analizinde de karşımıza çıkar.

Küçük n'de f6 ile ⌈log₂ n⌉ birbirine yakındır; n = 32'de ikisi de 5'tir. n büyüdükçe logaritma artmayı sürdürür, f6 ise 5'te kalır. Sonuç: O(log n) doğru bir üst sınırdır, ama sıkı sınır Θ(log* n)'dir.

f6'nın kodundaki yorum satırı “taşma yok sayılır” der. Bu varsayım Java'da önemlidir. Java'da int 32 bitliktir ve kaydırma işleci, kaydırma miktarının yalnız son beş bitini kullanır; yani miktarın 32'ye göre kalanını alır. 65 536 = 32 · 2048 olduğundan 1 << 65536, 1 << 0 ile aynıdır ve 1 verir. Bu yüzden n > 65 536 için i 0, 1, 2, 4, 16, 65 536, 1, 2, 4, 16, 65 536, … döngüsüne girer; koşul hiç yanlış olmaz ve f6 hiç bitmez. Bu davranış, n = 100 000 ile çalıştırılan ve tur sayısı sınırlanan bir kopyayla gözlenmiştir. Analizdeki Θ(log* n) sonucu, sınırsız tamsayılarla çalışan soyut makine için geçerlidir.

1.2.4Özyinelemeli analiz

Döngülü kodda tur sayıları toplanır. Özyinelemeli kodda ise süre, aynı fonksiyonun daha küçük girdilerdeki süresine bağlıdır. T(n)'yi bulmak için önce T(n − 1) ya da T(n/2) gibi değerler gerekir. Bu ilişkiyi yazan denkleme özyineleme bağıntısı denir. Bu kesim bağıntının nasıl kurulduğunu ve en temel çözüm yöntemi olan açma yöntemini anlatır.

1.2.4.1Özyineleme bağıntısı

Bağıntıyı kurmak için koda üç soru sorulur:

1. Kaç özyinelemeli çağrı var? Bu sayı, bağıntıda T'nin katsayısı olur.
2. Her çağrının girdisi ne kadar küçülüyor? Girdi bir azalıyorsa T(n − 1), yarıya iniyorsa T(n/2) yazılır.
3. Çağrıların dışında ne kadar iş yapılıyor? Bölme, birleştirme, toplama gibi işlerin süresi bağıntıya ek terim olarak girer.

Bağıntı kurulduktan sonra çözülmesi gerekir; yani T(n)'nin, içinde T geçmeyen kapalı bir biçimi bulunur. Üç yöntem vardır:

• Açma (yerine koyma): Bağıntı kendi içine tekrar tekrar konur, bir örüntü bulunur, taban duruma ulaşınca terimler toplanır. f3'te kullanılır.
• Özyineleme ağacı (recursion tree): Her çağrı bir düğüm olarak çizilir, her seviyedeki iş toplanır, sonra seviye toplamları toplanır. f3, f4 ve f5'te kullanılır.
• Ana Teorem (master theorem): T(n) = aT(n/b) + f(n) biçimindeki bağıntılar için hazır bir sonuç verir. f4 ve f5'te kullanılır.

1.2.4.2f3: iki çağrı, n − 1

public long f3(int n) {
  if (n <= 1) {
    return 1;
  }
  return f3(n - 1) + f3(n - 1);
}

f3 iki parçadan oluşur.

• Taban durum: n ≤ 1 iken fonksiyon 1 döndürür. Bu sabit süreli bir iştir: T(1) = c.
• Özyinelemeli durum: n > 1 iken f3(n − 1) iki kez çağrılır ve sonuçlar toplanır. Toplama ve karşılaştırma sabit bir iştir; buna da c denir.

Üç soru cevaplanınca bağıntı ortaya çıkar: iki çağrı vardır, her biri n − 1 boyutludur, çağrı dışında sabit iş yapılır.

T(n) = 2T(n − 1) + c, n > 1;  T(1) = c

Girdi her çağrıda yalnız bir azalır, ama çağrı sayısı her seviyede iki katına çıkar. f3(4), iki f3(3)'ü; her f3(3) iki f3(2)'yi; her f3(2) de iki f3(1)'i çağırır. Seviyelerde 1, 2, 4, 8 çağrı vardır ve toplam 1 + 2 + 4 + 8 = 15 = 2⁴ − 1 eder (Şekil 1.2.13).

Bu bağıntı T(n/b) biçiminde değildir; alt problem bölünerek değil bir çıkarılarak küçülür. Bu yüzden Ana Teorem uygulanamaz ve bağıntı açma yöntemiyle çözülür.

1.2.4.3Kod izleme: f3(3)

Özyinelemeli kodun izlenmesinde çağrıların hangi sırayla başlayıp bittiği önemlidir. f3(3) çağrısının adımları şöyledir; girinti, çağrının derinliğini gösterir. Sıra Java ile çalıştırılan ve her çağrının başını ve sonunu yazdıran bir kopyayla doğrulanmıştır.

İzleme üç şey gösterir. Toplam 7 = 2³ − 1 çağrı yapılmıştır. Yığında aynı anda en çok üç çerçeve bulunmuştur; bu, n'ye eşit olan derinliktir. Üçüncüsü ve en önemlisi, sağdaki f3(2) soldakinin yaptığı işi aynen tekrarlar. f3'ün üstel süresinin kaynağı bu tekrardır. Kod return 2 * f3(n - 1); diye yazılsaydı dönüş değeri aynı kalırdı (2ⁿ⁻¹), ama her seviyede tek çağrı yapılırdı. Bağıntı T(n) = T(n − 1) + c'ye iner ve süre Θ(n) olur.

1.2.4.4Bağıntıyı açma

Açma yönteminde bağıntının sağ tarafındaki T(n − 1), kendi tanımıyla değiştirilir. İşlem birkaç kez tekrarlanınca katsayılarda bir örüntü belirir. Örüntü genel biçimde yazılır ve taban duruma ulaşılan adım bulunur.

Sonuç, f3'ün çağrı sayısıyla birebir uyuşur: her çağrı c iş yapar ve 2ⁿ − 1 çağrı vardır. Formül küçük değerlerle denetlenebilir: T(1) = c, T(2) = 3c, T(3) = 7c. Java ile sayıldığında f3(16) 65 535, f3(32) ise 4 294 967 295 çağrı yapar; ikisi de 2ⁿ − 1'dir. n 16'dan 32'ye çıkınca çağrı sayısı 65 537 katına çıkar. Üstel büyümenin işareti budur: girdi iki katına çıkınca süre karesine yakın bir değere ulaşır.

Açma yönteminde ek işi (c) ihmal edip T(n) = 2^k T(n − k) yazmak da olur. Bu durumda T(n) = 2ⁿ⁻¹ T(1) çıkar ve büyüme sınıfı değişmez. Ek iş, yalnız sabit çarpanı ikiye katlar.

Açma yöntemi başka çıkarmalı bağıntılara da uygulanır. T(n) = T(n − 1) + n, T(1) = 1 bağıntısı açılınca T(n) = n + (n − 1) + … + 2 + 1 = n(n + 1)/2 bulunur: Θ(n²). Bu bağıntı, her adımda n iş yapıp problemi yalnız bir küçülten algoritmalarda çıkar. Hızlı sıralamanın en kötü durumu buna bir örnektir.

1.2.5Ana Teorem

Açma yöntemi her bağıntıda işe yarar, ama zahmetlidir. Algoritmaların büyük bir kısmı, problemi eşit büyüklükte parçalara bölen böl ve fethet (divide and conquer) yaklaşımını kullanır. Bu algoritmaların bağıntıları hep aynı biçimdedir. Ana Teorem, bu biçimdeki bağıntılar için hazır bir sonuç verir. Teorem, Jon Bentley, Dorothea Haken ve James Saxe'ın 1980'de yayımladığı genel bir yönteme dayanır; “Ana Teorem” adı ise Cormen ve arkadaşlarının ders kitabıyla yaygınlaştı.

1.2.5.1Böl ve fethet bağıntısı

Böl ve fethet bir algoritma, n boyutlu problemi her biri n/b boyutlu a alt probleme böler, alt problemleri özyinelemeyle çözer ve sonuçları birleştirir. Bağıntısı şöyledir:

T(n) = a · T(n/b) + f(n), a ≥ 1, b > 1

• a: alt problem (özyinelemeli çağrı) sayısı.
• b: küçülme oranı; her alt problemin boyutu n/b'dir.
• f(n): çağrının kendi yaptığı iş, yani problemi bölme ve sonuçları birleştirme işi.

Bu bağıntının özyineleme ağacı düzenli bir yapıdadır (Şekil 1.2.16). Kökte tek bir düğüm vardır ve f(n) iş yapar. Her düğümün a çocuğu vardır; j. seviyede a^j düğüm bulunur ve her biri n/b^j boyutlu bir problemle uğraşır. Girdi her seviyede b'ye bölündüğü için ağacın derinliği log_b n'dir. Son seviyedeki yaprak sayısı

a^{log_b n} = n^{log_b a}

olur. İki ifadenin eşitliği, iki tarafın da log_b'si alınınca görülür: ikisi de log_b n · log_b a verir. Her yaprak sabit iş yaptığı için yaprakların toplam işi Θ(n^{log_b a})'dır. Bu nicelik teoremin merkezindedir: f(n) her zaman onunla karşılaştırılır.

1.2.5.2Üç durum

Teorem, f(n) ile yaprak işi n^{log_b a}'yı karşılaştırır. Karşılaştırmanın üç sonucu vardır: kök tarafındaki iş baskındır, yapraklardaki iş baskındır ya da seviyeler dengelidir. Aşağıda teoremin, f(n)'nin polinom derecesi c ile yazılan sık kullanılan biçimi verilir.

Üç durumda farklı gösterimlerin kullanılması rastlantı değildir. Durum 1'de f(n) için bir üst sınır yeter, çünkü yaprak işi zaten f'den büyüktür ve onu bastırır. Durum 2 ve 3'te ise yalnız f(n) = O(n^c) yazmak yetmez. Örneğin f(n) = 1 de O(n²)'dir; ama T(n) = T(n/2) + 1 bağıntısının çözümü Θ(n²) olamaz. Bu yüzden Durum 2'de f = Θ(n^c), Durum 3'te f = Ω(n^c) ve ayrıca düzenlilik koşulu istenir. Bu koşullar sağlanınca sonuçlar Θ ile, yani sıkı olarak verilir.

Düzenlilik koşulu (regularity condition), Durum 3'e özgüdür: a · f(n/b) ≤ k · f(n). Anlamı şudur: kökün çocuklarının toplam işi, kökün kendi işinin sabit bir kesrinden fazla değildir. Böylece iş, köke doğru giderek büyür. f(n) = n^c gibi polinomlarda koşul kendiliğinden sağlanır: a(n/b)^c = (a/b^c) n^c'dir ve c > log_b a olduğundan a/b^c < 1'dir; k = a/b^c seçilebilir.

1.2.5.3Neden üç durum? Seviye toplamları

Teoremin neden üç durumdan oluştuğu, özyineleme ağacının seviye toplamlarına bakınca anlaşılır. f(n) = n^c olsun. j. seviyede a^j düğüm vardır ve her biri (n/b^j)^c iş yapar. Seviyenin toplam işi

a^j · (n/b^j)^c = n^c · (a/b^c)^j

olur. Seviye toplamları, oranı r = a/b^c olan bir geometrik seri oluşturur. T(n), bu serinin j = 0'dan log_b n'ye kadar toplamıdır. Geometrik serinin davranışı ise yalnız orana bağlıdır:

• r > 1: seri artar. Toplamı son terim, yani yapraklar belirler. Bu Durum 1'dir. Örnek: 4T(n/2) + n için r = 4/2 = 2; seviye toplamları n, 2n, 4n, … diye artar ve sonuç Θ(n²) çıkar.
• r = 1: terimler eşittir. Her seviye aynı işi yapar; toplam, seviye sayısı ile seviye işinin çarpımıdır. Bu Durum 2'dir. Örnek: 2T(n/2) + n için r = 2/2 = 1; log n seviyenin her biri n iş yapar ve sonuç Θ(n log n) çıkar.
• r < 1: seri azalır. Toplamı ilk terim, yani kök belirler. Bu Durum 3'tür. Örnek: 2T(n/2) + n² için r = 2/4 = 1/2; seviye toplamları n², n²/2, n²/4, … diye azalır, toplamları 2n²'yi geçmez ve sonuç Θ(n²) çıkar.

Oranın 1'den büyük olması ile c < log_b a aynı şeydir: r > 1 ⇔ b^c < a ⇔ c < log_b a. Ana Teoremin üç durumu böylece geometrik serinin artan, sabit ya da azalan olmasına karşılık gelir. Teoremi ezberlemek yerine bu tabloyu akılda tutmak yeter: a ile b^c karşılaştırılır.

Bu sonuçlar küçük bir hesapla da denetlenebilir. Bağıntılar T(1) = 1 ile doğrudan hesaplandığında n = 16 için 2T(n/2) + n 80 verir; bu, n log₂ n + n değeridir. 2T(n/2) + n² ise 496 verir, yani 2n² − n; kökteki n² = 256 toplamın yarısından fazlasıdır.

1.2.5.4Örnek: 2T(n/2) + n

Bu bağıntı algoritmaların en tanıdıklarından birkaçında karşımıza çıkar.

• Birleştirme sıralaması (merge sort): dizi ikiye bölünür, iki yarı ayrı ayrı sıralanır, sıralı yarılar Θ(n) sürede birleştirilir.
• f5: bölümün örnek fonksiyonlarından biridir; f1(n)'yi çağırır (doğrusal iş) ve kendini iki kez n/2 ile çağırır.
• Hızlı sıralama (quick sort): pivot diziyi her seferinde iki eşit parçaya bölerse bağıntı aynıdır.

1.2.5.5Daha fazla örnek

Tablo 1.2.17 teoremi sık karşılaşılan bağıntılara uygular. Her satırda önce log_b a hesaplanır, sonra f(n)'nin derecesi c ile karşılaştırılır. Logaritma değerleri Python ile hesaplanmıştır.

Tablonun ilk satırı ikili aramadır: her adımda tek bir alt problem (a = 1) yarı boyutta çözülür ve sabit iş yapılır. log₂ 1 = 0 ve c = 0 olduğundan Durum 2 uygulanır: Θ(n⁰ · log n) = Θ(log n). Sabit bir f(n)'nin Durum 2'ye girmesi şaşırtıcı görünebilir; ama ağaçta her seviyede tek düğüm vardır ve her seviye aynı sabit işi yapar.

Karatsuba ve Strassen satırları, böl ve fethetin gücünü gösterir. İki n basamaklı sayıyı okulda öğretilen yöntemle çarpmak Θ(n²) sürer. Sayıları ikiye bölüp dört yarı çarpım yapmak da bunu değiştirmez: 4T(n/2) + n = Θ(n²). Anatoli Karatsuba 1962'de dört çarpımdan birinin ötekilerden hesaplanabildiğini gösterdi. Üç çarpımla bağıntı 3T(n/2) + n olur ve sonuç Θ(n^{log₂ 3}) ≈ Θ(n^1,585)'e iner. Volker Strassen 1969'da aynı düşünceyi matris çarpımına uyguladı: sekiz yerine yedi alt çarpım. 8T(n/2) + n² bağıntısı Θ(n³) verir; 7T(n/2) + n² ise Θ(n^{log₂ 7}) ≈ Θ(n^2,807) verir. İki örnekte de tek bir alt çağrıyı azaltmak, üssü küçültmüştür. Durum 1'de sonucu yalnız a ve b belirlediği için a'daki her azalma doğrudan kazanca dönüşür.

Durum 3 satırlarında düzenlilik koşulu da denetlenmelidir. 2T(n/2) + n² için 2 · (n/2)² = n²/2 ≤ ½ · n² olduğundan k = ½ ile koşul sağlanır. T(n/2) + n için 1 · (n/2) ≤ ½ · n, yine k = ½.

1.2.5.6Teoremin uygulanamadığı bağıntılar

Ana Teorem güçlüdür, ama yalnız belirli bir biçimdeki bağıntılara uygulanır. Biçimin dışına çıkan bağıntılarda başka bir yöntem gerekir.

• Çıkarmalı bağıntılar. T(n) = 2T(n − 1) + c (f3) ya da T(n) = T(n − 1) + n: alt problem n/b değil, n − 1'dir. Açma yöntemi kullanılır.
• Polinom olmayan fark. T(n) = 2T(n/2) + n / log n: n^{log₂ 2} = n ile f(n) = n / log n karşılaştırılır. f(n), n'den küçüktür ama yalnız bir log çarpanı kadar; n^ε gibi bir polinom çarpanı kadar değil. Bu yüzden ne Durum 1'in ne de Durum 2'nin koşulu sağlanır. (Bağıntının çözümü Θ(n log log n)'dir ve özyineleme ağacıyla bulunur.)
• Eşit olmayan bölme. T(n) = T(n/3) + T(2n/3) + n: alt problemler farklı boyuttadır. Özyineleme ağacında her seviyenin işi en çok n'dir ve en uzun dal log_3/2 n derinliktedir; sonuç Θ(n log n)'dir. Bu tür bağıntıları genel olarak Akra–Bazzi yöntemi çözer.
• Sabit olmayan a ya da a < 1. T(n) = 2ⁿ T(n/2) + n ya da T(n) = ½ T(n/2) + n: teoremin a ≥ 1 sabit varsayımı bozulur.

Temel biçimin sık kullanılan bir genişlemesi, Durum 2'yi logaritma çarpanlarına uzatır: f(n) = Θ(n^{log_b a} · log^k n) ve k ≥ 0 ise T(n) = Θ(n^{log_b a} · log^k+1 n). Örneğin T(n) = 2T(n/2) + n log n için k = 1 ve sonuç Θ(n log² n)'dir. Bu genişleme, temel biçimin “uygulanamaz” dediği bazı bağıntıları da çözer.

1.2.6Uygulama: f4 ve f5

Bu kesim, iki özyinelemeli fonksiyonu üç yöntemle birden çözer: izleme, özyineleme ağacı ve Ana Teorem. f4, f3'ün yalnız tek bir karakteri değiştirilmiş hâlidir; ama bu değişiklik süreyi üstelden doğrusala indirir. f5 ise f4'e her çağrıda doğrusal bir iş ekler ve birleştirme sıralamasının bağıntısını verir.

1.2.6.1f4: iki çağrı, n/2

public int f4(int n) {
  if (n <= 1) {
    return 1;
  }
  return f4(n / 2) + f4(n / 2);
}

• Taban durum: n ≤ 1 iken 1 döner; O(1).
• Özyinelemeli durum: n > 1 iken f4(n / 2) iki kez çağrılır ve sonuçlar toplanır. Toplama sabit bir iştir.

T(n) = 2T(n/2) + O(1), T(1) = O(1)

Java'da n / 2 tamsayı bölmesidir; kesirli kısım atılır. Analizde n'nin ikinin kuvveti olduğu varsayılır, böylece her bölme tam çıkar. Bu varsayım büyüme sınıfını değiştirmez.

f3 ile tek fark, girdinin n − 1 yerine n/2 olmasıdır. Çağrı sayısı yine her seviyede ikiye katlanır; ama girdi her seviyede yarıya indiği için ağaç yalnız log₂ n seviye derinliğindedir. n = 8 için seviyelerde 1, 2, 4, 8 çağrı vardır ve girdiler 8, 4, 2, 1'dir. f3'te 8'den başlayan bir ağaç 8 seviye inerdi; burada 4 seviyede biter.

İki çağrı her zaman üstel süre demek değildir. Belirleyici olan, girdinin ne kadar küçüldüğüdür. Girdi bir azalırsa ağaç n derinliğe iner ve 2ⁿ yaprağa ulaşır. Girdi yarıya inerse ağaç log₂ n derinlikte kalır ve 2^{log₂ n} = n yaprağa ulaşır.

1.2.6.2f4'ün özyineleme ağacı

Özyineleme ağacı yönteminde her çağrı bir düğüm olarak çizilir ve yanına yaptığı iş yazılır. Sonra her seviyenin işi toplanır, en sonda da seviye toplamları toplanır. f4(8) için:

1. Kök: f4(8) yalnız sabit iş (c) yapar ve iki çağrı başlatır. Seviye 0'ın işi c'dir.
2. Seviye 1: iki f4(4) çağrısı; toplam 2c.
3. Seviye 2: dört f4(2) çağrısı; toplam 4c. Seviye işi her adımda iki katına çıkar.
4. Yapraklar: sekiz f4(1); toplam 8c = n · c.

Toplam c(1 + 2 + 4 + 8) = 15c = (2n − 1)c'dir; yani Θ(n). Seviye toplamları geometrik olarak artar ve toplamı son terim, yaprakların işi belirler. Java ile sayıldığında f4(16) 31, f4(32) 63 çağrı yapar; ikisi de 2n − 1'dir. Fonksiyonun dönüş değeri de yaprak sayısına eşittir: f4(n) = n.

n ikinin kuvveti değilse tamsayı bölmesi devreye girer. f4(10) önce iki f4(5)'i, her f4(5) iki f4(2)'yi, her f4(2) de iki f4(1)'i çağırır. Çağrı sayısı 15, dönüş değeri 8'dir. Sonuç, n'den küçük en büyük ikinin kuvvetine (8) göre çalışmış gibidir; büyüme sınıfı yine doğrusaldır.

1.2.6.3f4'ü Ana Teorem ile çözmek

Ana Teorem, özyineleme ağacının verdiği sonucu toplamı hesaplamadan verir. Ağaçta 2n − 1 düğüm sayılmıştı; teorem yalnız “yapraklar baskın” der ve yaprak sayısı n olduğu için Θ(n) sonucuna varır.

f4'ün belleği ise farklı bir sorudur. Çağrılar sırayla yürüdüğü için yığında aynı anda yalnız bir dal bulunur: f4(n), f4(n/2), …, f4(1). Bu dalın uzunluğu log₂ n + 1'dir; f4(16) çalışırken yığında en çok 5 çerçeve bulunur. Zaman Θ(n), ek bellek Θ(log n)'dir.

1.2.6.4f5: doğrusal iş ve iki çağrı

public int f5(int n) {
  if (n <= 1) {
    return 1;
  }
  return f1(n) + f5(n / 2) + f5(n / 2);
}

• Taban durum: n ≤ 1 iken 1 döner; O(1).
• Özyinelemeli durum: n > 1 iken önce f1(n) çağrılır. f1, n tur dönen bir döngüdür ve Θ(n) iş yapar. Ardından f5(n / 2) iki kez çağrılır.

T(n) = 2T(n/2) + f1(n) = 2T(n/2) + Θ(n)

f4'ten tek farkı her çağrıda yapılan doğrusal iştir. Bağıntı birleştirme sıralamasının bağıntısıyla aynıdır. Burada sık yapılan bir hata, iki parçayı ayrı ayrı düşünüp toplamaktır: “f1 doğrusal, özyineleme logaritmik, toplam O(n + log n) = O(n).” Bu yanlıştır. f1 yalnız kökte değil, ağacın her düğümünde çağrılır; her düğüm kendi girdisi kadar iş yapar. Bu işlerin toplamı bulunmalıdır.

1.2.6.5Kod izleme: f5(4)

Sonuç 12'dir. Bu sayı işin seviyelere nasıl dağıldığını da gösterir. Kökte f1(4) 4 birim, birinci seviyede iki f1(2) toplam 4 birim iş yapar. Dört yaprağın her biri 1 döndürür; toplam 4. Her seviyenin işi n = 4'tür. log₂ 4 = 2 iç seviye ve bir yaprak seviyesi vardır: 2 · 4 + 4 = 12 = n log₂ n + n.

1.2.6.6f5'in özyineleme ağacı ve Ana Teorem

f5(8)'in ağacında örüntü daha açık görülür (Şekil 1.2.21).

1. Kök: f5(8) içinde f1(8) 8 adım yapar.
2. Seviye 1: iki f5(4), her biri f1(4) ile 4 adım; toplam 8.
3. Seviye 2: dört f5(2), her biri 2 adım; toplam yine 8.
4. Yapraklar: sekiz f5(1), her biri 1; toplam 8.

Toplam 3 · 8 + 8 = 32 = n log₂ n + n'dir ve Java'da f5(8) gerçekten 32 döndürür. Her seviye n iş yapar ve log₂ n iç seviye vardır; sonuç Θ(n log n)'dir. Daha büyük girdilerde de formül tutar: f5(16) = 80 = 16 · 4 + 16, f5(32) = 192 = 32 · 5 + 32.

Ana Teorem ile çözüm, f4'tekiyle aynı adımları izler; yalnız f(n) değişmiştir:

1. T(n) = 2T(n/2) + Θ(n): a = 2, b = 2, f(n) = Θ(n).
2. log_b a = 1, c = 1. Üsler eşit: Durum 2.
3. T(n) = Θ(n^{log_b a} · log n) = Θ(n log n).

Tablo, f3–f4–f5 üçlüsünün öğrettiğini özetler. Üç fonksiyon da kendini iki kez çağırır. f3 ile f4 arasındaki fark küçülme biçimidir (n − 1 ile n/2) ve sonucu Θ(2ⁿ)'den Θ(n)'ye indirir. f4 ile f5 arasındaki fark ek iştir (sabit ile doğrusal) ve sonucu Θ(n)'den Θ(n log n)'ye çıkarır.

1.2.7Karşılaştırma ve amortize analiz

1.2.7.1f1–f6: ölçülen adım sayıları

Altı fonksiyonun analizle bulunan sınıfları, fonksiyonlar çalıştırılarak denetlenebilir. Tablo 1.2.20 her fonksiyonun n = 16 ve n = 32 için ölçülen adım sayısını verir. f1, f2, f5 ve f6 için dönüş değeri, f3 ve f4 için çağrı sayısı kullanılmıştır. Değerler Java ile ölçülmüştür.

Oran sütunu, büyüme sınıfını ele veren pratik bir testtir. n iki katına çıkınca doğrusal fonksiyonlar (f1, f4) iki katına çıkar. Log-doğrusal f5, 2'den biraz fazla, 2,4 katına çıkar; fazlalık log n çarpanının 4'ten 5'e artmasından gelir. Kübik f2 yaklaşık 8 katına çıkar. Üstel f3'ün oranı ise 2¹⁶ + 1 = 65 537'dir; girdi iki katına çıkınca adım sayısı yaklaşık karesine çıkmıştır. f6 yalnız bir adım artar.

Bu test, analizi doğrulamanın deneysel bir yoludur ve kodun karmaşıklığı bilinmediğinde de kullanılır. Bir program farklı n'lerle çalıştırılır, süre ya da adım sayısı ölçülür ve ardışık ölçümlerin oranına bakılır. Sedgewick ve Wayne bu yönteme “ikiye katlama deneyi” der. Sunumdaki etkileşimli adım sayacı aynı deneyi 1 ile 40 arasındaki her n için yapar ve sonuçları logaritmik ölçekli çubuklarla gösterir. Orada f5 için ayrıca çağrı sayısı da sayılır, bu yüzden değerler tablodakinden biraz büyüktür; oranlar ise aynı sınıfı gösterir.

1.2.7.2Amortize analiz

Bazı veri yapılarında işlemlerin çoğu ucuz, arada bir yapılan bazıları ise pahalıdır. Böyle bir yapıda tek bir işlemin en kötü durumuna bakmak, toplam maliyeti olduğundan çok gösterir. Amortize analiz, işlem dizisinin bütününe bakar.

Klasik örnek, Java'daki ArrayList gibi dinamik dizidir (dynamic array). Dizi dolduğunda kapasitesi iki katına çıkarılır: iki kat büyüklükte yeni bir dizi ayrılır ve bütün öğeler oraya kopyalanır. Bu ekleme pahalıdır. Yer olduğu sürece yapılan eklemeler ise tek bir yazmadır ve 1 birim tutar. Aşağıdaki kod bu mantığı yazar; maliyet, yazma sayısı ile kopyalanan öğe sayısının toplamıdır.

int[] veri = new int[1];
int boyut = 0;
long maliyet = 0;

void ekle(int x) {
  if (boyut == veri.length) {               // dizi dolu
    int[] yeni = new int[2 * veri.length];  // kapasiteyi iki katına çıkar
    for (int i = 0; i < boyut; i++) {
      yeni[i] = veri[i];                    // kopya: 1 birim
      maliyet++;
    }
    veri = yeni;
  }
  veri[boyut++] = x;                        // yazma: 1 birim
  maliyet++;
}

Teorem, kopyalamanın pahalı olduğu anların seyrek olmasına dayanır. Bir kapasite artırması m öğeyi kopyalar, ama ondan sonra m ekleme daha ucuza yapılır. Pahalı işlemin maliyeti, onu izleyen ucuz işlemlere “yayılır”. Python ile yapılan bir sayımda 1000 eklemenin toplam maliyeti 2023 çıkar; bu, 3n = 3000'in altındadır.

İki katına büyütmenin neden önemli olduğu, sabit miktarla büyütmeyle karşılaştırınca görülür. Dizi dolduğunda kapasite yalnız 1 artırılsaydı her ekleme bütün diziyi kopyalardı. n eklemenin toplam maliyeti 1 + 2 + … + n = n(n + 1)/2, yani Θ(n²) olurdu; n = 1000 için 500 500 birim. Kapasite sabit bir k kadar artırılsa da sonuç değişmez, yalnız sabit çarpan küçülür.

Amortize analiz, ortalama durum analizinden farklıdır. Ortalama durum, girdilerin bir olasılık dağılımına dayanır ve “beklenen” süreyi verir. Amortize analizde olasılık yoktur: her işlem dizisi için, en kötü dizide bile geçerli bir garanti verilir. Dinamik dizide tek bir ekleme Θ(n) sürebilir; ama hangi sırayla ekleme yapılırsa yapılsın, n eklemenin toplamı 3n'yi aşmaz. Amortize maliyeti bulmanın üç standart yöntemi vardır: toplama yöntemi (burada kullanılan), hesap (accounting) yöntemi ve potansiyel yöntemi.

1.2.8Sık yapılan hatalar

Bölüm boyunca kutularda verilen hataların en önemlileri bir arada şöyledir:

• Büyük O'yu en kötü durumla eş tutmak. O bir üst sınırdır, en kötü durum ise bir girdi türüdür. “En iyi durum O(1)'dir” geçerli bir cümledir.
• Sabitleri ve küçük terimleri yazmak. O(3n + 3) ya da O(n²/3 + n) yazılmaz; O(n) ve O(n²) yeterlidir.
• “İç içe döngü = n²” kuralı. Sonucu iç döngünün sınırı belirler. f2'de sınır i² olduğu için Θ(n³) çıkar; i *= 2 ile ilerleyen bir döngü ise log n tur döner.
• “İki çağrı = üstel” kuralı. f3 (n − 1) Θ(2ⁿ), f4 (n/2) Θ(n)'dir. Küçülme biçimi sonucu belirler.
• Ana Teoremi her bağıntıya uygulamak. T(n − 1) içeren, eşit bölmeyen ya da f(n) = n / log n gibi polinomdan farklı bir fark taşıyan bağıntılarda teorem geçerli değildir.
• Durum 3'te düzenliliği unutmak. c > log_b a yetmez; a · f(n/b) ≤ k · f(n), k < 1 de sağlanmalıdır.
• Özyinelemenin belleğini çağrı sayısıyla karıştırmak. Bellek, aynı anda açık olan çerçeve sayısıyla, yani derinlikle belirlenir: f3'te Θ(n), f4'te Θ(log n).
• Kaydırmayı çarpmayla karıştırmak. i = 1 << i, 2ⁱ'dir; 2 * i değildir. f6'nın sıkı sınırı Θ(log* n)'dir.

1.2.9Özet

• Zaman karmaşıklığı T(n), temel işlem sayısının girdi boyutu n ile nasıl büyüdüğünü verir. Alan karmaşıklığı S(n), girdiye ek olarak kullanılan belleği verir; özyinelemede çağrı yığınının derinliği de bu belleğe girer.
• Süre ölçümü makineye bağlıdır ve büyük girdiler için tahmin vermez. RAM modelinde her temel işlem bir birim sayılır; doğrusal arama en kötü durumda 3n + 3 adım sürer ve Θ(n)'dir.
• En iyi, en kötü ve ortalama durum, aynı boyuttaki farklı girdilerle ilgilidir. Doğrusal aramada sırasıyla 1, n ve (n + 1)/2 karşılaştırma yapılır.
• f = O(g) üst sınır, f = Ω(g) alt sınır, f = Θ(g) sıkı sınırdır. Sınırlar c ve n₀ sabitleri bulunarak kanıtlanır; 3n² + 5n + 2 için c₁ = 3, c₂ = 4, n₀ = 6. Durum (hangi girdi) ile sınır (O, Ω, Θ) ayrı kavramlardır.
• Hesap kuralları: sabit çarpanlar ve düşük dereceli terimler atılır; ardışık kodda büyük olan kalır, iç içe kodda tur sayıları çarpılır ya da toplanır; logaritmanın tabanı önemsiz, üstel ifadenin tabanı önemlidir. Büyüme sırası: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!.
• Döngü analizinde her dış tur için iç döngünün tur sayısı yazılır ve toplanır. f1: Σ 1 = n, Θ(n). f2: Σ i² = (n − 1)n(2n − 1)/6, Θ(n³). Çarpımsal döngü Θ(log n); içinde j < i olan çarpımsal döngü geometrik seri nedeniyle Θ(n)'dir.
• f6'da i = 1 << i, yani i ← 2ⁱ'dir; tur sayısı log* n + 1'dir. O(log n) doğru ama sıkı değildir; sıkı sınır Θ(log* n)'dir. Java'da n > 65 536 için kaydırma taşar ve döngü bitmez.
• Özyineleme bağıntısı, çağrı sayısı, küçülme biçimi ve ek işten kurulur. f3: T(n) = 2T(n − 1) + c; açma yöntemiyle (2ⁿ − 1)c = Θ(2ⁿ). Belleği ise yalnız Θ(n)'dir.
• Ana Teorem, T(n) = aT(n/b) + f(n) bağıntısında f(n)'yi yaprak işi n^{log_b a} ile karşılaştırır: yapraklar baskın (Durum 1), seviyeler dengeli (Durum 2, ek log n çarpanı), kök baskın (Durum 3, düzenlilik koşuluyla). Üç durum, oranı a/b^c olan geometrik serinin artan, sabit ya da azalan olmasına karşılık gelir.
• Teorem çıkarmalı, eşit bölmeyen, f(n) farkı polinom olmayan ya da a'sı sabit olmayan bağıntılara uygulanmaz.
• f4: 2T(n/2) + 1, Durum 1, Θ(n); 2n − 1 çağrı, Θ(log n) bellek. f5: 2T(n/2) + n, Durum 2, Θ(n log n); f5(n) = n log₂ n + n.
• Amortize analiz, bir işlem dizisinin toplam maliyetini işlem sayısına böler. İki katına büyüyen dinamik dizide n eklemenin toplamı 3n'den azdır; ekleme amortize Θ(1)'dir. Ortalama durumdan farklı olarak olasılık kullanmaz.

1.2.10Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity
• karmaşıklık sınıfı complexity class
• büyüme hızı growth rate
• RAM modeli random-access machine
• en iyi durum best case
• en kötü durum worst case
• ortalama durum average case
• asimptotik gösterim asymptotic notation
• büyük O gösterimi Big O notation
• büyük Omega Big Omega (Ω)
• büyük Teta Big Theta (Θ)
• üst sınır upper bound
• alt sınır lower bound
• sıkı sınır tight bound
• sabit zaman constant time
• logaritmik logarithmic
• doğrusal linear
• log-doğrusal linearithmic
• karesel quadratic
• kübik cubic
• üstel exponential
• faktöriyel factorial
• polinom zaman polynomial time
• yinelenmiş logaritma iterated logarithm
• özyineleme recursion
• taban durum base case
• çağrı yığını call stack
• özyineleme bağıntısı recurrence relation
• özyineleme ağacı recursion tree
• böl ve fethet divide and conquer
• ana teorem master theorem
• düzenlilik koşulu regularity condition
• amortize analiz amortized analysis
• dinamik dizi dynamic array

1.2.11Kendini Dene

1. 5n³ + 2n + 8 = O(n³) sınırı için c = 6 seçiliyor. 5n³ + 2n + 8 ≤ 6n³ eşitsizliğinin her n ≥ n₀ için sağlandığı en küçük n₀ kaçtır?

   Cevap

   5n³ + 2n + 8 ≤ 6n³ ⇔ n³ ≥ 2n + 8. n = 2'de 8 < 12, eşitsizlik bozulur; n = 3'te 27 ≥ 14, sağlanır. n artınca n³, 2n + 8'den hızlı büyüdüğü için eşitsizlik bundan sonra hep sağlanır: n₀ = 3. Denetim: n = 3'te 149 ≤ 162.

2. for (i = 0; i < n; i++) for (j = i; j < n; j++) x++; parçası n = 6 için kaç kez x++ yapar? Büyüme sınıfı nedir?

   Cevap

   i. turda iç döngü n − i kez döner: 6 + 5 + 4 + 3 + 2 + 1 = 21. Genel olarak n(n + 1)/2, yani Θ(n²). İç döngünün dış sayaca bağlı olması toplamı yarıya indirir, ama sınıfı değiştirmez.

3. for (int i = 1; i * i <= n; i++) x++; döngüsü n = 64 için kaç tur döner? Büyüme sınıfı nedir?

   Cevap

   Döngü i² ≤ n, yani i ≤ √n iken sürer. n = 64 için i = 1, …, 8: 8 tur. Sınıf Θ(√n)'dir; deneme bölmesiyle asallık testi bu kalıbı kullanır.

4. 2ⁿ⁺¹ = O(2ⁿ) ve 2²ⁿ = O(2ⁿ) ifadelerinden hangisi doğrudur?

   Cevap

   Birincisi doğrudur: 2ⁿ⁺¹ = 2 · 2ⁿ; c = 2, n₀ = 1 yeter. İkincisi yanlıştır: 2²ⁿ = 4ⁿ ve 4ⁿ/2ⁿ = 2ⁿ oranı sonsuza gider; hiçbir sabit c bu farkı kapatamaz. Üsse eklenen sabit bir çarpan, üssü çarpan sabit ise tabanı değiştirir.

5. T(n) = 2T(n/4) + √n bağıntısının Ana Teoreme göre çözümü nedir?

   Cevap

   a = 2, b = 4, log₄ 2 = 1/2. f(n) = √n = n^1/2, c = 1/2. Üsler eşit: Durum 2, T(n) = Θ(√n log n). Denetim: T(1) = 1 ile T(256) = 80 = 16 · 4 + 16.

6. T(n) = 5T(n/2) + n² bağıntısının çözümü nedir? Seviye toplamları artar mı, azalır mı?

   Cevap

   log₂ 5 ≈ 2,32 > c = 2: Durum 1, T(n) = Θ(n^{log₂ 5}) ≈ Θ(n^2,32). Oran r = 5/2² = 1,25 > 1; seviye toplamları her seviyede 1,25 katına çıkar, yapraklar baskındır.

7. T(n) = T(n − 1) + 1, T(1) = 1 bağıntısının açma yöntemiyle bulunan kapalı biçimi nedir? Ana Teorem neden uygulanamaz?

   Cevap

   T(n) = T(n − 1) + 1 = T(n − 2) + 2 = … = T(n − k) + k. k = n − 1'de T(n) = T(1) + n − 1 = n: Θ(n). Alt problem n/b değil n − 1 olduğu için bağıntı Ana Teoremin biçimine uymaz. Tek çağrılı bir özyinelemenin girdisi her adımda bir azalırsa süre, her çağrının işinin n katıdır.

8. f4(10) kaç çağrı yapar ve ne döndürür? (Java'da n / 2 tamsayı bölmesidir.)

   Cevap

   f4(10) iki f4(5)'i, her f4(5) iki f4(2)'yi, her f4(2) iki f4(1)'i çağırır. Çağrılar 1 + 2 + 4 + 8 = 15'tir. Sekiz yaprak 1 döndürür; sonuç 8'dir. Ağaç, girdisi 8 olan ağaçla aynı biçimdedir.

9. Kapasitesi 1 olan ve dolunca iki katına büyüyen boş bir dinamik diziye 17 öğe ekleniyor. Toplam kaç kopya yapılır, toplam maliyet nedir, son kapasite kaçtır?

   Cevap

   Kapasite artırmaları 2., 3., 5., 9. ve 17. eklemelerde yapılır; kopyalar 1 + 2 + 4 + 8 + 16 = 31'dir. 17 yazma ile toplam 48 birimdir; 3 · 17 = 51'in altında kalır. Son kapasite 32'dir.

10. for (i = 0; i < n; i++) for (j = 1; j < n; j *= 2) x++; parçasının n = 10 için x++ sayısı ve büyüme sınıfı nedir?

    Cevap

    İç döngü dış sayaçtan bağımsızdır; j = 1, 2, 4, 8 değerlerinde 4 tur döner. Dış döngü 10 tur döner; toplam 10 · 4 = 40. Genel olarak n · ⌈log₂ n⌉, yani Θ(n log n).

1.2.12İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 3 ve 4: asimptotik gösterimin biçimsel tanımlarını, yerine koyma ve özyineleme ağacı yöntemlerini ve Ana Teoremin kanıtını verir; Akra–Bazzi yöntemine de değinir.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.4: çalışma süresini deneylerle ölçmeyi, ikiye katlama deneyini ve matematiksel modelleri Java örnekleriyle birleştirir.
• J. Kleinberg ve É. Tardos, Algorithm Design (2005), Bölüm 2 ve 5: verimlilik kavramını ve polinom zaman ölçütünü tartışır; böl ve fethet bağıntılarını özyineleme ağacıyla açık bir dille çözer.
• D. E. Knuth, “Big Omicron and Big Omega and Big Theta” (1976): O, Ω ve Θ gösterimlerinin tarihini ve bugünkü tanımlarının neden seçildiğini anlatan kısa bir makaledir.

1.2.13Kaynaklar

1. J. L. Bentley, D. Haken, J. B. Saxe, “A General Method for Solving Divide-and-Conquer Recurrences”, SIGACT News 12(3), 1980.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
3. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005.
4. D. E. Knuth, “Big Omicron and Big Omega and Big Theta”, SIGACT News 8(2), 1976.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

İlgili sayfalar: Bölüm 1.2 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.