Bölüm 1.1: Giriş

1.1.1Algoritma kavramı

“Algoritma” sözcüğü, 9. yüzyılda Bağdat'ta yaşamış matematikçi Muhammed bin Musa el-Harezmî'nin adının Latinceleşmiş biçiminden gelir. Harezmî'nin Hint rakamlarıyla hesap yapmayı anlatan kitabı, Avrupa'da Latince çevirisiyle tanınmıştır. Çeviri “Dixit Algorizmi” (Harezmî der ki) sözleriyle başlar. Zamanla bu ad, belirli bir hesabı adım adım yapma yönteminin genel adı olmuştur. Bugün bir bilgisayar programının çözdüğü her problemin arkasında bir algoritma vardır: arama motorunun sonuçları sıralaması, haritanın en kısa yolu bulması, bir fotoğrafın sıkıştırılması.

1.1.1.1Algoritma nedir?

Bir yemek tarifi, bir mobilya kurulum kılavuzu ya da elle uzun bölme yapma yöntemi aynı ortak yapıyı taşır. Hepsinde başlangıçta elde bazı şeyler vardır: malzemeler, parçalar, iki sayı. Ardından sırası belli adımlar gelir. Adımlar bittiğinde istenen sonuç ortaya çıkar: yemek, dolap, bölüm ve kalan. Algoritma, bu yapının bilgisayar biliminde kesin kurallarla tanımlanmış hâlidir.

Tanımda üç parça öne çıkar. Birincisi girdi ve çıktı: algoritma bir şey alır ve bir şey verir. İkincisi adımların açıklığı: her adım tek bir biçimde anlaşılır. Üçüncüsü sonluluk: adımlar sonsuza kadar sürmez. Bu üç parçanın her biri, bir sonraki alt kesimde ayrı bir özellik olarak ele alınır.

Algoritmanın bir programlama dilinde yazılmış olması gerekmez. Türkçe cümlelerle, numaralı adımlarla, akış şemasıyla ya da sözde kodla (pseudocode) anlatılabilir. Program ise algoritmanın belirli bir dilde, belirli bir makinede çalışacak biçimde yazılmış hâlidir. Aynı algoritma Java, Python ya da C ile yazılabilir; her biri ayrı bir programdır ama hepsi aynı algoritmayı izler. Bu ayrım, algoritma analizinin temelidir. Bir algoritmanın iyi ya da kötü olduğuna, onu yazan dilden ve çalıştıran makineden bağımsız olarak karar verilir.

1.1.1.2Bir algoritmanın taşıması gereken özellikler

Her adımlar listesi algoritma sayılmaz. Donald Knuth, algoritmanın beş özelliğini sayar: girdi, çıktı, açıklık, sonluluk ve etkinlik. Bunlara pratikte bir altıncısı, doğruluk eklenir. Tablo 1.1.1 bu altı özelliği kısa açıklamalarıyla verir; ardından her biri tek tek ele alınır.

Girdi (input). Algoritma çalışmaya başlamadan önce ya da çalışırken dışarıdan değer alır. Girdi sayısı sıfır da olabilir. Örneğin “ilk 100 asal sayıyı yazdır” görevinin dışarıdan aldığı bir değer yoktur; yine de geçerli bir algoritmadır. Çoğu algoritmada ise girdi, problemin kendisidir: sıralanacak dizi, aranan sayı, iki şehir arasındaki yol ağı.

Çıktı (output). Algoritma en az bir sonuç üretir ve bu sonuç girdiyle ilişkilidir. Hiçbir şey üretmeyen bir adımlar listesi, ne kadar uzun çalışırsa çalışsın bir işe yaramaz. Çıktı her zaman ekrana yazılan bir değer olmak zorunda değildir. Bir metodun döndürdüğü değer, değiştirilmiş bir dizi ya da “evet/hayır” biçiminde bir karar da çıktıdır.

Açıklık (definiteness). Her adım kesin olarak tanımlanır ve yalnız bir biçimde anlaşılır. “Biraz tuz ekle” bir insan için yeterli olabilir; bir makine için ise anlamsızdır. Algoritma, adımı okuyan herkesin aynı işi yapmasını gerektirir. Bu yüzden “biraz”, “yeterince”, “uygun bir değer” gibi ifadeler algoritmada yer almaz.

Sonluluk (finiteness). Algoritma her girdi için sonlu sayıda adımdan sonra durur. Kodu yazılmış ama bazı girdilerde hiç bitmeyen bir döngü, o girdiler için algoritma değildir. Sonluluğu bozan en yaygın hata, döngü koşulunun hiçbir zaman yanlış olmamasıdır. Örneğin bir sayıyı her turda 2 azaltıp sıfıra ulaşınca duran bir döngü, tek sayılarda sıfırı atlar ve sonsuza dek döner.

Etkinlik (effectiveness). Her adım, kâğıt kalemle ya da makinede sonlu sürede yapılabilecek kadar temel bir işlemdir. “Sayının asal çarpanlarını bul” tek bir adım olarak yazılamaz, çünkü bu kendi başına bir problemdir; ancak daha temel adımlara ayrıldıktan sonra algoritmanın parçası olur. “Bütün gerçel sayıları tek tek dene” ise hiç yapılamaz, çünkü gerçel sayılar sayılamayacak kadar çoktur.

Doğruluk (correctness). Algoritma her geçerli girdi için doğru çıktıyı verir. Birkaç örnekte doğru sonuç vermek yetmez; doğruluk, bütün geçerli girdiler için gösterilmesi gereken bir özelliktir. Bu gösterim çoğu zaman bir kanıt gerektirir. Öklid algoritmasının doğruluğu, bu notun son kesiminde böyle bir kanıtla gösterilir.

Örnek, doğruluğun girdi kümesine bağlı olduğunu da gösterir. Bir algoritma “her geçerli girdi için” doğru olmalıdır; hangi girdilerin geçerli olduğu ise problemin tanımında baştan söylenir. Problem tanımı belirsiz kalırsa algoritmanın doğru olup olmadığı da belirsiz kalır.

1.1.1.3Günlük hayattan: çay hazırlama

Algoritma kavramını somutlaştırmanın kolay bir yolu, iyi bilinen bir günlük işi adım adım yazmaktır. Çay hazırlamanın girdisi su, çay yaprakları ve isteğe bağlı olarak şeker ile süttür; çıktısı bir fincan çaydır. Sunumdaki algoritma altı adımdan oluşur:

1. Suyu kaynat.
2. Kaynamış suyu demliğe koy.
3. Demliğin içine çay yapraklarını ekle.
4. Çayın demlenmesini bekle.
5. Demlenen çayı fincana süzerek koy.
6. İsteğe bağlı olarak şeker ve süt ekle.

Bu kısa liste, algoritmanın üç önemli niteliğini gösterir.

Sıra önemlidir. Algoritma, sıralı bir adımlar listesidir. Bazı adımların yeri değişebilir: 2. ve 3. adımlar yer değiştirse, yani önce yapraklar demliğe konup sonra kaynar su eklense, sonuç değişmez. Ama 1. adım ile 5. adımın yeri değişemez. Su kaynamadan çay süzülemez; süzülecek bir şey yoktur. Bir algoritma yazılırken hangi adımın hangisinden önce gelmesi gerektiği, yani adımlar arasındaki bağımlılık dikkatle düşünülür.

