Bölüm 2: Algoritma Analizi

2.1Algoritmalar ve ölçüm

Veri yapıları dersinin her konusunda aynı soru tekrar tekrar sorulur: bu işlem ne kadar sürer? Bir dizide arama, bir listeye ekleme, bir ağaçta silme… Her veri yapısı bazı işlemleri hızlı, bazılarını yavaş yapar. Hangi yapının hangi işte iyi olduğunu söyleyebilmek için önce “hızlı” ve “yavaş” sözcüklerine kesin bir anlam vermek gerekir. Algoritma analizi (algorithm analysis) bu işi yapar. Bu kesim, algoritma kavramıyla başlar ve bir algoritmanın maliyetini ölçmenin iki yolunu tanıtır: saatle ölçmek ve işlem saymak.

2.1.1Algoritma nedir?

Yemek tarifini düşünelim. Tarif, malzemeleri (girdiyi) alır, sıralı adımlarla işler ve sonunda bir yemek (çıktı) verir. Adımlar açık yazılmıştır: “suyu kaynat”, “pirinci ekle”, “on beş dakika pişir”. Tarifi izleyen herkes aynı yemeği elde eder. Tarif bir yerde biter; sonsuza kadar karıştırmaya devam etmez.

Bilgisayar bilimindeki algoritma (algorithm) aynı yapıdadır. Algoritma bir problemi çözmek için izlenen adım adım bir yöntemdir: girdi alınır, adımlar uygulanır, çıktı üretilir.

Şekil 2.1 bu tanımı bir sıralama algoritması üzerinde gösterir. Girdi sırasız dört sayıdır; çıktı aynı sayıların küçükten büyüğe dizilmiş hâlidir. Algoritmanın içinde ne olduğu, yani sayıları hangi sırayla karşılaştırıp yer değiştirdiği, algoritmadan algoritmaya değişir. Aynı girdiyi aynı çıktıya götüren pek çok yol vardır.

Analizin çıkış noktası da budur. Aynı problemi çözen farklı algoritmalar bulunabilir ve bunlardan bazıları ötekilerden çok daha verimli çalışır. Doğru algoritmayı seçmek önemlidir, çünkü iyi bir algoritma aynı işi daha az zaman ve daha az bellekle yapar. Küçük girdilerde fark hissedilmeyebilir. Girdi büyüdükçe ise bir algoritma saniyede biterken öteki günlerce sürebilir; bu farkın sayısal örnekleri Tablo 2.7'de verilir.

Algoritmalar çözdükleri problem türüne göre gruplanır. Tablo 2.1 ders boyunca sık karşılaşılacak üç grubu özetler.

Arama algoritmalarından ikisi, doğrusal ve ikili arama, bu notta ayrıntılı olarak incelenir (2.3.5–2.3.7). İkisi de aynı soruyu cevaplar: “Aranan değer dizide var mı, varsa hangi indiste?” Ama biri dizinin bütün öğelerine bakarken öteki yalnız birkaçına bakar. Bu fark, algoritma seçiminin neden önemli olduğunu en açık biçimde gösteren örneklerden biridir.

2.1.2İyi bir algoritmanın ölçütleri

İyi bir algoritma, problemi etkili biçimde çözen algoritmadır. “Etkili” sözcüğünü dört ölçüte ayırarak somutlaştırabiliriz. İlk ikisi maliyetle, son ikisi güvenilirlikle ilgilidir.

• Zaman karmaşıklığı (time complexity): Algoritmanın çalışma süresi ya da yaptığı işlem sayısı. Girdi büyüdükçe bu sürenin nasıl arttığı zaman karmaşıklığını belirler.
• Alan karmaşıklığı (space complexity): Algoritmanın kullandığı bellek miktarı. Bunun da girdi boyutuna göre nasıl arttığına bakılır (2.4.1).
• Doğruluk (correctness): Algoritma her geçerli girdi için doğru sonucu üretmelidir. Yanlış sonuç veren bir algoritma, ne kadar hızlı olursa olsun işe yaramaz (2.4.2).
• Sağlamlık (robustness): Algoritma beklenmeyen girdiler ve durumlarla da başa çıkabilmeli, çökmemeli ya da sessizce yanlış sonuç vermemelidir (2.4.4).

Bu ölçütler arasında bir sıra vardır. Doğruluk pazarlık konusu değildir: yanlış sonuç veren hızlı bir algoritma, doğru sonuç veren yavaş bir algoritmadan her zaman kötüdür. Doğru algoritmalar arasında seçim yapılırken zaman ve alan maliyeti devreye girer. İkisi bazen çatışır: daha fazla bellek kullanarak daha az zaman harcayan algoritmalar vardır. Önek ortalamaları örneğinde (2.3.12) bunun tersi görülür: hızlı çözüm aynı belleği kullanır, yalnız gereksiz işi atar.

Notun büyük kısmı zaman karmaşıklığına ayrılmıştır, çünkü veri yapısı seçiminde en sık belirleyici olan budur. Bellek için kullanılan gösterim ve yöntem aynıdır; zamanı ölçmeyi öğrenen, belleği de aynı araçlarla ölçebilir.

2.1.3Deneysel analiz: System.nanoTime()

Bir programın ne kadar sürdüğünü öğrenmenin en doğal yolu onu çalıştırıp süreyi ölçmektir. Bu yaklaşıma deneysel analiz (empirical analysis) denir. Java'da süre ölçmek için System.nanoTime() kullanılır. Bu metot bir sayı döndürür. İki çağrının döndürdüğü sayıların farkı, aradan geçen süreyi nanosaniye (ns, saniyenin milyarda biri) cinsinden verir.

Aşağıdaki kod, bir dizide tekrar eden öğe olup olmadığını denetleyen tekrarVar metodunun süresini farklı dizi boyutları için ölçer. tekrarVar, dizideki bütün öğe çiftlerini karşılaştıran bir metottur; kodu ve analizi 2.3.3'te verilir. Şimdilik yalnız şunu bilmek yeterlidir: dizide tekrar yoksa metot bütün çiftlere bakar ve ancak ondan sonra false döndürür.

for (int n = 1000; n <= 64000; n *= 2) {
  int[] a = new int[n];
  for (int i = 0; i < n; i++) a[i] = i; // tekrarsız
  long bas = System.nanoTime();
  tekrarVar(a);                        // ölçülen iş
  long sure = System.nanoTime() - bas;  // ns
  System.out.println(n + " " + sure / 1e6 + " ms");
}

Kod satır satır şöyle çalışır:

• Dış döngü n'yi 1000'den başlatır ve her turda ikiyle çarpar: 1000, 2000, 4000, …, 64000. Böylece yedi farklı boyut denenir.
• new int[n] ile n hücrelik bir dizi oluşturulur. İç döngü a[i] = i ile diziyi 0, 1, 2, … değerleriyle doldurur. Bütün değerler farklı olduğu için dizide tekrar yoktur.
• bas = System.nanoTime() ölçümden hemen önceki anı kaydeder. Ardından ölçülen iş, yani tekrarVar(a) çağrısı yapılır.
• System.nanoTime() - bas geçen süreyi nanosaniye olarak verir. Bu değer 10⁶'ya bölünerek milisaniyeye (ms) çevrilir ve n ile birlikte yazdırılır.

System.nanoTime()'ın döndürdüğü sayının kendi başına bir anlamı yoktur. Bu sayı günün saatini göstermez; yalnız iki okuma arasındaki fark anlamlıdır. Saatin “şu an 14.05” demesine benzeyen değer System.currentTimeMillis()'tir. Kısa süreleri ölçmek için nanoTime() daha uygundur, çünkü hem daha ince çözünürlüklüdür hem de bilgisayarın saati ayarlanınca kaymaz.

Ölçüm yaparken üç ilkeye uyulur:

1. Ölçmek. Ölçülecek işin hemen öncesinde ve hemen sonrasında System.nanoTime() okunur. Dizinin oluşturulması ve doldurulması ölçüme katılmaz; yalnız tekrarVar çağrısı ölçülür.
2. Tekrarlamak. Tek bir ölçüm güvenilir değildir. Java sanal makinesi (Java Virtual Machine, JVM) kodu ilk çalıştırmalarda yorumlar, sık çalışan kısımları ise sonradan makine koduna derler. Bu derlemeye anında derleme (just-in-time compilation, JIT) denir ve ilk ölçümleri yavaşlatır. Çöp toplayıcı ve bilgisayarda aynı anda çalışan öteki programlar da ölçüme gürültü katar. Bu yüzden her ölçüm birkaç kez yapılır ve ortanca (median) alınır. Ortanca, ölçümler küçükten büyüğe sıralandığında ortaya düşen değerdir; tek bir aşırı değerden etkilenmez.
3. Çizmek. Süre n'ye karşı bir grafiğe çizilir. Asıl bakılacak şey tek tek sürelerin büyüklüğü değil, n iki katına çıkınca sürenin kaç katına çıktığıdır. Bu oran bir sonraki altkesimin konusudur.

Yukarıdaki kodun bir dizüstü bilgisayarda bir kez çalıştırılmasıyla elde edilen değerler Tablo 2.2'de verilmiştir. Değerler makineden makineye, hatta aynı makinede çalıştırmadan çalıştırmaya değişir; burada yalnız ölçümün nasıl yorumlanacağını göstermek için kullanılıyor.

Tablonun ilk iki satırı tuhaftır: 1000 öğeli dizi, 2000 öğeli diziden yaklaşık dokuz kat uzun sürmüştür. Bunun nedeni algoritma değil, JIT'tir. İlk çağrıda tekrarVar henüz yorumlanarak çalışır; ikinci çağrıya gelindiğinde derlenmiş ve hızlanmıştır. İlk ölçüm bu yüzden “ısınma” ölçümüdür ve yorumda kullanılmaz. Sonraki satırlarda oran 3,1 ile 5,0 arasında dolaşır ve çoğunlukla 4'e yakındır. Son satırdaki 5,0, büyük dizinin işlemci önbelleğine sığmaması ya da o sırada başka bir programın çalışması gibi nedenlerle oluşan gürültüdür. Ölçümü tekrarlayıp ortancayı almak bu tür sapmaları büyük ölçüde giderir.

2.1.4Katlama deneyi

Ölçülen süreler tek başına az şey söyler. “64.000 öğeli dizide 727 ms” bilgisi başka bir bilgisayarda geçerli değildir. Daha kalıcı bir bilgi, sürenin girdiyle nasıl büyüdüğüdür. Bunu bulmanın pratik yolu katlama deneyidir (doubling experiment): girdi boyutu her adımda iki katına çıkarılır ve ardışık iki sürenin oranına bakılır.

Çalışma süresini T(n) ile gösterelim. Sürenin yaklaşık olarak T(n) ≈ c · n^k biçiminde olduğunu varsayalım. Burada c makineye bağlı bir sabit, k ise algoritmaya bağlı bir üstür. Girdi iki katına çıkınca:

T(2n) / T(n) ≈ c · (2n)^k / (c · n^k) = 2^k

Sabit c sadeleşir ve geriye yalnız 2^k kalır. Oran makineden bağımsızdır. Hızlı bir bilgisayarda c küçülür, ama oran değişmez. Oran 2 ise k = 1'dir: süre doğrusal büyür. Oran 4 ise k = 2'dir: süre karesel büyür. Oran 8 ise k = 3'tür: süre kübik büyür.

Şekil 2.2 dört büyüme biçimi için beklenen oranları gösterir. O(…) gösterimi 2.2.1'de tanımlanır; burada “süre yaklaşık bu fonksiyon gibi büyür” diye okunabilir. Dikkat çeken sütun n log n'dir. Logaritma çarpanı n iki katına çıkınca biraz büyür; bu yüzden oran 2'den az fazladır:

(2000 · log₂ 2000) / (1000 · log₂ 1000) = 2 · 10,966 / 9,966 ≈ 2,2

Bu küçük fark, katlama deneyinde n ile n log n'yi ayırmanın zor olduğunu da gösterir. Ölçüm gürültüsü 2,0 ile 2,2'yi kolayca karıştırabilir.

2.1.5Deneysel analizin sınırları

Deneysel analiz somuttur ve gerçek bir programın gerçek bir makinedeki davranışını gösterir. Yine de üç önemli sınırı vardır (Goodrich vd., Kesim 4.1):

• Sonuçlar ortama bağlıdır. Süre; işlemciye, belleğe, JVM sürümüne ve o anda çalışan öteki programlara bağlıdır. İki algoritmayı karşılaştırmak için ikisi aynı makinede, aynı koşullarda ölçülmelidir. Başka birinin makinesinde ölçülmüş bir süreyle kendi ölçümümüzü karşılaştırmak anlamsızdır.
• Yalnız denenen girdiler hakkında bilgi verir. Sınırlı sayıda girdi denenebilir. Algoritmayı yavaşlatan önemli bir girdi türü denemelerin dışında kalabilir. tekrarVar'ı yalnız sıfırlarla dolu dizilerle ölçen biri, metodun en kötü durumunu hiç görmez.
• Algoritmanın tamamen kodlanmasını gerektirir. Ölçmek için önce çalışan bir program gerekir. Oysa çoğu zaman karar, kod yazılmadan önce verilmelidir: on farklı yöntemi kodlayıp ölçtükten sonra birini seçmek pahalıdır.

Bu sınırları aşmanın yolu, süreyi ölçmek yerine algoritmanın attığı adımları saymaktır. Sayma yöntemi donanımdan bağımsızdır, bütün girdiler için geçerli bir sonuç verir ve kodu çalıştırmadan, hatta yalnız sözde koddan yapılabilir. Deneysel analiz bu yöntemin yerini tutmaz; ama onun sonucunu sınamak için iyi bir araçtır. Örnek 2.1, ölçümle saymanın aynı sonuca vardığı bir durumdu.

2.1.6İlkel işlemleri sayma: maksimum()

Saymaya başlamak için neyin sayılacağına karar vermek gerekir. Bir Java satırı makinede birkaç komuta dönüşebilir ve bu komutların süreleri işlemciden işlemciye değişir. Bu ayrıntılarla uğraşmamak için bir basitleştirme yapılır: bazı temel işlemlerin her birinin sabit sürede çalıştığı kabul edilir ve yalnız kaç kez çalıştıkları sayılır.

Bir algoritmanın ilkel işlem sayısı, onun çalışma süresiyle orantılıdır. Her ilkel işlem en çok bir sabit süre alıyorsa, toplam süre de en çok bu sabitle işlem sayısının çarpımıdır. Sabit makineden makineye değişir; işlem sayısı ise değişmez. Böylece makineden bağımsız bir ölçü elde edilir.

İlk örnek, bir dizinin en büyük öğesini bulan maksimum metodudur:

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

Metot, dizinin ilk öğesini geçici en büyük olarak alır. Sonra diziyi 1. indisten sona kadar tarar. Her öğeyi o ana kadarki en büyükle karşılaştırır; öğe daha büyükse enBuyuk'u günceller. Döngü bitince enBuyuk bütün dizinin en büyüğüdür.

Şimdi her ifadenin kaç kez çalıştığını sayalım. Dizinin uzunluğu n olsun. Satır numaraları, metot başlığı 1. satır olacak biçimde verilmiştir.

Sayıların gerekçesi şöyledir:

• Döngüden önceki atama (enBuyuk = a[0]) ve döngü değişkeninin ilk değeri (i = 1) birer kez çalışır.
• Döngü gövdesi i = 1, 2, …, n − 1 için çalışır; bu n − 1 turdur. Gövdedeki karşılaştırma ve tur sonundaki i++ bu yüzden n − 1'er kez çalışır.
• Döngü koşulu i < a.length, gövdeden bir kez fazla sınanır. n − 1 kez doğru çıkar ve gövde çalışır; son bir kez, i = n iken yanlış çıkar ve döngü biter. Toplam n sınama.
• Güncelleme satırı (enBuyuk = a[i]) yalnız karşılaştırma doğru çıkınca çalışır. Kaç kez çalışacağı dizinin içeriğine bağlıdır: hiç çalışmayabilir, en çok n − 1 kez çalışır.

Güncelleme sayısını g ile gösterirsek toplam işlem sayısı şudur:

1 + 1 + n + (n − 1) + g + (n − 1) + 1 = 3n + 1 + g,   0 ≤ g ≤ n − 1

Buradan iki uç durum çıkar. En iyi durumda a[0] dizinin en büyüğüdür ve hiçbir güncelleme yapılmaz: g = 0, toplam 3n + 1. En kötü durumda dizi artan sıralıdır; her yeni öğe öncekilerin hepsinden büyük olduğu için her turda güncelleme yapılır: g = n − 1, toplam 3n + 1 + n − 1 = 4n.

Analizin vardığı sonuç, sayıların kendisinden daha önemlidir. En iyi durumda da en kötü durumda da işlem sayısı n ile doğru orantılı büyür. n iki katına çıkınca işlem sayısı da yaklaşık iki katına çıkar. 3 ya da 4 katsayısı ve sondaki +1 gibi sabitler ise makineye göre zaten değişen ayrıntılardır. Bu yüzden atılırlar ve iki durum için de aynı sonuç yazılır: maksimum'un çalışma süresi Θ(n)'dir. Θ gösteriminin kesin anlamı 2.2.2'de verilir.

Bir noktaya dikkat etmek gerekir: hangi işlemlerin ayrı sayılacağı bir uzlaşmadır. Örneğin enBuyuk = a[i] satırı aslında iki iş yapar: dizi hücresini okur ve değeri atar. Bunu iki işlem saymak toplamı 3n + 1 yerine başka bir doğrusal ifadeye çevirir, ama büyüme hızı yine doğrusal kalır. Sabitlerin atılmasının bir nedeni de budur: sayım kuralları değişince değişen şey yalnız sabitlerdir.

2.1.7Kod izleme: maksimum(a)

Sayımı somut bir dizi üzerinde izleyelim. Girdi a = {3, 8, 2, 9, 4}, yani n = 5. Tablo 2.4 her adımda değişkenlerin durumunu verir.

İzlemenin ayrıntıları şunlardır. Başlangıçta enBuyuk = a[0] = 3'tür; ilk öğe geçici en büyüktür. 1. turda a[1] = 8, 3'ten büyüktür ve enBuyuk 8 olur. 2. turda a[2] = 2, 8'den küçüktür; değişiklik olmaz. 3. turda a[3] = 9 > 8 olduğu için yeni en büyük 9'dur. 4. turda a[4] = 4, 9'dan küçüktür. i 5 olunca koşul yanlış çıkar, döngü biter ve metot 9 döndürür.

Sayımı tabloyla doğrulayalım. Koşul 5 kez sınanmıştır (4 doğru, 1 yanlış), karşılaştırma 4 kez yapılmış, i++ 4 kez çalışmıştır. Güncelleme iki kez olmuştur (8 ve 9 için), yani g = 2. Toplam işlem sayısı 3 · 5 + 1 + 2 = 18'dir. Bu değer en iyi durum sınırı 16 ile en kötü durum sınırı 20 arasındadır.

Şekil 2.3'ün alt kısmındaki yeşil çizgi, algoritmanın doğruluğu hakkında da bir şey söyler. Her turun başında enBuyuk, o ana kadar işlenen kısmın en büyüğüdür. Döngü bitince işlenen kısım bütün dizi olduğu için sonuç doğrudur. Bu gözlem, 2.4.3'te döngü değişmezi adıyla bir ispata dönüşür.

2.2Asimptotik gösterim

maksimum için 3n + 1 ile 4n arasında bir işlem sayısı bulduk ve sonunda yalnız “n ile orantılı” sonucunu tuttuk. Bu ayıklama işi her analizde tekrarlanır. Onu düzenli ve kesin biçimde yapmanın aracı asimptotik (asymptotic) gösterimdir. “Asimptotik” sözcüğü, girdi boyutu çok büyüdüğünde ne olduğuna bakıldığını anlatır. Küçük girdilerdeki ayrıntılar bir yana bırakılır; büyük girdilerdeki büyüme hızı karşılaştırılır.

2.2.1Zaman karmaşıklığı ve büyük O

Zaman karmaşıklığı, bir algoritmanın ne kadar sürede çalıştığını girdi boyutu n'ye bağlı bir fonksiyonla ifade eder. Girdi boyutu probleme göre seçilir: dizide öğe sayısı, dizgede karakter sayısı, çizgede düğüm ve kenar sayısı. Bu fonksiyonun tam biçimini bilmek gerekmez; nasıl büyüdüğünü bilmek yeterlidir.

Büyük O (Big O) gösterimi, çalışma süresi için bir üst sınır verir. “Bu algoritma O(n)'dir” demek, çalışma süresinin büyük n için n'nin bir sabit katını aşmadığı anlamına gelir. Büyük O çoğunlukla en kötü durum için kullanılır, çünkü en kötü durumun üst sınırı bütün girdiler için bir garanti verir. Ama bu bir alışkanlıktır, tanımın parçası değildir (2.2.5).