Açıklık her okur için ayrı sınanır. “Çayın demlenmesini bekle” adımı bir insan için yeterlidir; deneyimli biri çayın rengine bakıp karar verir. Bir bilgisayar için ise bu adım belirsizdir: ne kadar beklenecektir? Adım makine için “10 dakika bekle” biçiminde yazılmalıdır. Açıklık özelliği tam olarak bunu ister: adımı okuyan herkes, yorum yapmadan aynı işi yapabilmelidir.

Algoritmalar karar içerir. 6. adım bir koşul taşır: “şeker isteniyorsa şeker ekle, süt isteniyorsa süt ekle.” Algoritmanın izlediği yol girdiye göre değişebilir. Programlamada bu, if deyimine karşılık gelir. Benzer biçimde “su kaynayana kadar bekle” gibi bir adım bir döngüdür. Sıralı adımlar, kararlar ve döngüler, her algoritmanın yapı taşlarıdır.

1.1.1.4Algoritmadan koda: ortalama bulma

Üç sayının ortalamasını bulma problemi, algoritma ile program arasındaki ilişkiyi göstermek için uygun, küçük bir örnektir. Girdi üç sayıdır (Sayı1, Sayı2, Sayı3), çıktı bunların ortalamasıdır. Algoritma üç adımdan oluşur:

1. Toplam = Sayı1 + Sayı2 + Sayı3
2. Ortalama = Toplam / 3
3. Ortalama değerini ekrana yazdır.

Bu algoritmanın Python ile yazılmış hâli şöyledir:

def ortalama_hesapla(sayi1, sayi2, sayi3):
    ortalama = (sayi1 + sayi2 + sayi3) / 3
    return ortalama

sayi1 = float(input("Birinci sayıyı girin: "))
sayi2 = float(input("İkinci sayıyı girin: "))
sayi3 = float(input("Üçüncü sayıyı girin: "))
ort = ortalama_hesapla(sayi1, sayi2, sayi3)
print("Girilen sayıların ortalaması:", ort)

Aynı algoritmanın Java'daki karşılığı da aşağıdadır. Kod, bir sınıfın main metodu olarak yazılmıştır; Scanner sınıfı için dosyanın başında import java.util.Scanner; satırı gerekir.

public static void main(String[] args) {
  Scanner giris = new Scanner(System.in);
  System.out.println("Birinci sayıyı girin: ");
  double sayi1 = giris.nextDouble();
  System.out.println("İkinci sayıyı girin: ");
  double sayi2 = giris.nextDouble();
  System.out.println("Üçüncü sayıyı girin: ");
  double sayi3 = giris.nextDouble();
  double ortalama = (sayi1 + sayi2 + sayi3) / 3;
  System.out.println("Sayıların ortalaması: "
                     + ortalama);
}

İki program farklı görünür. Python'da hesap bir fonksiyona ayrılmıştır ve girdiler input ile okunup float'a çevrilir. Java'da her şey main içindedir, girdiler Scanner nesnesiyle nextDouble() metoduyla okunur ve değişkenlerin tipi (double) açıkça yazılır. Ama iki program da aynı üç adımı izler: üç sayı toplanır, toplam 3'e bölünür, sonuç yazılır. Örneğin girdi 4, 7 ve 10 ise iki program da 7,0 yazar.

Bu gözlem, algoritmanın dilden bağımsız olduğunu gösterir. Program, algoritmanın belirli bir dildeki karşılığıdır. Bir algoritmayı anlamak ve analiz etmek için onun hangi dilde yazıldığı önemli değildir. Bu notta kodlar Java ile verilir, ama her kodun arkasındaki fikir başka bir dile de aynen taşınabilir.

1.1.1.5Algoritma türleri

Algoritmalar, çözdükleri probleme ya da izledikleri tasarım fikrine göre gruplanır. Bu ders, aşağıdaki grupların her birinden temel algoritmaları ele alır.

• Sıralama algoritmaları öğeleri bir düzene koyar. Eklemeli sıralama (insertion sort), birleştirme sıralaması (merge sort) ve hızlı sıralama (quick sort) bu grubun en bilinen üyeleridir. Sıralı veri, aramayı ve birçok başka işlemi hızlandırdığı için sıralama, bilgisayar biliminin en çok çalışılmış problemlerinden biridir.
• Arama algoritmaları bir veri kümesinde belirli bir öğeyi bulur. Doğrusal arama öğeleri tek tek inceler. İkili arama sıralı dizide aralığı her adımda yarıya indirir. Hash tablosu ise öğenin yerini doğrudan hesaplar.
• Çizge algoritmaları, düğümler ve onları bağlayan kenarlardan oluşan yapılar üzerinde çalışır. İki nokta arasındaki en kısa yolu bulan Dijkstra algoritması, bütün düğümleri en az toplam maliyetle bağlayan minimum kapsayan ağaç algoritmaları ve bir ağdan geçebilecek en büyük akışı bulan Ford–Fulkerson yöntemi bu gruptandır.
• Dizgi ve sıkıştırma algoritmaları metinle çalışır. Bir metinde bir sözcüğü aramak, sözcükleri trie adlı ağaçta saklamak ve dosya boyutunu küçültmek (Huffman kodlaması, gzip) bu gruba girer.
• Tasarım teknikleri tek bir problemi değil, birçok probleme uygulanabilen genel bir çözüm fikrini anlatır. Böl ve fethet (birleştirme sıralaması, ikili arama, hızlı üs alma), dinamik programlama, açgözlü algoritmalar, geri izleme ve dal sınır bu tekniklerin başlıcalarıdır.
• Rastgele ve yaklaşık algoritmalar, zor problemler için iki ayrı yol sunar. Rastgele algoritma adımlarında rastgele seçim yapar. Yaklaşık algoritma ise en iyi çözümü bulmanın çok uzun süreceği problemlerde, en iyiye kanıtlanmış bir oranda yakın bir çözümü kısa sürede bulur.

Bu gruplar birbirini dışlamaz. Birleştirme sıralaması hem bir sıralama algoritmasıdır hem de böl ve fethet tekniğinin örneğidir. Hızlı sıralama, pivotu rastgele seçen biçimiyle aynı zamanda bir rastgele algoritmadır.

1.1.1.6Deterministik ve rastgele algoritmalar

Algoritmaları ayırmanın bir başka yolu, aynı girdi verildiğinde hep aynı yolu izleyip izlemediklerine bakmaktır.

Bir dizinin en büyük öğesini bulan algoritma deterministiktir: dizi aynıysa hangi öğelerin hangi sırayla karşılaştırılacağı da aynıdır. Pivotu rastgele seçen hızlı sıralama ise her çalıştırmada diziyi farklı noktalardan bölebilir. Bu algoritma bir anlamda zar atar. Ama sonuç değişmez; dizi her seferinde doğru sıralanır. Değişen yalnız izlenen yol ve dolayısıyla çalışma süresidir.