İki sık görülen sınıfın anlamı şudur:

• O(1): İşlem sayısı girdi boyutuyla büyümez. Dizinin ilk öğesine erişmek, dizi bir milyon öğeli de olsa üç öğeli de olsa aynı sayıda adım sürer. O(1), farklı girdilerde sürenin birebir aynı olduğunu söylemez; yalnız n'den bağımsız bir sabitle sınırlandığını söyler.
• O(n): Girdi büyüdükçe süre doğrusal artar. n iki katına çıkınca süre de en çok yaklaşık iki katına çıkar. Diziyi baştan sona bir kez taramak bu sınıftadır.

Şekil 2.4 altı temel büyüme biçimini aynı eksen üzerinde gösterir. n yalnız 12'ye kadar çizildiği hâlde farklar açıktır. 2ⁿ eğrisi n = 6 civarında grafiğin üstünden çıkar; n² eğrisi n ≈ 7,7'de çıkar. n log n, n doğrusundan belirgin biçimde yukarıdadır. log n ise 12'de bile 3,6 civarındadır. Büyük girdilerde bu farkların ne kadar açıldığı Tablo 2.7'de sayılarla görülür.

Büyük O ile yazarken yalnız en hızlı büyüyen terim tutulur. Sabit çarpanlar ve daha yavaş büyüyen terimler atılır:

3n² + 5n + 2 → O(n²)  ·  4n + 100 → O(n)  ·  7 → O(1)

Neden atılabildiklerini ilk örnek üzerinde görelim. n = 10 için 3n² = 300, 5n = 50, sabit terim 2'dir; karesel terim toplamın %85'ini oluşturur. n = 1000 için 3n² = 3.000.000, 5n = 5000'dir; karesel terim toplamın %99,8'inden fazlasıdır. n büyüdükçe küçük terimlerin payı sıfıra yaklaşır. Sabit çarpan 3 ise makineye bağlıdır ve büyüme hızını değiştirmez: n iki katına çıkınca 3n² de n² de dört katına çıkar.

2.2.2O, Ω ve Θ'nın kesin tanımı

“Büyük n için bir sabit katını aşmaz” sözünü kesin bir tanıma çevirelim. Burada f(n) incelenen algoritmanın işlem sayısı, g(n) ise karşılaştırma için seçilen basit bir fonksiyondur (n, n², log n gibi).

Tanımın üç parçası da gereklidir. c sabiti, sabit çarpanların neden önemsiz olduğunu kesinleştirir: 3n ile n arasındaki fark, c = 3 seçilerek kapatılır. n₀ eşiği, küçük girdilerin neden önemsiz olduğunu kesinleştirir: eşitsizliğin yalnız bir noktadan sonra sağlanması yeter. “Her n ≥ n₀ için” ifadesi de sınırın tek tük noktalarda değil, eşikten sonra her yerde geçerli olmasını ister.

Üç tanımı tek bir fonksiyon üzerinde görelim: f(n) = 2n + 10.

Büyük O. Şekil 2.5 iki doğruyu gösterir. n = 0'da f 10'dan, 4n ise 0'dan başlar; 4n daha dik olduğu için bir noktada f'yi yakalar. Kesişme noktasını bulmak için 2n + 10 = 4n denklemini çözeriz: n = 5. n ≥ 5 için 2n + 10 ≤ 4n sağlanır. Böylece c = 4, n₀ = 5 ile f(n) = O(n) gösterilmiş olur. n < 5 için f daha büyüktür; örneğin n = 2'de f = 14, 4n = 8'dir. Tanım bu küçük değerlerle ilgilenmez.

Büyük Omega. Alt sınır için c = 2 seçmek yeterlidir. 2n + 10 ≥ 2n eşitsizliği, 10 pozitif olduğu için her n'de doğrudur (Şekil 2.6). Burada n₀ = 1 alınabilir; eşik gerekmez. f(n) = Ω(n) sonucu, f'nin n'den daha yavaş büyümediğini söyler.

Büyük Teta. İki sonucu birleştirince n ≥ 5 için 2n ≤ 2n + 10 ≤ 4n elde edilir (Şekil 2.7). f, eğimleri 2 ve 4 olan iki doğru arasına sıkışmıştır. Bu durumda f(n) = Θ(n) yazılır: f'nin büyüme hızı tam olarak n'dir.

Üç gösterim arasındaki fark, bir sınav notu benzetmesiyle kolayca anlaşılır. “Notum en çok 90” bir üst sınırdır (O); “notum en az 70” bir alt sınırdır (Ω). İkisi birlikte notu daraltır. Asimptotik dünyada “en çok” ve “en az” sabit çarpanlara kadar söylenir. Alt ve üst sınır aynı fonksiyonla verilebiliyorsa büyüme hızı kesin olarak bilinir (Θ).

Bir algoritma için hangisinin yazılacağı, ne bilindiğine bağlıdır. O en sık görülendir, ama tek başına gevşek olabilir. 2n + 10 = O(n²) ifadesi de doğrudur, çünkü n ≥ 5 için 2n + 10 ≤ n²'dir. Yine de yararsızdır; gerçek büyüme hızını gizler. Bu yüzden analizde mümkün olan en sıkı sınır verilir. Sıkı sınır biliniyorsa Θ yazmak en açık ifadedir.

2.2.3Tanımı kullanmak: c ve n₀ bulma

Bir ifadenin büyük O sınıfını göstermek için tanımdaki c ve n₀ değerlerini bulmak gerekir. Bunlar tek değildir; koşulu sağlayan herhangi bir çift yeter. İki yaygın yol vardır: her terimi en büyük terimle sınırlamak ya da eşitsizliği doğrudan çözmek.

Örnekteki birinci yol bütün polinomlara uygulanabilir. Katsayıları negatif olmayan d. dereceden bir polinomun her terimi n ≥ 1 için n^d'nin bir katıyla sınırlanır; katsayıların toplamı c olarak seçilir. Alt sınır için de en yüksek dereceli terimin katsayısı yeter. Bu gözlem aşağıdaki teoremde toplanır.

Teorem negatif katsayılı polinomlar için de geçerlidir (yalnız a_d > 0 olsun), ama o durumda n₀ daha dikkatli seçilir. Örneğin n(n − 1)/2 = n²/2 − n/2 ifadesi Θ(n²)'dir: n ≥ 2 için n/2 ≤ n²/4 olduğundan n²/4 ≤ n(n − 1)/2 ≤ n²/2 sağlanır. Bu ifade, tekrarVar analizinde yeniden karşımıza çıkar.

2.2.4Hesap kuralları

Her analizde tanıma dönüp c ve n₀ aramak yorucu olur. Tanımdan çıkan birkaç kural, işin çoğunu kısaltır:

• Sabit çarpanlar atılır. k > 0 bir sabitse k · f(n), f(n) ile aynı sınıftadır. 5n de n/2 de Θ(n)'dir.
• Toplamda en büyük terim kalır. f₁ = O(g₁) ve f₂ = O(g₂) ise f₁ + f₂ = O(max(g₁, g₂)). Ardışık iki kod bloğunun maliyeti bu kuralla birleşir: O(n) + O(n²) = O(n²).
• Çarpımda sınırlar çarpılır. f₁ = O(g₁) ve f₂ = O(g₂) ise f₁ · f₂ = O(g₁ · g₂). İç içe döngülerin maliyeti bu kuralla bulunur: dış döngü n tur, iç döngü her turda log n tur dönüyorsa toplam O(n log n)'dir.
• Logaritmanın tabanı önemsizdir. log_a n = log_b n / log_b a olduğundan farklı tabanlı iki logaritma arasında yalnız sabit bir çarpan vardır. Örneğin log₂ n = log₁₀ n / log₁₀ 2 ≈ 3,32 · log₁₀ n. Bu yüzden taban yazılmaz ve yalnız O(log n) denir.
• Geçişlilik. f = O(g) ve g = O(h) ise f = O(h)'dir. Aynısı Ω ve Θ için de geçerlidir.

Logaritma kuralı ilk bakışta şaşırtıcı gelebilir. n = 1.000.000 için log₂ n ≈ 19,9, log₁₀ n = 6'dır; sayılar farklıdır. Ama oran her n için aynıdır (yaklaşık 3,32). n bin katına çıktığında ikisi de aynı oranda artmaz, aynı miktarda artar: log₂ yaklaşık 10, log₁₀ tam 3 artar. Sabit çarpan farkı, büyüme sınıfını değiştirmez.

Üstel fonksiyonlarda durum farklıdır. Tabanı değiştirmek bir sabit çarpan değil, büyüme hızında gerçek bir fark yaratır: 3ⁿ / 2ⁿ = 1,5ⁿ oranı sınırsız büyür. Bu yüzden 3ⁿ, O(2ⁿ) değildir. Üste eklenen bir sabit ise yalnız sabit çarpan getirir: 2ⁿ⁺³ = 8 · 2ⁿ = Θ(2ⁿ).

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

maksimum örneğinde aynı n için farklı girdilerin farklı sayıda işlem gerektirdiğini gördük: azalan bir dizide 3n + 1, artan bir dizide 4n. Bu farklılık çoğu algoritmada çok daha büyüktür. Bu yüzden “algoritmanın çalışma süresi” derken hangi girdiden söz ettiğimizi de söylememiz gerekir. Üç bakış açısı vardır.

Tablo 2.5, üç asimptotik sınırı ve üç durumu bir arada özetler. Tablonun üst kısmı “ne tür bir sınır?”, alt kısmı “hangi girdi için?” sorusunu cevaplar. İki soru birbirinden bağımsızdır.

Doğrusal arama, dizinin öğelerine baştan başlayarak tek tek bakar ve aranan değeri bulunca durur (kodu 2.3.5'te). Küçük bir örnekle üç durumu hesaplayalım. Dizi [4, 8, 15, 16, 23, 42], yani n = 6.

Üç durumdan hangisinin raporlanacağı amaca bağlıdır:

• En kötü durum bir garanti verir. “Bu işlem hiçbir girdide 4n adımı geçmez” demek, sistemi tasarlayan kişiye güvenilir bir bilgi verir. Hesaplaması da genellikle kolaydır. Bu yüzden en sık raporlanan budur.
• Ortalama durum pratikte ne beklendiğini anlatır, ama bir olasılık dağılımı varsayar. Varsayım gerçeğe uymazsa sonuç yanıltıcı olur. Hesaplaması da çoğu zaman en kötü durumdan zordur.
• En iyi durum tek başına yanıltıcıdır. Hemen her arama algoritması, hedefin ilk bakılan yerde olduğu şanslı bir girdide hızlıdır. Bu bilgi algoritmanın genel davranışı hakkında hemen hiçbir şey söylemez.

2.2.6Amortize analiz

Bazı veri yapılarında işlemlerin çoğu ucuzdur, ama arada bir pahalı bir işlem gelir. Bu durumda en kötü durum analizi gereğinden kötümser bir tablo çizer. Amortize analiz (amortized analysis), tek bir işlemin değil, uzun bir işlem dizisinin toplam maliyetine bakar ve bu toplamı işlem sayısına böler.

Standart örnek, dolunca büyüyen dizidir. Java'daki ArrayList öğelerini bir dizide tutar. Sona ekleme çoğu zaman tek adımdır: boş hücreye yazılır. Dizi dolunca ise iki kat büyük yeni bir dizi ayrılır ve bütün öğeler oraya kopyalanır. Bu tek ekleme O(n) sürer.

Amortize analiz ortalama durum analizinden farklıdır. Ortalama durum bir olasılık varsayımı yapar ve beklenen maliyeti hesaplar. Amortize analizde olasılık yoktur: her işlem dizisi için, en kötüsü dahil, toplam maliyet 3n'den azdır. Bu yine bir garantidir; yalnız tek işlem için değil, işlem dizisi için verilir.

2.2.7Büyük O sınıfları

Algoritma analizinde sonuçlar çoğunlukla birkaç standart sınıftan birine düşer. Tablo 2.6 bu sınıfları yavaştan hızlıya doğru büyüme sırasıyla verir.

Her sınıfın arkasında bir sezgi yatar. O(log n) algoritmalar problemi her adımda sabit bir oranda küçültür; n milyon olsa bile 20 civarında adımda biter. O(n) algoritmalar her öğeye sabit sayıda bakar; girdiyi okumak bile n adım sürdüğü için pek çok problemde bundan iyisi mümkün değildir. O(n log n), iyi sıralama algoritmalarının sınıfıdır. O(n²), “her öğeyi her öğeyle karşılaştır” yaklaşımının doğal sonucudur. O(2ⁿ) ise bütün olasılıkları tek tek denemenin bedelidir; n'ye bir eklemek süreyi ikiye katlar.

Birleştirme sıralamasındaki “log n düzey” ifadesi biraz açıklama ister. Bu algoritma diziyi ikiye böler, iki yarıyı ayrı ayrı sıralar ve sonra birleştirir. Yarılar da aynı biçimde bölünür. n öğeli dizi, tek öğeli parçalara inene kadar log₂ n kez ikiye bölünebilir. Her düzeydeki birleştirmeler toplam n öğeye dokunur. log n düzey çarpı n iş, n log n eder.

2.2.8n büyüdükçe ne olur?

Sınıflar arasındaki farkın ne kadar büyük olduğunu en iyi sayılar anlatır. Tablo 2.7 her fonksiyonun üç farklı n değerindeki değerini verir.

Tablo sütun sütun okunduğunda iki şey dikkat çeker. Birincisi, log₂ n neredeyse hiç büyümez: n yüz kat artınca yalnız 3,3'ten 10'a çıkar. İkincisi, 2ⁿ n = 10'da henüz makul görünür (1.024), ama n = 100'de 31 basamaklı bir sayıdır.

Bu örnek, daha hızlı donanımın neden üstel bir algoritmayı kurtaramayacağını da gösterir. Bilgisayar bin kat hızlansa bile süre ancak 4 · 10¹⁰ yıla iner. Hızlanmanın kazandırdığı şey çok küçüktür: bin kat hız, 2ⁿ algoritmada aynı sürede çözülebilecek n'yi yalnız 10 artırır (2¹⁰ ≈ 1000). Karesel bir algoritmada ise aynı hızlanma, çözülebilecek n'yi yaklaşık 32 katına çıkarır (√1000 ≈ 31,6). Büyük girdilerde algoritma seçimi, donanım seçiminden çok daha etkilidir.

2.3Koddan karmaşıklığa

Asimptotik gösterim elimizdeyken asıl işe geçebiliriz: bir kod parçasına bakıp karmaşıklığını söylemek. Çoğu zaman her ilkel işlemi tek tek saymak gerekmez. Kodun maliyetini belirleyen, döngülerin kaç kez döndüğüdür. Döngüsüz bir kod parçası sabit sayıda işlem yapar ve O(1)'dir. Döngülerin yapısı ise birkaç kalıba ayrılır. Bu kesim önce bu kalıpları tanıtır, sonra onları gerçek metotlar üzerinde uygular: toplam, doğrusal ve ikili arama, tekrar denetimi ve önek ortalamaları.

2.3.1Döngü kalıpları

Bir döngünün maliyeti, gövdenin kaç kez çalıştığıyla gövdenin bir kez çalışmasının maliyetinin çarpımıdır. Gövde sabit sayıda işlem yapıyorsa döngünün maliyeti tur sayısıyla orantılıdır. Tablo 2.8 en sık görülen kalıpları, n = 16 için tur sayısını ve sınıfı verir.

Kalıpları tek tek açıklayalım.

Basit döngü. i 0'dan başlar, her turda 1 artar ve n'ye ulaşınca durur. i 0, 1, …, n − 1 değerlerini alır; bu n turdur.

Adımı 2 olan döngü. i 0, 2, 4, … değerlerini alır. n çiftse tur sayısı tam n/2'dir; tekse ⌈n/2⌉'dir. Adım 2 olsa da 100 olsa da tur sayısı n'nin sabit bir kesridir ve döngü O(n)'dir. Adımı büyütmek döngüyü hızlandırır, ama sınıfını değiştirmez.

Katlanan döngü. i her turda iki katına çıkar: 1, 2, 4, 8, … Gövde, i n'ye ulaşmadığı sürece çalışır. k tur sonra i = 2^k olur. Döngü 2^k ≥ n olduğu ilk anda durur, yani k = ⌈log₂ n⌉'de. n = 16 için i 1, 2, 4, 8 değerlerini alır; 16'da durur: 4 tur. Bu kalıbın ayrıntılı izlemesi 2.3.2'de verilir. Aynı sonuç, i'nin n'den başlayıp her turda yarıya indiği döngü için de geçerlidir.

İç içe döngüler. Dış döngünün her turunda iç döngü baştan sona çalışır. İç döngü dıştan bağımsız olarak n tur dönüyorsa toplam n · n = n² turdur. İç döngünün sınırı dış değişkene bağlıysa (j < i) çarpım yerine toplam yazılır: i = 0'da iç döngü 0 kez, i = 1'de 1 kez, …, i = n − 1'de n − 1 kez döner. Toplam:

0 + 1 + 2 + … + (n − 1) = n(n − 1)/2

Bu toplam formülü sık kullanılır ve kolay hatırlanan bir gerekçesi vardır. Toplamı bir kez baştan, bir kez sondan yazıp alt alta toplayalım: 0 + (n − 1), 1 + (n − 2), … Her çift n − 1 eder ve n çift vardır. İki toplamın toplamı n(n − 1) olduğu için tek toplam bunun yarısıdır. n = 16 için 16 · 15 / 2 = 120. İç döngü ortalamada dış döngünün yarısı kadar dönse de sonuç yine O(n²)'dir; 1/2 katsayısı atılır.

Ardışık döngüler. Biri bittikten sonra öteki başlayan iki döngünün maliyetleri toplanır: n + n = 2n, yani O(n). Ardışık döngüler iç içe döngülerden çok daha ucuzdur.

Bu gözlemlerden iki genel kural çıkar:

• Ardışık bloklarda maliyetler toplanır ve en büyüğü kalır: O(n) + O(n²) = O(n²). Bir metotta önce doğrusal bir tarama, sonra iç içe bir döngü varsa metodun maliyetini iç içe döngü belirler.
• İç içe döngülerde maliyetler çarpılır: dış döngünün tur sayısı × iç döngünün tur sayısı. İç döngünün tur sayısı dış değişkene bağlıysa çarpım yerine bütün turların toplamı alınır.

2.3.2Kod izleme: adimSay(16)

Katlanan döngüyü bir metot içinde izleyelim. adimSay, 1'den başlayıp ikiye katlayarak n'ye kaç adımda ulaşıldığını sayar:

int adimSay(int n) {
  int k = 0;
  for (int i = 1; i < n; i *= 2)
    k++;
  return k;
}

Metot bir sayaç k'yi 0'la başlatır. Döngü değişkeni i 1'den başlar ve her turda i *= 2 ile iki katına çıkar. Her tur sayacı bir artırır. Döngü bitince sayaç, döngünün kaç tur döndüğünü verir.

Şekil 2.9 katlanan döngünün neden bu kadar az tur döndüğünü görsel olarak anlatır. Her atlama bir öncekinin iki katı uzunluktadır: 1, 2, 4, 8. Dört atlamada 1'den 16'ya varılır. Döngü n sayısının bütün değerlerine tek tek uğramaz; aradaki sayıların çoğunu atlar.

Metodun döndürdüğü 4, log₂ 16'ya eşittir. Genel olarak adimSay(n), ⌈log₂ n⌉ döndürür. Bu fonksiyonun ne kadar yavaş büyüdüğünü birkaç değerle görelim: adimSay(17) = 5, adimSay(1000) = 10, adimSay(16000) = 14. n'yi 1000 kat büyütmek tur sayısına yalnız 10 civarında tur ekler, çünkü 2¹⁰ = 1024 ≈ 1000'dir. Metot O(log n)'dir.

2.3.3Üç metot, üç sınıf

Kalıpları üç kısa metot üzerinde uygulayalım. Üçü de bir int dizisi alır; aralarındaki fark yalnız döngü yapısıdır.

O(1): ilk öğe.

int ilk(int[] a) {
    return a[0];
}

Metotta döngü yoktur. Bir dizi erişimi ve bir dönüş yapılır. Dizi indisle erişimde bellekteki adres doğrudan hesaplanır: başlangıç adresine indis çarpı öğe boyutu eklenir. Dizinin uzunluğu bu hesabı etkilemez. İşlem sayısı sabittir; metot O(1)'dir.

O(n): toplam.

int toplam(int[] a) {
    int s = 0;
    for (int x : a)  // n kez
        s += x;
    return s;
}

for (int x : a) biçimi, genişletilmiş for döngüsüdür (for-each): x sırasıyla dizinin her öğesini alır. Gövde her öğe için bir kez, toplam n kez çalışır. Gövdede yalnız bir toplama ve bir atama vardır. Döngü dışındaki atama ve dönüş sabit işlemlerdir. Toplam işlem sayısı n ile doğru orantılıdır; metot O(n)'dir.

O(n²): tekrar denetimi.

boolean tekrarVar(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j])
                return true;
    return false;
}
// dış döngü n, iç döngü ≈ n/2
// → n(n−1)/2 karşılaştırma