Rastgeleliğin bir algoritmaya ne kazandırdığı ilk bakışta açık değildir. Hızlı sıralamada pivot hep ilk öğe seçilirse, zaten sıralı bir dizi algoritmayı en yavaş çalışma biçimine sokar. Rastgele pivot ise “kötü girdi” kavramını ortadan kaldırır: hiçbir girdi her çalıştırmada kötü sonuç vermez ve beklenen süre her girdide aynı ölçüde kısa kalır. Bazı rastgele algoritmalar ise çok küçük bir olasılıkla yanlış cevap vermeyi göze alarak büyük hız kazanır. Bu notun geri kalanındaki bütün algoritmalar deterministiktir.

1.1.2Algoritma analizi

Bir problemi çözen algoritmayı bulmak işin yarısıdır. Aynı problemi çözen birden çok algoritma varsa hangisinin seçileceğine de karar vermek gerekir. Bu kararın aracı algoritma analizidir. Bu kesim, analizin neyi ölçtüğünü, ölçümün neden saniyeyle değil işlem sayısıyla yapıldığını ve n büyürken farklı algoritmaların ne kadar ayrıştığını anlatır.

1.1.2.1Neden analiz?

Analizin değerini küçük bir örnek açıkça gösterir. Bir milyon (10⁶) öğeli sıralı bir dizide bir sayı aranıyor olsun. Doğrusal arama dizinin başından başlar ve öğeleri tek tek inceler. Aranan sayı dizide yoksa ya da en sondaysa bir milyon karşılaştırma yapar. İkili arama ise ortadaki öğeye bakar ve aranan sayı daha küçükse sol yarıda, büyükse sağ yarıda aramayı sürdürür. Her karşılaştırma aralığı yarıya indirdiği için en fazla 20 karşılaştırma yapar, çünkü bir milyon yaklaşık 2²⁰'dir. Şekil 1.1.1 bu iki sayıyı logaritmik ölçekte karşılaştırır.

İki algoritma da doğrudur; ikisi de sayıyı bulur. Aralarındaki fark yalnız kaynak kullanımındadır ve bu fark elli bin kattır. Analiz, böyle bir farkı programı yazmadan, yalnız algoritmanın adımlarına bakarak önceden görmeyi sağlar. Hangi algoritmanın seçileceği, çoğu zaman bu tür bir karşılaştırmayla belirlenir.

1.1.2.2Girdi boyutu ve temel işlem

Bir algoritmanın ne kadar sürdüğünü ölçmenin ilk aklı gelen yolu, programı çalıştırıp saati tutmaktır. Ama bu ölçüm birçok şeye bağlıdır: işlemcinin hızı, programlama dili, derleyici, aynı anda çalışan öteki programlar. Aynı kod bir dizüstü bilgisayarda 2 saniye, bir sunucuda 0,3 saniye sürebilir. Bu sayılar algoritma hakkında değil, makine hakkında bilgi verir.

Algoritma analizi bu yüzden süreyi saniyeyle ölçmez. Onun yerine algoritmanın yaptığı temel işlemleri sayar. Temel işlem, makinede sabit sürede yapılan işlemdir: iki sayıyı toplamak ya da karşılaştırmak, bir dizi hücresine erişmek, bir değişkene değer atamak. İşlem sayısı makineden makineye değişmez. Hızlı bir makine her işlemi daha kısa sürede yapar, ama işlem sayısı aynı kalır.

İşlem sayısı ise girdiye bağlıdır. Beş öğeli bir diziyi toplamak, bir milyon öğeli diziyi toplamaktan az iş ister. Bu yüzden işlem sayısı, girdinin büyüklüğünü gösteren bir sayının fonksiyonu olarak yazılır.

Girdi boyutunun ne olduğu probleme göre seçilir. Bir dizi işleyen algoritmada doğal seçim öğe sayısıdır. İki n × n matrisi çarpan algoritmada n'dir. Tek bir sayıyı girdi olarak alan algoritmada ise iki seçenek vardır: sayının değeri ya da sayının kaç basamakla yazıldığı. Bu iki seçenek çok farklı sonuçlar verir; asallık testi incelenirken bu ayrıma ayrıca dönülür.

Aynı boyuttaki iki girdi de farklı sayıda işlem gerektirebilir. Doğrusal arama, aranan öğe dizinin ilk hücresindeyse tek karşılaştırmayla biter; dizide hiç yoksa n karşılaştırma yapar. Bu yüzden analizde çoğu zaman en kötü durum (worst case) incelenir: aynı boyuttaki girdiler arasında en çok işlem gerektireni. En kötü durum bir garanti verir. Algoritma hiçbir girdide bu sayıdan fazla işlem yapmaz.

1.1.2.3Satır satır sayım: dizi toplamı

İşlem saymanın nasıl yapıldığını görmek için n öğeli bir dizinin toplamını hesaplayan kısa koda bakalım. Sunumdaki kodun her satırının yanında o satırın kaç kez çalıştığı yazılıdır.

int toplam = 0;                   // 1 kez
for (int i = 0; i < n; i++)       // n+1 karşılaştırma
  toplam += dizi[i];              // n kez
return toplam;                    // 1 kez

Sayım satır satır yapılır.

• int toplam = 0; döngüden önce bir kez çalışır: 1 işlem.
• for satırındaki i < n karşılaştırması, döngüye her girişte bir kez yapılır. i değeri 0, 1, …, n − 1 iken koşul doğrudur ve döngü gövdesi çalışır; bu n karşılaştırma eder. i = n olduğunda koşul bir kez daha sınanır, yanlış çıkar ve döngü biter. Toplam n + 1 karşılaştırma.
• toplam += dizi[i]; döngü gövdesidir ve n kez çalışır.
• return toplam; bir kez çalışır: 1 işlem.

Bu sayıların toplamı çalışma süresini verir:

T(n) = 1 + (n + 1) + n + 1 = 2n + 3

Bu sayımda i++ artırmaları ve dizi[i] erişimi ayrı işlem olarak sayılmadı. Onlar da sayılsaydı sonuç 4n + 3 gibi başka bir ifade olurdu. Hangi işlemlerin sayılacağı bir seçimdir ve bu seçim katsayıları değiştirir. Ama bir şey değişmez: işlem sayısı her durumda n'nin bir katı artı bir sabittir. Dizi iki katına çıkarsa iş de yaklaşık iki katına çıkar.

1.1.2.4Sabitler neden önemsizleşir?

2n + 3 ifadesindeki 2 ve 3 sayıları makineye ve sayım biçimine bağlıdır. Bir makinede karşılaştırma toplama işleminden iki kat yavaş olabilir; bir derleyici iki işlemi tek komutta birleştirebilir. Bu sabitleri kesin olarak bilmek hem zordur hem de pek bir işe yaramaz. Önemli olan, n büyürken T(n)'nin hangi hızla büyüdüğüdür.