Metot dizide birbirine eşit iki öğe olup olmadığını denetler. Dış döngü her i indisi için iç döngüyü çalıştırır. İç döngü j'yi i + 1'den başlatır ve a[i]'yi sağındaki her öğeyle karşılaştırır. j'nin i + 1'den başlaması iki şeyi sağlar: bir öğe kendisiyle karşılaştırılmaz ve her çift yalnız bir kez karşılaştırılır (a[0] ile a[3] karşılaştırıldıysa a[3] ile a[0] ayrıca karşılaştırılmaz). Eşit bir çift bulunduğu anda metot true döndürür. Döngüler hiçbir eşitlik bulmadan biterse sonuç false'tur.

Karşılaştırma sayısını en kötü durum için, yani dizide hiç tekrar olmadığında sayalım. i = 0 iken iç döngü n − 1 kez, i = 1 iken n − 2 kez, …, i = n − 2 iken 1 kez, i = n − 1 iken hiç dönmez:

(n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2 = n²/2 − n/2

Sabitler ve küçük terim atılınca sonuç O(n²)'dir. İç döngü ortalamada yaklaşık n/2 tur döner; ama dış döngünün n turuyla çarpılınca yine karesel bir toplam çıkar. Bu sayı, aynı zamanda n öğeden seçilebilecek farklı çiftlerin sayısıdır. Bütün çiftlere bakan her algoritma en az bu kadar karşılaştırma yapar.

En iyi durum ise ilk karşılaştırmada eşitlik bulunan girdidir: a[0] == a[1] ise metot tek karşılaştırmayla döner, Θ(1). 2.1.3'teki sıfırlarla dolu dizi tam olarak bu durumdu.

2.3.4Kod izleme: toplam()

toplam metodunu, onu çağıran kodla birlikte izleyelim. İzleme, metot çağrısının nasıl yürüdüğünü de gösterir.

int toplam(int[] a) {
    int s = 0;
    for (int x : a) {
        s += x;
    }
    return s;
}

// main içinde:
System.out.println(toplam(a));

main içinde a = {7, 2, 9} olsun. toplam(a) çağrıldığında yeni bir çağrı çerçevesi (stack frame) açılır. Çerçeve, metodun parametrelerini ve yerel değişkenlerini (s, x) tutar. Parametre a, main'deki diziyle aynı diziyi gösterir; dizi kopyalanmaz. Java'da dizi değişkeni bir referanstır (reference): dizinin kendisini değil, bellekteki yerini tutar. Metoda geçirilen de bu yerdir. Bu yüzden çağrının maliyeti dizinin boyutuna bağlı değildir.

Döngü gövdesi n = 3 kez çalışmıştır. Gövdenin dışında kalan işler, yani çerçeveyi açma, s'yi başlatma, dönüş ve yazdırma, dizinin boyutundan bağımsızdır. Dizi 3 değil 3 milyon öğeli olsaydı yalnız gövdenin tur sayısı değişirdi. Toplam süre c₁ · n + c₂ biçimindedir: O(n).

2.3.5Doğrusal arama

Doğrusal arama (linear search), bir değeri dizide bulmanın en basit yoludur: dizinin başından başlanır ve öğelere sırayla bakılır.

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

Döngü i'yi 0'dan dizinin sonuna kadar ilerletir. Her turda a[i] hedefle karşılaştırılır. Eşitse metot o anda i'yi döndürür ve döngünün geri kalanı çalışmaz. Döngü bir eşitlik bulmadan biterse hedef dizide yoktur ve metot -1 döndürür. -1 geçerli bir indis olmadığı için “bulunamadı” anlamında kullanılır.

Metodu sıralı bir dizi üzerinde izleyelim: a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} (n = 10), hedef 23.

Hedef 6 karşılaştırmada bulunmuştur. Dizinin sıralı olduğuna dikkat edelim: doğrusal arama bu bilgiyi hiç kullanmaz. 2'nin 23'ten küçük olduğunu görmek, ötekiler hakkında bir şey öğretmez; her adımda yalnız bir öğe elenir (Şekil 2.10). Hedef son öğe olsaydı ya da dizide hiç olmasaydı (örneğin 40 aransaydı) on öğenin hepsine bakılırdı: 10 karşılaştırma.

Analiz Örnek 2.3'teki sonuçların aynısını verir. En iyi durum, hedefin ilk öğe olmasıdır: 1 karşılaştırma, Θ(1). En kötü durum, hedefin sonda olması ya da hiç olmamasıdır: n karşılaştırma, Θ(n). Ortalama durum da konumlar eşit olasılıklıysa (n + 1)/2 karşılaştırmadır, yine Θ(n). Metot yalnız birkaç değişken kullanır; ek alanı O(1)'dir.

Doğrusal aramanın iyi bir yanı da vardır: dizinin sıralı olmasını gerektirmez. Sırasız bir dizide bir değeri bulmanın daha hızlı bir yolu yoktur. Hiçbir öğeye bakmadan onun hedef olmadığını bilemeyiz; en kötü durumda her öğeye bakmak zorunludur.

2.3.6İkili arama

Dizi sıralıysa çok daha iyisi yapılabilir. Telefon rehberinde bir isim ararken ilk sayfadan başlayıp tek tek bakmayız. Rehberi ortadan açarız; aradığımız isim alfabede daha önceyse sağ yarıyı, daha sonraysa sol yarıyı bir kenara bırakırız. Kalan yarıda aynı işi tekrarlarız. İkili arama (binary search) bu yöntemin algoritma hâlidir.

int ikiliArama(int[] a, int hedef) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == hedef) return mid;
        if (a[mid] < hedef) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Kod satır satır şöyle çalışır:

• lo ve hi, hedefin bulunabileceği aralığın sol ve sağ uçlarıdır. Başlangıçta aralık bütün dizidir: lo = 0, hi = a.length - 1.
• while (lo <= hi): aralıkta en az bir öğe kaldığı sürece arama sürer. lo > hi olunca aralık boşalmıştır.
• mid = (lo + hi) / 2 aralığın ortasındaki indistir. Java'da iki int'in bölümü tamsayıdır; kesirli kısım atılır. Örneğin (0 + 9)/2 = 4.
• a[mid] == hedef ise hedef bulunmuştur ve mid döndürülür.
• a[mid] < hedef ise hedef ortadakinden büyüktür. Dizi sıralı olduğu için hedef ancak mid'in sağında olabilir: lo = mid + 1. Sol yarı, ortadaki öğeyle birlikte elenir.
• Aksi hâlde a[mid] > hedef'tir ve hedef ancak solda olabilir: hi = mid - 1.
• Döngü hedefi bulmadan biterse -1 döndürülür.

Algoritmanın gücü, tek bir karşılaştırmanın aralığın yarısını elemesinden gelir. Doğrusal aramada a[i] ≠ hedef bilgisi yalnız bir öğeyi eler. İkili aramada ise a[mid] < hedef bilgisi, dizinin sıralı olması sayesinde mid'in solundaki her öğenin de hedeften küçük olduğunu söyler.

Aynı diziyi ve aynı hedefi kullanalım: a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, hedef 23.

İzlemenin ayrıntıları şunlardır. 1. turda aralık bütün dizidir ve mid = (0 + 9)/2 = 4 olur. a[4] = 16, 23'ten küçüktür; hedef sağ yarıdadır ve lo = 5 yapılır. Beş öğe tek karşılaştırmayla elenmiştir. 2. turda mid = (5 + 9)/2 = 7, a[7] = 56'dır. 56 hedeften büyük olduğu için hi = 6 yapılır. 3. turda mid = (5 + 6)/2 = 5 ve a[5] = 23: hedef bulunmuştur.

İkili arama 3 turda bitmiştir; doğrusal arama aynı hedef için 6 karşılaştırma yapmıştı. Her turda aralık yarıya iner: 10 öğe, 5 öğe, 2 öğe. Fark bu küçük dizide iki kattır; büyük dizilerde çarpıcı hâle gelir.

2.3.7İkili aramada en kötü durum

İkili aramanın en kötü durumu, hedefin dizide olmadığı ve aralığın tek öğeye kadar daraldığı durumdur. Aynı dizide 40'ı arayalım. 40, 38 ile 56 arasında kalan ve dizide bulunmayan bir değerdir.

İlk iki tur, 23 aramasıyla aynıdır. 3. turda a[5] = 23 hedeften küçük çıkar ve lo = 6 olur. Aralık artık tek öğedir: 6. indisteki 38. 4. turda mid = 6, 38 de hedeften küçüktür ve lo = 7 yapılır. Bu noktada lo = 7 > hi = 6'dır (Şekil 2.12). Döngü koşulu yanlış çıkar ve metot -1 döndürür.

Son durum ilginç bir bilgi de taşır. Döngü bittiğinde lo, hedefin dizide olsaydı yerleşeceği indistir: 40, 38'in (6. indis) ve 56'nın (7. indis) arasına, yani 7. indise girerdi. Sıralı diziye ekleme yapan bazı algoritmalar ikili aramanın bu özelliğini kullanır.

En kötü durumda bile yalnız 4 tur yapılmıştır; doğrusal arama aynı hedef için 10 karşılaştırma yapardı. Bu sayının nereden geldiğini aşağıdaki teorem açıklar.

Gerekçe şöyledir. Aralıktaki öğe sayısına m diyelim. Bir tur sonunda hedef bulunmamışsa yeni aralık, mid'in solundaki ya da sağındaki kısımdır. Ortadaki öğe de elendiği için yeni aralıkta en çok ⌊m/2⌋ öğe kalır. Başlangıçta m = n'dir. Her tur öğe sayısını en az yarıya indirdiği için k turdan sonra en çok ⌊n/2^k⌋ öğe kalır. Bu sayı 2^k > n olduğunda 0'a iner, yani k = ⌊log₂ n⌋ + 1 turdan sonra aralık kesinlikle boştur.

Örnekte n = 10 için ⌊log₂ 10⌋ + 1 = 3 + 1 = 4'tür. Öğe sayıları 10 → 5 → 2 → 1 → 0 diye azalmıştır. Tablo 2.14 farklı dizi boyutları için en kötü durum tur sayısını, doğrusal aramanın en kötü durumuyla karşılaştırır.

Bir milyon öğeli sıralı dizide ikili arama en çok 20 tur döner. Doğrusal arama aynı dizide bir milyon karşılaştırma yapabilir. Fark elli bin kattır ve n büyüdükçe daha da açılır. Bedeli, dizinin sıralı tutulmasıdır. Dizi bir kez sıralanıp çok kez aranacaksa bu bedel kolayca karşılanır.

2.3.8Kod izleme: tekrarVar()

2.3.3'teki tekrarVar metodunu küçük bir dizide izleyelim: a = {4, 7, 1, 7}. Dizide 7 iki kez geçer.

boolean tekrarVar(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j])
                return true;
    return false;
}

Dış döngü i = 0 iken iç döngü a[0] = 4'ü sağındaki üç öğeyle karşılaştırır; hiçbiri 4 değildir. i = 1'de iç döngü j = 2'den başlar. a[1] = 7 önce 1 ile, sonra a[3] = 7 ile karşılaştırılır. Eşitlik bulunur ve metot beşinci karşılaştırmada true döndürür. i = 2 turu hiç çalışmaz.

Dizide tekrar olmasaydı, örneğin {4, 7, 1, 9} verilseydi, bütün çiftler karşılaştırılırdı: n(n − 1)/2 = 4 · 3 / 2 = 6 karşılaştırma. Bu en kötü durumdur ve O(n²)'dir. Tablo 2.2'deki ölçümde sürenin her katlamada yaklaşık 4 katına çıkması bu karesel büyümenin sonucudur.

Aynı problem daha hızlı çözülebilir mi? Evet. Dizi önce sıralanırsa eşit öğeler yan yana gelir ve yalnız komşu öğeleri karşılaştırmak yeterli olur. Sıralama O(n log n), komşu taraması O(n) sürer; toplam O(n log n)'dir. Bir sonraki örnek, gereksiz işi atarak karesel bir algoritmayı doğrusala indirmenin başka bir yolunu gösterir.

2.3.9Önek ortalamaları problemi

Aynı problemi çözen iki algoritmanın maliyetleri ne kadar farklı olabilir? Bu soruyu somut bir problem üzerinde yanıtlayalım (Goodrich vd., Kesim 4.3).

Bir dizinin “öneki”, baştan başlayan bir parçasıdır: x[0..j]. Problem her önekin ortalamasını ister. Bu hesap gerçek hayatta sık kullanılır. Bir hisse senedinin yılbaşından bu yana günlük ortalama fiyatı ya da bir öğrencinin dönem başından bu yana not ortalaması birer önek ortalamasıdır. Hareketli ortalama ve finansal eğilim analizi de benzer hesaplara dayanır.

Hesaba dikkatle bakınca bir tekrar göze çarpar: a[2]'nin payı olan 18, a[1]'in payı 12'ye x[2] = 6 eklenerek bulunabilirdi. Problemin iki çözümü bu gözlemden ayrılır. Birinci çözüm her j için toplamı baştan hesaplar ve O(n²) sürer. İkinci çözüm toplamı turdan tura taşır ve O(n) sürer.

2.3.10onekOrt1: her j için baştan toplama

double[] onekOrt1(double[] x) {
  int n = x.length;
  double[] a = new double[n];
  for (int j = 0; j < n; j++) {
    double top = 0;
    for (int i = 0; i <= j; i++)
      top += x[i];
    a[j] = top / (j + 1);
  }
  return a;
}

Kod satır satır şöyle çalışır:

• n girdinin uzunluğudur. a = new double[n] sonuç dizisini ayırır; Java bu diziyi 0.0 değerleriyle doldurur.
• Dış döngü her j için bir önek ortalaması hesaplar.
• double top = 0 satırı dış döngünün içindedir. Toplam her j için sıfırdan başlar.
• İç döngü i'yi 0'dan j'ye kadar (dahil) ilerletir ve x[i]'leri top'a ekler. Koşul i <= j'dir; < yazılsaydı x[j] toplama girmezdi.
• a[j] = top / (j + 1) ortalamayı yazar. top bir double olduğu için bölme kesirli yapılır.

Tablo 2.16, x = [4, 8, 6, 2] için iç döngünün her turunu gösterir.

Tablonun üçüncü sütunu algoritmanın zayıf noktasını açıkça gösterir. x[0] = 4 dört kez, x[1] = 8 üç kez, x[2] = 6 iki kez toplanmıştır. Her j turu, bir önceki turun bulduğu toplamı unutur ve aynı toplamaları yeniden yapar.

Toplama sayısını genel olarak sayalım. j turunda iç döngü j + 1 kez döner. Bütün turların toplamı:

1 + 2 + … + n = n(n + 1)/2

n = 4 için 4 · 5 / 2 = 10 toplama yapılır; tablodaki 1 + 2 + 3 + 4 ile aynıdır. Bu ifade n²/2 + n/2'dir ve Teorem 2.1'e göre Θ(n²)'dir. Algoritmanın ek alanı, sonuç dizisi a için O(n)'dir.

2.3.11onekOrt2: birikimli toplam

Gereksiz işi atmak için toplamı turdan tura taşımak yeterlidir. j. önekin toplamı, j − 1. önekin toplamına x[j] eklenerek bulunur:

double[] onekOrt2(double[] x) {
  int n = x.length;
  double[] a = new double[n];
  double top = 0;
  for (int j = 0; j < n; j++) {
    top += x[j];
    a[j] = top / (j + 1);
  }
  return a;
}

İki kod arasındaki fark küçüktür ama belirleyicidir. double top = 0 satırı döngünün dışına alınmıştır; toplam bir kez sıfırlanır ve turlar boyunca korunur. İç döngü kaldırılmış, yerine tek bir top += x[j] satırı gelmiştir. Her turun başında top, x[0..j−1]'in toplamını tutar; x[j] eklenince x[0..j]'nin toplamı olur.

Sonuç [4.0, 6.0, 6.0, 5.0]'dır; onekOrt1 ile aynıdır. Toplama sayısı ise 10 yerine 4'tür. Genel olarak döngü n tur döner ve her turda sabit sayıda işlem yapar: bir toplama, bir bölme, bir atama. onekOrt2, Θ(n) zamanda çalışır. Ek alanı yine sonuç dizisi için O(n)'dir.

2.3.12İki çözümün karşılaştırması

İki algoritmanın toplama sayılarını farklı n değerleri için yan yana koyalım.

n = 10'da fark 5,5 kattır ve önemsiz görünebilir. n = 10⁶'da ise onekOrt1 yaklaşık 5 · 10¹¹ toplama yapar, onekOrt2 yalnız 10⁶. Saniyede 10⁹ toplama yapan bir makinede birincisi yaklaşık 500 saniye (8 dakikadan fazla), ikincisi 1 milisaniye sürer. Oran, (n + 1)/2 olduğu için n ile birlikte büyür.

Farkın kaynağı tekrarlanan işin ortadan kaldırılmasıdır. onekOrt2 önceki toplamı hatırlar; onekOrt1 unutur ve yeniden hesaplar. Bu fikir yalnız bu probleme özgü değildir. Bir hesabın sonucunu saklayıp sonraki hesaplarda kullanmak, pek çok verimli algoritmanın temelidir. Bir algoritmayı hızlandırmanın ilk adımı çoğu zaman şu soruyu sormaktır: “Aynı işi birden fazla kez yapıyor muyum?”

İki algoritmanın alan maliyeti aynıdır: ikisi de sonuç için n hücrelik bir dizi ayırır ve birkaç değişken kullanır. Hızlı çözüm, ek bellek harcamadan kazanılmıştır.

2.4Alan, doğruluk ve sağlamlık

Şimdiye kadar yalnız zamanı ölçtük. İyi bir algoritmanın dört ölçütünden üçü daha vardır (2.1.2): bellek kullanımı, doğruluk ve sağlamlık. Bellek, zamanla aynı araçlarla ölçülür. Doğruluk ve sağlamlık ise ölçülmez; gösterilir ve sınanır.

2.4.1Alan karmaşıklığı

Alan karmaşıklığı, bir algoritmanın kullandığı bellek miktarının girdi boyutuna göre nasıl arttığını gösterir. Zaman karmaşıklığında olduğu gibi büyük O gösterimiyle ifade edilir; sabitler ve küçük terimler yine atılır.

Girdinin kendisi çoğu zaman sayılmaz. maksimum metodu n öğeli bir dizi alır, ama bu dizi metot çağrılmadan önce zaten bellektedir. Metodun kendi harcadığı bellek yalnız enBuyuk ve i değişkenleridir. Algoritmanın girdi dışında kullandığı bu belleğe ek alan denir ve analizde genellikle bu ölçülür. Bir analizde girdinin sayılıp sayılmadığı açıkça belirtilmelidir.

Şekil 2.18 üç temel sınıfı gösterir:

• O(1), sabit alan. Birkaç değişken oluşturmak. Bellek kullanımı girdi boyutuyla değişmez. maksimum, toplam, dogrusalArama, ikiliArama ve tekrarVar yalnız birkaç değişken (en büyük değer, toplam, indisler, lo, hi, mid) kullanır; ek alanları O(1)'dir.
• O(n), doğrusal alan. Girdinin boyutunda yeni bir dizi oluşturmak. onekOrt1 ve onekOrt2, sonucu tutan a dizisi için n hücre ayırır; ek alanları O(n)'dir.
• O(n²), karesel alan. n × n boyutunda bir matris saklamak. Örneğin n şehir arasındaki uzaklıkları tutan bir tablo n² hücre gerektirir. n = 10.000 için bu yüz milyon hücredir; her biri 4 baytlık int ise yaklaşık 400 MB eder.

Bellek verimliliği, belleği sınırlı sistemlerde önemlidir: gömülü cihazlar, telefonlar, aynı anda binlerce isteğe hizmet eden sunucular. Ama sınırsız bellekli bir sistem yoktur. Karesel bellek gerektiren bir algoritma, n yeterince büyüyünce en güçlü makinede de belleği tüketir.