n = 10 iken 2n + 3 = 23'tür ve sabit terim 3 toplamın yaklaşık sekizde birini oluşturur. n = 10⁶ olduğunda ise 2n + 3 = 2.000.003'tür ve 3'ün katkısı milyonda bir düzeyine iner. Büyük n için yalnız en hızlı büyüyen terim belirleyicidir. Katsayısı da önemsizleşir, çünkü katsayı her n için aynı oranda etki eder: süreyi iki katına çıkarır, ama büyüme biçimini değiştirmez.

Bu düşünce, algoritmaları büyüme hızlarına göre sınıflamaya götürür. 2n + 3, 5n ve n/2 + 100 fonksiyonlarının hepsi n ile doğru orantılı büyür. Bunlara doğrusal (linear) denir ve kısaca Θ(n) diye yazılır. Θ (teta) gösterimi, sabit katsayıları ve küçük terimleri atıp yalnız büyüme hızını bırakır. Benzer biçimde O(n) (büyük O) gösterimi “en fazla n ile orantılı büyür” anlamına gelir; yani bir üst sınır verir. Bu notta iki gösterim bu sezgisel anlamlarıyla kullanılır. T(n) = 2n + 3 için hem T(n) = Θ(n) hem de T(n) = O(n) yazılabilir.

1.1.2.5Büyüme tablosu

Algoritmaların çalışma süreleri birkaç tanıdık fonksiyon ailesine düşer: sabit (1), logaritmik (log n), karekök (√n), doğrusal (n), log-doğrusal (n log n), karesel (n²), kübik (n³), üstel (2ⁿ) ve faktöriyel (n!). Bu fonksiyonların n büyürken nasıl davrandığını görmenin en iyi yolu, değerlerini yan yana koymaktır. Tablo 1.1.2 sunumdaki büyüme tablosunu verir.

Tabloyu satır satır okumak birkaç önemli gözlem verir.

Sabit ve logaritmik büyüme neredeyse hiç büyümez. n, 10'dan 10⁶'ya, yani yüz bin katına çıktığında log₂ n yalnız 3,3'ten 19,9'a çıkar. Logaritma, “n'yi kaç kez ikiye bölersem 1'e inerim?” sorusunun cevabıdır. Bir milyonu yirmi kez ikiye bölmek onu 1'e indirir. İkili aramanın 20 karşılaştırması bu sayıdan gelir.

Karekök, doğrusaldan çok yavaş büyür. n = 10⁶ iken √n yalnız 1000'dir. Bir algoritmayı n'den √n'ye indirmek, bir milyonluk girdide işi bin kat azaltır.

n log n, doğrusala çok yakındır. Bir milyon öğede n log₂ n yaklaşık 2 · 10⁷'dir; doğrusal sürenin yalnız yirmi katı. Saniyede 10⁹ işlem yapan bir makinede bu 20 milisaniye eder. Verimli sıralama algoritmaları bu sınıftadır.

Polinomlar arasında bile büyük uçurumlar vardır. Aynı bir milyonluk girdide n² işlem 16,7 dakika, n³ işlem yaklaşık 32 yıl sürer. Karesel bir algoritma küçük girdilerde sorun çıkarmaz, ama girdi büyüdükçe kullanılamaz hâle gelir.

Üstel ve faktöriyel büyüme her sınırı aşar. 2ⁿ, n = 100'de bile 1,3 · 10³⁰'a ulaşır. Saniyede 10⁹ işlemle bu, yaklaşık 4 · 10¹³ yıl eder; evrenin yaşı ise yaklaşık 1,4 · 10¹⁰ yıldır. n! daha da hızlıdır: n = 10'da 3.628.800'e, n = 100'de 158 basamaklı bir sayıya ulaşır. Bu iki sınıftaki algoritmalar yalnız çok küçük girdilerde kullanılabilir.

Tablodaki sıralama, bu dersin geri kalanında sürekli kullanılır:

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

Buradaki “<” işareti, yeterince büyük n için soldaki fonksiyonun sağdakinden küçük kaldığını, üstelik aradaki oranın sınırsız büyüdüğünü anlatır. Küçük n değerlerinde sıra bozulabilir: n = 10'da √n ≈ 3,2, log₂ n ≈ 3,3'ten küçüktür. n = 16'da ikisi de 4'e eşittir ve bundan sonra √n hep öndedir.

1.1.2.6Hızlı bilgisayar mı, iyi algoritma mı?

Yavaş bir programı hızlandırmanın iki yolu vardır: daha hızlı bir bilgisayar almak ya da daha iyi bir algoritma bulmak. Büyüme tablosu, bu iki yolun etkisinin çok farklı olduğunu gösterir.

Daha hızlı bir bilgisayar, her işlemi daha kısa sürede yapar. Bu, T(n)'deki sabit katsayıyı küçültmekle aynıdır. Bin kat hızlı bir makine, her algoritmayı bin kat hızlandırır. Ama büyüme biçimini değiştirmez. Daha iyi bir algoritma ise büyüme hızını değiştirir. Bir milyon öğede n² işlem yapan bir sıralama yerine n log n işlem yapan bir sıralama kullanmak, süreyi 16,7 dakikadan 20 milisaniyeye indirir. Bu yaklaşık elli bin katlık bir kazançtır ve n büyüdükçe daha da artar.

Aynı karşılaştırma ters yönden de yapılabilir: belirli bir sürede çözülebilecek en büyük girdi ne kadardır? Tablo 1.1.3, saniyede 10⁹ işlem yapan bir bilgisayarın bir saniyede çözebileceği en büyük n değerlerini verir.

Şimdi bilgisayarın bin kat hızlandığını düşünelim. Doğrusal algoritmada çözülebilen girdi de bin kat büyür. Karesel algoritmada yalnız √1000 ≈ 31,6 kat, kübik algoritmada 10 kat büyür. Üstel algoritmada ise 2¹⁰ ≈ 1000 olduğu için n yalnız 10 artar: 29'dan 39'a. Bin kat hızlı bir makine, üstel bir algoritmaya on öğe daha işleme imkânı verir. Bu yüzden algoritma tasarımında asıl kazanç, donanımdan değil, büyüme hızını düşüren fikirlerden gelir.

1.1.3Karmaşıklık örnekleri

Büyüme tablosundaki her satırın arkasında gerçek algoritmalar vardır. Bu kesimde her sınıftan kısa bir Java kodu incelenir. Her kod için aynı soru sorulur: girdi boyutu n nedir, hangi işlem sayılır ve bu işlem n'ye bağlı olarak kaç kez yapılır? Kodların çoğu satır satır izlenir ve ara değerleri bir tabloda verilir.

1.1.3.1Sabit zaman: ilk öğeyi yazdırma

En hızlı algoritmalar, girdi ne kadar büyük olursa olsun aynı sayıda işlem yapanlardır. Bir dizinin ilk öğesini yazdıran metot bu türdendir.

void ilkElemaniYazdir(int[] dizi) {
  if (dizi.length > 0)
    System.out.println("İlk eleman: "
                     + dizi[0]);
  else
    System.out.println("Dizi boş");
}