Alan hesabında gözden kaçan bir kalem de çağrı yığınıdır (call stack). Her metot çağrısı bir çerçeve açar (2.3.4) ve çerçeve, metot dönene kadar bellekte kalır. Döngüyle yazılmış bir metot tek çerçeve kullanır. Kendini çağıran, yani özyinelemeli bir metotta ise aynı anda açık olan çerçeve sayısı çağrı derinliği kadardır. n derinliğe inen bir özyineleme, hiç dizi ayırmasa bile O(n) ek alan kullanır.

2.4.2Doğruluk

Hızlı çalışan ama yanlış sonuç veren bir algoritmanın değeri yoktur. Bu yüzden doğruluk, maliyetten önce gelir.

“Her geçerli girdi” ifadesi önemlidir. Sınırsız sayıda girdi vardır ve hepsini denemek mümkün değildir. Doğruluğu göstermek için dört araç kullanılır:

• Test senaryoları. Algoritma, sonucu önceden bilinen girdilerle çalıştırılır ve çıktılar beklenen sonuçlarla karşılaştırılır. Örneğin maksimum({3, 8, 2, 9, 4}) 9 döndürmelidir. Testler hataları bulmakta çok etkilidir, ama doğruluğu kanıtlamaz: denenmeyen bir girdide hata olabilir.
• Uç durumlar. Hataların büyük kısmı sınırlarda saklanır. Boş girdi, tek öğeli girdi, en büyük ve en küçük değerler, bütün öğeleri eşit dizi, zaten sıralı ya da ters sıralı dizi mutlaka denenir. maksimum için tek öğeli dizi, en büyüğün başta, sonda ve ortada olduğu diziler ve negatif sayılardan oluşan dizi iyi uç durumlardır.
• Döngü değişmezi. Her turda doğru kalan bir özellik bulunur ve algoritmanın doğruluğu bu özellikten ispatlanır. Bu, testlerden farklı olarak bütün girdileri kapsar (2.4.3).
• Karşı örnek. Bir algoritmanın yanlış olduğunu göstermek için tek bir girdi yeter. Bu girdiye karşı örnek denir. Doğruluğu göstermek için bütün girdiler hakkında konuşmak gerekir; yanlışlığı göstermek için bir tanesi yeterlidir.

2.4.3Döngü değişmeziyle ispat

Testler “bu girdilerde çalışıyor” der. İspat ise “her girdide çalışır” der. Döngü içeren algoritmalar için en kullanışlı ispat aracı döngü değişmezidir.

Yöntem, matematikteki tümevarıma benzer. Başlangıç adımı ilk basamağı, koruma adımı bir basamaktan ötekine geçişi sağlar; ikisi birlikte önermenin her turda doğru olduğunu gösterir. Sonlanma adımı da bu önermeyi istenen sonuca bağlar.

İspat. Değişmez şudur: her turun başında enBuyuk, a[0..i−1] öğelerinin en büyüğüdür.

• Başlangıç. İlk turdan önce i = 1 ve enBuyuk = a[0]'dır. a[0..0] tek öğelidir ve en büyüğü a[0]'dır. Değişmez doğrudur.
• Koruma. Turun başında enBuyuk, a[0..i−1]'in en büyüğü olsun. Tur a[i]'yi enBuyuk ile karşılaştırır. a[i] daha büyükse enBuyuk = a[i] yapılır; a[i] hem eski en büyükten hem de dolayısıyla öncekilerin hepsinden büyük olduğu için a[0..i]'nin en büyüğüdür. a[i] daha büyük değilse enBuyuk değişmez; eski en büyük a[i]'den küçük değildir ve a[0..i]'nin en büyüğü olarak kalır. Her iki durumda tur sonunda enBuyuk, a[0..i]'nin en büyüğüdür. i++ sonrası bu, “a[0..i−1]'in en büyüğü” demektir. Değişmez korunur.
• Sonlanma. i her turda 1 artar ve döngü i = n olunca durur; yani döngü sonlu sürede biter. Durduğu anda değişmez, enBuyuk'un a[0..n−1]'in, yani bütün dizinin en büyüğü olduğunu söyler. Metot bu değeri döndürür. ∎

Şekil 2.19 değişmezi {3, 8, 2, 9, 4} dizisinde i = 3 anında gösterir. Yeşil çizgiyle işaretli a[0..2] = {3, 8, 2} işlenmiştir ve enBuyuk = 8 bu kısmın en büyüğüdür. Sıradaki a[3] = 9 daha büyük olduğu için tur sonunda enBuyuk = 9 olur ve değişmez a[0..3] için de doğru kalır.

İspatın başında “en az bir öğeli” koşulu vardır. Boş dizide a[0] yoktur ve başlangıç adımı çalışmaz. Bu koşul ispatın bir eksiği değil, metodun ön koşuludur. Ön koşulun sağlanmadığı durumda ne olacağı ise sağlamlık sorusudur.

2.4.4Sağlamlık

Doğruluk, geçerli girdiler hakkındadır. Gerçek programlar ise geçersiz girdilerle de karşılaşır: boş bir dosya, eksik bir satır, beklenmedik biçimde bir sayı. Sağlamlık, algoritmanın bu tür beklenmeyen durumlarla başa çıkabilmesidir. Sağlam bir algoritma, normal aralığın dışındaki girdilerde de çökmez ya da sessizce yanlış sonuç üretmez. Ya girdiyi uygun biçimde işler ya da sorunu açık bir hata mesajıyla bildirir.

Sağlamlık dört açıdan sınanır:

Bu durumların her biri gerçek bir hata kaynağına karşılık gelir. maksimum'a boş dizi verilirse a[0] satırı ArrayIndexOutOfBoundsException fırlatır; null verilirse NullPointerException fırlatır. Bu istisnalar programı durdurur, ama hata mesajı sorunun nedenini açıkça söylemez. İkili aramadaki taşma hatası (2.3.7) ise büyük veri kümelerinde ortaya çıkan bir sağlamlık sorunudur: algoritma küçük dizilerde kusursuz çalışır, ancak bir milyardan büyük dizilerde bozulur.

Sağlam bir sürüm, ön koşulu açıkça denetler ve ihlali anlaşılır bir mesajla bildirir. Aşağıdaki metot, maksimum'un sağlamlaştırılmış bir hâlidir:

int maksimumSaglam(int[] a) {
  if (a == null || a.length == 0)
    throw new IllegalArgumentException("Dizi boş olamaz");
  int enBuyuk = a[0];
  for (int i = 1; i < a.length; i++)
    if (a[i] > enBuyuk)
      enBuyuk = a[i];
  return enBuyuk;
}

İlk satır iki geçersiz durumu birlikte yakalar. a == null denetimi önce yapılır; || işleci soldaki koşul doğruysa sağdakini hiç değerlendirmez. Bu sayede null bir dizinin length alanına erişilmeye çalışılmaz. Geçersiz girdide IllegalArgumentException fırlatılır ve mesaj sorunun ne olduğunu söyler. Metodun geri kalanı maksimum ile aynıdır.

Denetim tek bir karşılaştırmadır ve O(1) sürer. Metodun karmaşıklığı Θ(n) olarak kalır. Sağlamlığın maliyeti çoğu zaman bu kadar küçüktür. Bu yüzden özellikle başkalarının çağıracağı metotlarda ön koşulların denetlenmesi iyi bir alışkanlıktır.

Boş dizide ne yapılacağı bir tasarım kararıdır. İstisna fırlatmak bir seçenektir. Başka bir seçenek, özel bir değer döndürmektir; Java kütüphanesindeki OptionalInt bu iş için tasarlanmıştır. Yanlış olan tek seçenek, sessizce anlamsız bir değer döndürmektir. Örnek 2.9'daki hatalı sürüm boş dizide 0 döndürür. Bu değer, çağıran kodun “dizinin en büyüğü 0'dır” sonucuna varmasına yol açar.

2.5Sık yapılan hatalar

Not boyunca her konunun yanında verilen hataların en önemlileri Tablo 2.20'de bir arada toplanmıştır.

Dizi karşılaştırma hatası, tekrarVar gibi metotları sınarken sık yapılır. int[] a = {1, 2}; int[] b = {1, 2}; yazıldığında a == b false'tur, çünkü a ve b bellekte iki ayrı diziyi gösterir. == “aynı dizi mi?” sorusunu sorar, “aynı içerikte mi?” sorusunu değil. Arrays.equals(a, b) ise öğeleri tek tek karşılaştırır ve true döndürür. Bu karşılaştırma O(n) sürer; == ise O(1)'dir, çünkü yalnız iki referansı karşılaştırır.

“O(1) her zaman hızlıdır” satırının ardındaki ders, öteki sınıflar için de geçerlidir. Örneğin 1000n adımlık doğrusal bir algoritma ile n² adımlık karesel bir algoritmayı karşılaştıralım. 1000n < n² eşitsizliği ancak n > 1000 için doğrudur. Daha küçük girdilerde karesel algoritma daha hızlıdır. Asimptotik analiz, girdi büyüdükçe hangisinin kazanacağını söyler; küçük girdilerde hangisinin hızlı olduğunu söylemek için sabitlere de bakmak gerekir.

2.6Özet