Metot önce dizinin boş olup olmadığını dizi.length > 0 koşuluyla sınar. Dizi boş değilse dizi[0] hücresine erişip değeri yazar; boşsa “Dizi boş” iletisini yazar. Java'da bir dizinin uzunluğu dizi nesnesinde saklanır; length değerini okumak öğeleri saymayı gerektirmez. Dizinin herhangi bir hücresine erişmek de, hücrenin adresi başlangıç adresinden doğrudan hesaplandığı için tek adımdır.

Böylece dizi ister 10 öğeli, ister 10 milyon öğeli olsun, metot bir karşılaştırma, bir dizi erişimi ve bir yazdırma yapar. Örneğin {5, 8, 12, 4} dizisiyle çağrıldığında “İlk eleman: 5”, boş diziyle çağrıldığında “Dizi boş” yazar. İşlem sayısı n'den bağımsızdır: T(n) = O(1).

O(1) “tek işlem” demek değildir. Üç işlem yapan bir metot da, bin işlem yapan bir metot da, bu sayı n'ye bağlı değilse sabit zamanlıdır. Önemli olan, girdi büyüdüğünde işlem sayısının değişmemesidir.

1.1.3.2Doğrusal zaman: en büyük öğeyi bulma

Sırasız bir dizinin en büyük öğesini bulmak için her öğeye en az bir kez bakmak gerekir. Bakılmayan bir öğe, en büyük öğe olabilir. Sunumdaki enBuyukBul metodu bu işi tek geçişte yapar.

Integer enBuyukBul(int[] dizi) {
  if (dizi.length == 0)
    return null;            // dizi boşsa
  int enBuyuk = dizi[0];
  for (int eleman : dizi)
    if (eleman > enBuyuk)
      enBuyuk = eleman;
  return enBuyuk;
}

Metodun dönüş tipi int değil Integer'dır. Bunun nedeni boş dizi durumudur: boş bir dizinin en büyük öğesi yoktur ve metot bunu null döndürerek bildirir. int tipi null değeri alamaz; Integer ise bir nesne referansıdır ve alabilir.

Dizi boş değilse enBuyuk değişkeni ilk öğeyle başlatılır. Ardından for (int eleman : dizi) döngüsü dizinin bütün öğelerini sırayla gezer. Bu “her biri için” biçimindeki döngü, indis kullanmadan dizinin öğelerini baştan sona verir; ilk öğe de bu gezintiye dahildir. Her öğe enBuyuk ile karşılaştırılır. Öğe daha büyükse enBuyuk güncellenir. Döngü bittiğinde enBuyuk, o ana kadar görülen bütün öğelerin en büyüğüdür; döngü bütün diziyi gezdiği için de dizinin en büyüğüdür.

Tablo 1.1.4, metodun {5, 8, 12, 4} dizisindeki çalışmasını verir; Şekil 1.1.2 aynı izlemeyi sunumdaki şekille gösterir.

Metot dört öğeli dizide dört karşılaştırma yapar ve 12 döndürür. Genel olarak n öğeli dizide tam n karşılaştırma yapılır; bu sayı dizinin içeriğine bağlı değildir. Güncelleme sayısı ise içeriğe bağlıdır. Dizi azalan sıradaysa ({9, 5, 3, 2}) hiç güncelleme olmaz. Artan sıradaysa ({2, 3, 5, 9}) her öğe öncekinden büyük olduğu için n − 1 güncelleme yapılır. Her iki durumda da toplam iş n ile orantılıdır: T(n) = Θ(n).

Metodun kullandığı ek bellek enBuyuk ve eleman değişkenlerinden ibarettir. Dizi ne kadar büyük olursa olsun bu iki değişken yeter. Bu yüzden alan karmaşıklığı O(1)'dir. Girdi dizisinin kendisi alan hesabına katılmaz; alan karmaşıklığı algoritmanın girdiye ek olarak ayırdığı belleği ölçer.

1.1.3.3Karekök zaman: asallık testi

Bir n sayısının asal olup olmadığını anlamanın en doğrudan yolu, 2'den n − 1'e kadar her sayının n'yi bölüp bölmediğine bakmaktır. Bu yöntem n − 2 bölme yapar; 97 için 95 bölme gerekir. Ama bu bölmelerin çoğu gereksizdir. Aşağıdaki teorem, aramanın çok daha erken bitirilebileceğini söyler.

Teoremin karşıt tersi şunu söyler: √n'e kadar hiçbir bölen yoksa n asaldır. Örneğin 91 = 7 · 13'te küçük çarpan 7'dir ve 7 ≤ √91 ≈ 9,5'tir. Büyük çarpan 13'e hiç bakmaya gerek yoktur; 7 bulunduğunda sayının bileşik olduğu anlaşılır.

İkinci bir tasarruf daha yapılabilir. 2'den büyük bir çift sayı 2'ye bölündüğü için asal olamaz. Tek bir sayı ise hiçbir çift sayıya bölünemez, çünkü çift bir bölen sayıyı da çift yapardı. Bu yüzden önce sayının çift olup olmadığına bakılır; tek sayılarda ise yalnız tek bölenler denenir. Sunumdaki asalMi metodu bu iki fikri birleştirir.

boolean asalMi(int n) {
  if (n <= 1)
    return false;
  else if (n == 2)
    return true;
  else if (n % 2 == 0)
    return false;
  int kokN = (int) Math.sqrt(n) + 1;
  for (int i = 3; i < kokN; i += 2)
    if (n % i == 0)
      return false;
  return true;
}

Metodun ilk üç dalı özel durumları ayırır. 1 ve daha küçük sayılar tanım gereği asal değildir. 2, tek çift asal sayıdır. 2'den büyük çift sayılar asal değildir. Bu üç dal döngüye girilmeden sonuç döndürür.

Tek sayılar için kokN = (int) Math.sqrt(n) + 1 hesaplanır. Math.sqrt karekökü double olarak verir; (int) dönüşümü kesirli kısmı atar ve ⌊√n⌋ değerini bırakır. Döngü koşulu i < kokN, yani i ≤ ⌊√n⌋ olduğu için √n'in tam kısmı da denenir. Döngü 3'ten başlar ve i += 2 ile yalnız tek sayıları dener. Bir bölen bulunursa metot hemen false döndürür. Döngü bölen bulamadan biterse sayı asaldır ve metot true döndürür.

Kaç bölme yapılır? En kötü durum, sayının asal olduğu durumdur, çünkü o zaman döngü sonuna kadar çalışır. Döngü 3'ten √n'e kadar ikişer ikişer ilerler. Bu aralıkta yaklaşık √n / 2 tek sayı vardır. Sabit katsayı 1/2 atıldığında T(n) = O(√n) bulunur. Birkaç somut değer bu sayıyı doğrular:

• n = 97: ⌊√97⌋ = 9; denenen bölenler 3, 5, 7, 9: 4 bölme. 2'den 96'ya kadar her sayı denenseydi 95 bölme gerekirdi.
• n = 1.000.000.007 (asal): √n ≈ 31.622,8; denenen tek sayılar 3, 5, …, 31.621: 15.810 bölme. Basit yöntem ise yaklaşık bir milyar bölme yapardı.

Sayı bileşikse döngü genellikle çok daha erken biter. 221 için ⌊√221⌋ = 14 ve kokN = 15'tir; 3, 5, 7, 9, 11 bölmez, 13 böler (221 = 13 · 17) ve metot 6 bölmeden sonra false döndürür.

1.1.3.4Kod izleme: asalMi(97)

Sunumun izleme slaytı, asalMi(97) çağrısını satır satır yürütür. Tablo 1.1.5 bu izlemenin değişken değerlerini, Şekil 1.1.3 ise başlangıçtaki ve sondaki durumu gösterir.

İzlemede dikkat çeken nokta, i = 11 adımıdır. i += 2 artırması 9'dan sonra i'yi 11 yapar. Döngü koşulu 11 < 10 yanlış olduğu için gövde çalışmaz; 11 hiç denenmez. 10'dan büyük bir tek sayıyı denemeye de gerek yoktur, çünkü 97'nin √97'den büyük bir böleni olsaydı, Teorem 1.1.1 gereği küçük bir böleni de olurdu ve o bölen zaten denenmiş olurdu.

1.1.3.5Girdi boyutu: sayının değeri mi, uzunluğu mu?

Asallık testinde girdi boyutu olarak n sayısının değeri alındı ve süre O(√n) bulundu. Bu ilk bakışta doğrusal süreden bile iyi görünür. Ama bir sayının bilgisayardaki büyüklüğü, değeriyle değil, kaç bitle yazıldığıyla ölçülür. 1.000.000.007 sayısı bir milyar değerindedir, ama yalnız 30 bitle yazılır.

Sayının bit uzunluğu b olsun. O zaman n yaklaşık 2^b'dir ve

√n ≈ √(2^b) = 2^b/2

bulunur. Yani bölme sayısı, bit uzunluğuna göre üstel büyür. Sayıya bir bit eklemek değerini iki katına, bölme sayısını ise yaklaşık √2 ≈ 1,41 katına çıkarır. 30 bitlik bir sayı için 15.810 bölme kolaydır. Kriptografide kullanılan 1024 bitlik bir sayı için ise 2⁵¹² mertebesinde bölme gerekir; bu, büyüme tablosundaki “evrenin yaşından çok” satırına düşer.

Bu gözlem, karmaşıklık hesabında girdi boyutunun dikkatle seçilmesi gerektiğini gösterir. Bir dizi işleyen algoritmada öğe sayısı doğal bir ölçüdür. Tek bir sayıyla çalışan algoritmalarda ise iki ölçü çok farklı sonuç verir. Karmaşıklık kuramı, girdi boyutunu her zaman girdiyi yazmak için gereken bit sayısı olarak alır. Değere göre polinom, ama bit uzunluğuna göre üstel olan bu tür sürelere sözde-polinom (pseudo-polynomial) süre denir. Büyük sayıların asallığını hızla sınayan yöntemler bu yüzden deneme bölmesinden tamamen farklı fikirlere dayanır.

1.1.3.6Kübik zaman: matris çarpımı

İki matrisin çarpımı, bilimsel hesaplamadan bilgisayar grafiğine ve yapay sinir ağlarına kadar birçok alanda temel işlemdir. n × n boyutlu A = [a_ij] ve B = [b_ij] matrislerinin çarpımı C = A · B'nin her öğesi şu formülle tanımlanır:

c_ij = Σ_k=1..n a_ik · b_kj   (i, j = 1, 2, …, n)

Yani c_ij, A'nın i. satırı ile B'nin j. sütununun karşılıklı öğelerinin çarpımlarının toplamıdır. Sunumdaki örnekte

bulunur. Örneğin c₁₁ = 1 · 5 + 2 · 7 = 19, c₂₁ = 3 · 5 + 4 · 7 = 43'tür. Bu tanım doğrudan üç iç içe döngüye dönüşür:

int[][] matrisCarp(int[][] A, int[][] B) {
  int n = A.length, m = B[0].length, p = B.length;
  int[][] sonuc = new int[n][m];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      int eleman = 0;
      for (int k = 0; k < p; k++)
        eleman += A[i][k] * B[k][j];
      sonuc[i][j] = eleman;
    }
  return sonuc;
}

Kod yalnız kare matrislerle sınırlı değildir. n, A'nın satır sayısıdır; m, B'nin sütun sayısıdır; p ise B'nin satır sayısıdır ve A'nın sütun sayısına eşit olmalıdır. Sonuç n × m boyutundadır. Java'da kod, matrisin indislerini 0'dan başlatır; formüldeki 1'den başlayan indislerle arada bir kayma vardır, ama hesap aynıdır.

Dış iki döngü sonuç matrisinin her (i, j) hücresini bir kez ziyaret eder. Her hücre için eleman sıfırlanır, en içteki döngü p çarpım toplar ve sonuç sonuc[i][j]'ye yazılır. En içteki satır eleman += A[i][k] * B[k][j] toplam n · m · p kez çalışır. Kare matrislerde n = m = p olduğu için bu sayı n³'tür:

T(n) = n · n · n = n³ çarpma  ⇒  T(n) = Θ(n³)

Gerekçe kısaca şudur: sonuçta n² öğe vardır ve her öğe n çarpma gerektirir. n = 100 için bir milyon, n = 200 için sekiz milyon çarpma yapılır. n'nin iki katına çıkması süreyi sekiz katına çıkarır; kübik büyümenin işareti budur. Sonuç matrisi n² hücre tuttuğu için alan karmaşıklığı Θ(n²)'dir.

Bu düz yöntem matris çarpımının en hızlı yolu değildir. Böl ve fethet fikriyle çalışan Strassen algoritması aynı işi yaklaşık n^2,81 çarpmayla yapar. Ama düz yöntem hem en anlaşılır olanıdır hem de küçük ve orta boy matrislerde pratikte hâlâ çok kullanılır.

1.1.3.7Kod izleme: 2 × 2 matris çarpımı

matrisCarp, sunumdaki 2 × 2 matrislerle çağrıldığında n = m = p = 2 olur ve sonuç 2 × 2 sıfır matrisi olarak oluşturulur. Tablo 1.1.6 her çarpmadan sonraki değişken değerlerini verir.

İzleme sonunda sonuc = [[19, 22], [43, 50]] döner ve tam 8 = 2³ çarpma yapılmış olur. Tablodaki desen genel durumu da gösterir: i ve j her sonuç hücresini bir kez seçer, k ise her seçimde n değer alır. 3 × 3 matrislerde aynı sayım 3³ = 27 çarpma verir.

1.1.3.8Faktöriyel zaman: bütün permütasyonlar

Permütasyon sayısının neden n! olduğu, sıralamanın konum konum kurulmasıyla görülür. İlk konuma n öğeden herhangi biri konabilir. İkinci konum için geriye n − 1 seçenek kalır, üçüncüsü için n − 2, ve böyle devam eder. Son konuma kalan tek öğe yerleşir. Seçenekler çarpılınca n! elde edilir. Üç öğe için 3 · 2 · 1 = 6 permütasyon vardır: 123, 132, 213, 231, 321, 312.