• Algoritma, her geçerli girdi için doğru çıktıyı üreten sonlu, kesin ve etkili adımlardan oluşan yöntemdir. İyi bir algoritma dört ölçütle değerlendirilir: zaman karmaşıklığı, alan karmaşıklığı, doğruluk ve sağlamlık.
• Deneysel analiz süreyi System.nanoTime() ile ölçer. Ölçümler tekrarlanır, ortanca alınır ve ilk (ısınma) ölçümü ayrılır. Katlama deneyinde T(2n)/T(n) ≈ 2^k ise T(n) ≈ c · n^k'dir. Deneysel analiz donanıma bağlıdır, yalnız denenen girdileri kapsar ve tam bir kod gerektirir.
• İlkel işlemleri saymak donanımdan bağımsızdır ve bütün girdiler için geçerlidir. maksimum en iyi durumda 3n + 1, en kötü durumda 4n işlem yapar; ikisi de Θ(n)'dir.
• f(n) = O(g(n)): bir c > 0 ve n₀ için her n ≥ n₀'da f(n) ≤ c · g(n) (üst sınır). Ω alt sınır, Θ ikisi birden (sıkı sınır). Sabit çarpanlar ve küçük terimler atılır; d. dereceden polinom Θ(n^d)'dir; logaritmanın tabanı önemsizdir.
• En iyi, ortalama ve en kötü durum, hangi girdinin maliyetine bakıldığını belirler ve sınır gösterimlerinden bağımsızdır. En kötü durum garanti verir; ortalama durum bir olasılık dağılımı varsayar; en iyi durum tek başına yanıltıcıdır. Amortize analiz, uzun bir işlem dizisinin toplam maliyetini işlem sayısına böler; büyüyen dizide sona ekleme amortize O(1)'dir.
• Sık görülen sınıflar, yavaştan hızlıya: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Saniyede 10⁹ işlemle n = 100 için 2ⁿ adım yaklaşık 4 · 10¹³ yıl sürer.
• Döngü kalıpları: tek döngü O(n); katlanan ya da yarıya inen döngü O(log n); iç içe iki tam döngü O(n²); dış n, iç log n tur dönen döngü O(n log n). Ardışık bloklarda maliyetler toplanır, iç içe döngülerde çarpılır.
• Doğrusal arama O(n)'dir ve sıralı dizi gerektirmez. İkili arama sıralı dizide her turda aralığı yarıya indirir ve en çok ⌊log₂ n⌋ + 1 tur döner: O(log n). Orta indis lo + (hi - lo) / 2 ile hesaplanır.
• tekrarVar bütün çiftleri karşılaştırır: en kötü durumda n(n − 1)/2 karşılaştırma, O(n²). Önek ortalamalarında her öneki baştan toplayan onekOrt1 n(n + 1)/2 toplama ile O(n²), toplamı taşıyan onekOrt2 n toplama ile O(n)'dir.
• Alan karmaşıklığı genellikle girdi dışındaki ek belleği ölçer: birkaç değişken O(1), yeni dizi O(n), n × n matris O(n²). Özyinelemede çağrı yığını da sayılır.
• Doğruluk testlerle, uç durumlarla ve döngü değişmeziyle (başlangıç, koruma, sonlanma) gösterilir; tek bir karşı örnek yanlışlığı kanıtlar. Sağlam bir algoritma geçersiz girdiyi fark eder ve açıkça bildirir.

Bu bölümde geliştirilen araçlar, sonraki bütün veri yapılarının işlemlerini karşılaştırmakta kullanılır. Tablo 2.22, temel veri yapılarında sık kullanılan işlemlerin maliyetlerini bir arada verir. Tablodaki yapılar dersin ilerleyen konularıdır; buradaki amaç, aynı işlemin farklı yapılarda ne kadar farklı maliyetli olabileceğini görmektir.

Tablonun ilk satırı bu bölümün sonuçlarıyla doğrudan ilişkilidir. Dizide i. öğeye erişim ilk metodundaki gibi adres hesabıyla yapılır: O(1). Sırasız dizide arama doğrusal aramadır: O(n). Dizi sıralı tutulursa arama ikili aramayla O(log n)'e iner. Ortaya ekleme ve silme ise sonraki öğelerin kaydırılmasını gerektirdiği için O(n)'dir.

2.7Kavram listesi

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

• algoritma algorithm
• algoritma analizi algorithm analysis
• karmaşıklık complexity
• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity
• deneysel analiz empirical analysis
• katlama deneyi doubling experiment
• ilkel işlem primitive operation
• asimptotik asymptotic
• büyük O Big O
• büyük Omega Big Omega
• büyük Teta Big Theta
• en iyi durum best case
• ortalama durum average case
• en kötü durum worst case
• amortize analiz amortized analysis
• döngü loop
• doğrusal arama linear search
• ikili arama binary search
• önek ortalamaları prefix averages
• çerçeve stack frame
• referans reference
• doğruluk correctness
• değişmez invariant
• sağlamlık robustness

2.8Kendini Dene

1. maksimum({5, 1, 7, 7, 2}) çağrısında enBuyuk kaç kez güncellenir? Tablo 2.3'teki sayım kurallarıyla toplam kaç ilkel işlem yapılır?

   Cevap

   Karşılaştırmalar: 1 > 5 yanlış, 7 > 5 doğru (güncelleme), 7 > 7 yanlış, 2 > 7 yanlış. Yalnız bir güncelleme yapılır: g = 1. İkinci 7, eşitlik olduğu için güncelleme yaptırmaz. Toplam 3n + 1 + g = 3 · 5 + 1 + 1 = 17 işlem.

2. f(n) = 4n + 7 için f(n) = O(n) olduğunu gösteren bir c ve n₀ çifti nedir? f(n) = Θ(n) midir?

   Cevap

   c = 5 seçilirse 4n + 7 ≤ 5n eşitsizliği n ≥ 7 için sağlanır: n₀ = 7. (c = 11, n₀ = 1 de geçerlidir.) Alt sınır için her n ≥ 1'de 4n + 7 ≥ 4n'dir, yani f(n) = Ω(n). İkisi birlikte f(n) = Θ(n) verir.

3. Aşağıdakilerden hangileri doğrudur? (a) n² + 100n = O(n²) (b) 2ⁿ⁺¹ = O(2ⁿ) (c) n log n = O(n) (d) 4ⁿ = O(2ⁿ) (e) log₁₀ n = Θ(log₂ n)

   Cevap

   (a), (b) ve (e) doğrudur. (a): n ≥ 1 için n² + 100n ≤ 101n². (b): 2ⁿ⁺¹ = 2 · 2ⁿ; sabit çarpan. (e): iki logaritma arasında sabit çarpan vardır. (c) yanlıştır: n log n / n = log n oranı sınırsız büyür. (d) yanlıştır: 4ⁿ / 2ⁿ = 2ⁿ oranı sınırsız büyür.

4. for (int i = 1; i <= n; i *= 3) s++; döngüsü n = 81 için kaç tur döner? Karmaşıklığı nedir?

   Cevap

   i 1, 3, 9, 27, 81 değerlerini alır; koşul <= olduğu için 81'de de gövde çalışır. Sonra i = 243 olur ve döngü biter: 5 tur, yani log₃ 81 + 1. Karmaşıklık O(log n)'dir; tabanın 3 olması sınıfı değiştirmez.

5. Aşağıdaki kod bittiğinde n = 10 için s kaçtır? Karmaşıklık nedir?

   for (i = 0; i < n; i++) for (j = 0; j < 5; j++) s++;
for (k = 0; k < n; k++) for (m = 0; m < k; m++) s++;

   Cevap

   Birinci blok: iç döngü sabit 5 tur, dış döngü 10 tur: 50; O(n). İkinci blok: 0 + 1 + … + 9 = 10 · 9 / 2 = 45; O(n²). Toplam s = 95. Ardışık bloklarda en büyük kalır: O(n²).

6. a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} dizisinde ikiliArama(a, 91) ve ikiliArama(a, 2) kaçar tur döner? Her turda lo, hi ve mid ne olur?

   Cevap

   91 için: (0, 9, mid 4, 16 < 91) → lo = 5; (5, 9, 7, 56) → lo = 8; (8, 9, 8, 72) → lo = 9; (9, 9, 9, 91) bulundu, 9 döner. 4 tur. 2 için: (0, 9, 4, 16 > 2) → hi = 3; (0, 3, 1, 5 > 2) → hi = 0; (0, 0, 0, 2) bulundu, 0 döner. 3 tur. İkisi de ⌊log₂ 10⌋ + 1 = 4 sınırını aşmaz.

7. 9 öğeli bir dizide doğrusal arama yapılıyor. Hedefin her zaman dizide olduğu ve dokuz konumdan her birinde eşit olasılıkla bulunduğu varsayılırsa ortalama kaç karşılaştırma yapılır? Hedef dizide yoksa kaç karşılaştırma yapılır?

   Cevap

   Hedef k. konumdaysa (1'den sayarak) k karşılaştırma yapılır. Ortalama (1 + 2 + … + 9)/9 = 45/9 = 5; bu (n + 1)/2 formülüyle aynıdır. Hedef yoksa dokuz öğenin hepsine bakılır: 9 karşılaştırma.

8. Bir katlama deneyinde n = 1000, 2000, 4000, 8000 için süreler 40, 81, 160 ve 322 ms ölçülmüştür. Algoritma hangi büyüme sınıfındadır? n = 16.000 için süre yaklaşık kaçtır?

   Cevap

   Oranlar 81/40 ≈ 2,03, 160/81 ≈ 1,98, 322/160 ≈ 2,01'dir. 2^k ≈ 2 olduğundan k = 1: büyüme doğrusaldır. n = 16.000 için süre yaklaşık 2 · 322 = 644 ms olur.

9. Bir öğrenci maksimum'u enBuyuk = 0 ile başlatıp döngüyü i = 0'dan çalıştırıyor. Bu sürümün yanlış olduğunu gösteren bir karşı örnek nedir? Hangi değişmez bu sürümde başlangıç adımında bozulur?

   Cevap

   {-4, -2, -9} için metot 0 döndürür; doğru cevap −2'dir. Değişmez “her turun başında enBuyuk, a[0..i−1]'in en büyüğüdür” önermesidir. İlk turdan önce i = 0'dır ve a[0..−1] boştur; boş kümenin en büyüğü yoktur ve 0 değeri dizinin bir öğesi değildir. Başlangıç adımı sağlanmadığı için ispat çöker ve negatif sayılı dizilerde sonuç yanlış çıkar.

10. Aşağıdaki metotların ek alan karmaşıklığı nedir? (Girdi sayılmaz.) (a) toplam (b) onekOrt1 (c) n öğeli bir diziden, her (i, j) çifti için a[i] + a[j] değerini tutan n × n bir matris oluşturan metot (d) adimSay

    Cevap

    (a) O(1): yalnız s ve x. (b) O(n): sonuç dizisi a. (c) O(n²): n² hücreli matris. (d) O(1): yalnız k ve i.

2.9İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 4: deneysel analizi, ilkel işlem saymayı, büyük O, Omega ve Teta gösterimlerini ve önek ortalamaları örneğini bu nottakine yakın bir sırayla ve Java koduyla anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.4: katlama deneyini ve gözleme dayalı çalışma süresi tahminini ayrıntılı örneklerle işler; deneysel ve matematiksel analizin birlikte nasıl kullanılacağını gösterir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 2 ve 3: döngü değişmeziyle doğruluk ispatını ve asimptotik gösterimin biçimsel tanımlarını daha matematiksel bir dille verir.
• J. Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken” (Google Research Blog, 2006): ikili aramadaki orta indis taşmasının gerçek bir yazılımda nasıl ortaya çıktığını anlatan kısa bir yazı.

2.10Kaynaklar

1. J. Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2 Haziran 2006.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
4. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

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