Bazı problemlerin en doğrudan çözümü bütün permütasyonları tek tek denemektir. Örneğin bir gezginin n şehri en kısa toplam yolla dolaşma sırası, bütün sıralar denenerek bulunabilir. Sunumdaki permutasyon metodu, bir dizinin bütün permütasyonlarını yazdırır.

void permutasyon(int[] dizi, int k) {
  if (k == dizi.length) {          // bir permütasyon hazır
    System.out.println(Arrays.toString(dizi));
    return;
  }
  for (int i = k; i < dizi.length; i++) {
    takas(dizi, k, i);             // i. elemanı k. konuma al
    permutasyon(dizi, k + 1);      // geri kalanları diz
    takas(dizi, k, i);             // eski hâline getir
  }
}

Metot özyinelemelidir ve k parametresi, dizinin hangi konumunun doldurulmakta olduğunu söyler. 0'dan k − 1'e kadar olan konumlar yerleşmiştir; k'den sona kadar olan öğeler ise henüz sıralanmamıştır.

• Taban durum: k == dizi.length olduğunda bütün konumlar dolmuştur. Dizi o anda bir permütasyondur ve yazdırılır.
• Özyinelemeli adım: k. konuma sırayla k, k + 1, …, son konumdaki öğeler getirilir. Bunun için takas(dizi, k, i) ile i. öğe k. konuma alınır. Ardından permutasyon(dizi, k + 1) geri kalan konumları aynı yolla doldurur.
• Geri alma: özyinelemeli çağrı döndükten sonra ikinci takas diziyi eski hâline getirir. Böylece döngünün bir sonraki turu, k. konumdan sonraki öğelerin özgün sırasıyla başlar.

Kodda kullanılan takas yardımcı metodu, dizinin iki konumundaki değerleri yer değiştirir: int t = dizi[a]; dizi[a] = dizi[b]; dizi[b] = t;. Arrays.toString ise diziyi [1, 2, 3] biçiminde metne çevirir ve java.util.Arrays sınıfındandır.

Çıkan sıranın 123, 132, 213, 231, 321, 312 olduğuna dikkat edilmeli. Bu, sözlük sırası değildir: 312 ile 321'in yeri terstir. Takas yöntemi her permütasyonu bir kez üretir, ama sözlük sırasını korumaz.

Kaç işlem yapılır? Yazılan satır sayısı tam n!'dir. Her satırda Arrays.toString n öğeyi metne çevirir. Bu yüzden toplam iş Θ(n · n!)'dir. Ara düğümlerdeki çağrılar bu sayıyı değiştirmez: çağrı sayısı n!'in sabit katıdır (yaklaşık e · n! ≈ 2,72 · n!). Bu sınıf kısaca “O(n!) sınıfı” diye anılır. Tablo 1.1.7, faktöriyelin ne kadar hızlı büyüdüğünü gösterir.

On öğenin permütasyonları bir göz açıp kapayıncaya kadar üretilir; yirmi öğeninkiler ise bir insan ömrü sürer. Bütün permütasyonları denemek, bu yüzden yalnız çok küçük girdilerde kullanılabilen bir yöntemdir. Daha büyük girdiler için geri izleme ve dal sınır gibi teknikler aramanın büyük kısmını budar; ya da problemin yapısından yararlanan bambaşka bir algoritma aranır.

1.1.3.9Üstel zaman: saf özyinelemeli Fibonacci

Fibonacci dizisi 0 ve 1 ile başlar; sonraki her terim önceki iki terimin toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Tanım şöyle yazılır:

F(0) = 0,   F(1) = 1,   F(n) = F(n − 1) + F(n − 2)  (n ≥ 2)

Bu tanım özyinelemelidir ve doğrudan bir Java metoduna dönüştürülebilir. Sunumdaki kodun ilk metodu fib bunu yapar; ikinci metot fibBellek ise bir sonraki alt kesimin konusudur.

long fib(int n) {           // saf özyineleme
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

long[] bellek = new long[N + 1]; // 0: yok
long fibBellek(int n) {     // bellekleme
  if (n <= 1) return n;
  if (bellek[n] == 0)
    bellek[n] = fibBellek(n - 1) + fibBellek(n - 2);
  return bellek[n];
}

fib metodu tanımın birebir kopyasıdır. n ≤ 1 taban durumdur ve n değerini döndürür: F(0) = 0, F(1) = 1. Aksi hâlde metot kendini iki kez çağırır ve sonuçları toplar. Dönüş tipi long'dur, çünkü Fibonacci sayıları çabuk büyür: F(47) artık int'e sığmaz.

Kod kısa ve doğrudur, ama çok yavaştır. Nedeni Şekil 1.1.5'deki çağrı ağacında açıkça görülür. fib(5), fib(4) ve fib(3)'ü çağırır. fib(4) de kendi içinde yine fib(3)'ü çağırır. Böylece fib(3) iki kez, baştan sona ayrı ayrı hesaplanır. Aşağı indikçe tekrar artar: fib(2) üç kez, fib(1) beş kez çağrılır.

Kaç çağrı yapılır? fib(n)'in yaptığı toplam çağrı sayısına Ç(n) diyelim. Taban durumlarda yalnız çağrının kendisi vardır: Ç(0) = Ç(1) = 1. Öteki durumlarda çağrının kendisine iki alt çağrının sayıları eklenir:

Ç(n) = 1 + Ç(n − 1) + Ç(n − 2)

Bu bağıntı, Fibonacci bağıntısına çok benzer. Değerleri sırayla hesaplanırsa Ç(0..6) = 1, 1, 3, 5, 9, 15, 25 bulunur. Tümevarımla Ç(n) = 2F(n + 1) − 1 olduğu gösterilebilir. n = 5 için 2 · 8 − 1 = 15, n = 30 için 2 · 1.346.269 − 1 = 2.692.537 çağrı. fib(40) ise 331.160.281 çağrı yapar; bu, 40'ıncı Fibonacci sayısını bulmak için üç yüz milyondan fazla metot çağrısı demektir.

Büyüme hızı. Her çağrı en fazla iki çağrı doğurur ve ağacın derinliği en fazla n'dir. Derinliği n olan bir ikili ağaçta en fazla 2ⁿ düğüm bulunabilir. Bu yüzden T(n) = O(2ⁿ)'dir. Gerçek büyüme biraz daha yavaştır, çünkü sağ dallar sol dallardan kısadır. Ç(n), F(n) ile aynı hızda büyür ve F(n) her adımda yaklaşık altın oran φ = (1 + √5) / 2 ≈ 1,618 katına çıkar. Kesin sınıf Θ(φⁿ) = Θ(1,618ⁿ)'dir. Taban 2 değil 1,618 olsa da büyüme yine üsteldir: n bir artınca süre yaklaşık yüzde 62 artar, n on artınca yüz yirmi kattan fazla artar.

1.1.3.10Bellekleme: aynı alt problemi bir kez çözmek

Saf Fibonacci kodunun yavaşlığı, aynı alt problemin defalarca çözülmesinden gelir. fib(30) hesaplanırken F(2) yüz binlerce kez yeniden bulunur. Oysa F(2) her seferinde aynı değerdir. Bir kez hesaplanıp bir yere yazılsa, sonraki her istekte oradan okunabilir.

Sunumdaki fibBellek metodu, bellek adlı bir long dizisi kullanır. Dizinin k. hücresi F(k)'yi tutar. Java'da yeni bir long dizisinin bütün hücreleri 0 ile başlar. 0 değeri burada “henüz hesaplanmadı” anlamında kullanılır. Bu seçim güvenlidir, çünkü k ≥ 1 için F(k) hiçbir zaman 0 değildir; F(0) = 0 ise taban durumda ayrıca ele alınır. N sabiti, hesaplanacak en büyük n'dir ve dizi N + 1 hücreyle ayrılır.

Metot önce taban durumu sınar. Sonra bellek[n] == 0 ise, yani F(n) daha önce hesaplanmamışsa, onu iki özyinelemeli çağrıyla hesaplar ve diziye yazar. Her durumda sonucu diziden döndürür. Böylece her F(k) yalnız bir kez hesaplanır.

Kaç çağrı? n ≥ 1 için fibBellek(n), 2'den n'ye kadar her k için tam iki alt çağrı yapar: biri hesaplanacak F(k − 1) için, öteki bellekten dönecek ya da taban durum olan F(k − 2) için. İlk çağrı da eklenince toplam 2(n − 1) + 1 = 2n − 1 çağrı bulunur. n = 5 için 9, n = 30 için 59 çağrı. Saf yöntemin 2.692.537 çağrısıyla karşılaştırıldığında fark yaklaşık kırk beş bin kattır. Çalışma süresi O(n)'ye iner.

Bu kazancın bir bedeli vardır: bellek dizisi n + 1 hücre tutar. Ayrıca özyineleme n derinliğe indiği için çağrı yığını da O(n) yer kaplar. Bellekleme, zamandan kazanmak için bellek harcar. Bu takas, algoritma tasarımında sık görülür. Aynı fikrin aşağıdan yukarı, döngüyle yazılmış biçimi dinamik programlamanın temelidir.

1.1.4Öklid algoritması

Öklid algoritması, bilinen en eski algoritmalardan biridir. Yunan matematikçi Öklid, MÖ 300 dolaylarında yazdığı Öğeler adlı eserinde bu yöntemi anlatır. Algoritma yaklaşık iki bin üç yüz yıldır kullanılır ve bugün de kriptografiden kesirlerin sadeleştirilmesine kadar birçok yerde iş görür. Kısa, doğruluğu kolay kanıtlanan ve şaşırtıcı ölçüde hızlı bir algoritma olduğu için analiz öğrenmeye de çok uygundur.

1.1.4.1EBOB ve Öklid'in fikri

EBOB'u bulmanın en doğrudan yolu, min(a, b)'den başlayıp aşağı doğru her sayıyı denemektir. İki sayıyı da bölen ilk sayı EBOB'dur. Bu yöntem en kötü durumda min(a, b) kadar deneme yapar: O(min(a, b)). Bir başka yol, iki sayıyı asal çarpanlarına ayırıp ortak çarpanları çarpmaktır; ama büyük sayıları çarpanlarına ayırmak zaten zor bir problemdir.

Öklid'in fikri, büyük sayıyı küçüğe bölüp kalanla devam etmektir. Temel eşitlik şudur:

ebob(a, b) = ebob(b, a mod b),    ebob(a, 0) = a

Burada a mod b, a'nın b'ye bölümünden kalandır. Algoritma üç adımla anlatılır:

1. Büyük sayı küçüğe bölünür ve kalan bulunur.
2. Kalan sıfır olana kadar işlem (bölen, kalan) çiftiyle tekrarlanır.
3. Kalan sıfır olduğunda son bölen EBOB'dur.

Eşitlik doğrudan özyinelemeli bir metoda dönüşür:

int ebob(int a, int b) {
  if (b == 0)
    return a;
  return ebob(b, a % b);
}

b == 0 taban durumdur; ebob(a, 0) = a, çünkü her sayı 0'ı böler ve a'yı bölen en büyük sayı a'nın kendisidir. Aksi hâlde metot kendini (b, a % b) ile çağırır. Java'da % işleci kalanı verir.

Metot, a < b olduğunda da doğru çalışır. Örneğin ebob(650, 1599) çağrısında 650 % 1599 = 650'dir ve ilk çağrı ebob(1599, 650) olur. Sayılar kendiliğinden yer değiştirir; bedeli yalnız bir fazla bölmedir.

1.1.4.2Algoritma neden doğru?

Teorem, her özyinelemeli çağrının EBOB'u koruduğunu söyler. Sonluluk da kolay gösterilir. Her çağrıda ikinci argüman b'den a mod b'ye geçer ve a mod b < b'dir. Negatif olmayan tam sayılar sonsuza kadar küçülemeyeceği için ikinci argüman sonunda 0 olur ve taban duruma ulaşılır. Taban durumda döndürülen a, doğru EBOB'dur. Böylece algoritma hem durur hem de doğru sonuç verir.

1.1.4.3Kod izleme: ebob(1599, 650)

Sunumun izleme örneği ebob(1599, 650)'dir. Tablo 1.1.8 her çağrıdaki bölmeyi verir.

Beş bölmeden sonra kalan 0 olur ve altıncı çağrı taban durumdur. 13 değeri, hiç değişmeden bütün çağrılardan geri döner; her çağrı yalnız alt çağrısının sonucunu iletir. Sonuç ebob(1599, 650) = 13'tür. Çarpanlara ayırma da bunu doğrular: 1599 = 3 · 13 · 41, 650 = 2 · 5² · 13; tek ortak çarpan 13'tür.

Sunumdaki şekiller algoritmanın geometrik bir yorumunu verir. a × b boyutlu bir dikdörtgenden kenarı b olan kareler kesilir. Kaç kare sığarsa (q tane) kesilir ve geriye b × r boyutlu bir şerit kalır. Aynı işlem bu şeride uygulanır. Şerit sonunda karelere tam bölündüğünde son karenin kenarı EBOB'dur. Şekil 1.1.6 bu sürecin üç adımını gösterir.

Son gözlem EBOB'un anlamını da açıklar. Kenarı 13 olan kareler 39 × 13'ü döşer. Bu kareler 52 × 39'u da döşer, çünkü 52 de 39 da 13'ün katıdır. Geriye doğru her adımda aynı akıl yürütme işler ve sonunda 1599 × 650 dikdörtgeni de 123 × 50 tane 13 × 13 kareyle döşenir. Bu dikdörtgeni döşeyebilen en büyük kare budur.

Özyinelemeli çağrılar çağrı yığınında birikir. Taban duruma ulaşıldığında yığında altı çerçeve vardır: ebob(1599, 650)'den ebob(13, 0)'a kadar. Bu derinlik bölme sayısıyla orantılı olduğu için özyinelemeli sürümün alan karmaşıklığı, bölme sayısıyla aynı mertebededir.