Karmaşıklık Analizi (Big-O)

Aynı işi yapan iki program düşün. İkisi de 1.000 elemanlık bir listeyi göz açıp kapayıncaya kadar işliyor. Liste 1.000.000 elemana çıktığında ise biri yine bir saniyenin altında bitirirken diğeri saatlerce çalışıyor. Aradaki farkı yaratan şey daha hızlı bir işlemci ya da daha akıllı bir derleyici değil; algoritmanın girdi büyüdükçe nasıl davrandığı.

Karmaşıklık analizi (complexity analysis), bu davranışı donanımdan, programlama dilinden ve ölçümdeki şanstan bağımsız olarak konuşmamızı sağlayan ortak dildir. "Bu fonksiyon O(n²)" dediğinde aslında "girdiyi iki katına çıkarırsan iş kabaca dört katına çıkar" demiş olursun. Bu yoldaki bütün veri yapısı ve algoritma dersleri, bir yapının hangi işlemde güçlü, hangisinde zayıf olduğunu bu dille anlatır; o yüzden ilk durağımız burası.

Bu dersin sonunda bir Go fonksiyonunun işlemlerini satır satır sayabilecek, sonucu Big-O, Big-Omega ve Big-Theta ile ifade edebilecek, döngülerden ve özyinelemeli fonksiyonlardan karmaşıklığı hızla çıkarabileceksin. En iyi, ortalama ve en kötü durumu ayırt etmeyi, alan karmaşıklığını hesaplamayı ve append'in neden "amortize O(1)" olduğunu göstermeyi öğreneceksin. Son olarak bir problemin kısıtlarına bakıp "bu yaklaşım bir saniyeye sığar mı?" sorusuna kabaca cevap verebileceksin.

Neden karmaşıklık analizi?

Kalın bir telefon rehberinde bir ismi aradığını düşün. İlk yöntem, ilk sayfadan başlayıp sayfaları tek tek çevirmek. İkinci yöntem, rehberi ortadan açmak; aradığın isim alfabede daha ilerideyse sağ yarıya, gerideyse sol yarıya geçmek ve bunu tekrarlamak. 1.000 sayfalık bir rehberde ilk yöntem en kötü durumda 1.000 sayfaya bakar, ikincisi yalnızca 10 sayfaya. Rehber 1.000.000 sayfa olsaydı ilk yöntem 1.000.000, ikincisi yaklaşık 20 bakış gerektirirdi. Girdi bin kat büyüdü; birinci yöntemin işi de bin kat arttı, ikincisininki ise yalnızca iki katına çıktı.

Peki neden kronometreyi alıp ölçmüyoruz? Ölçmek değerlidir, Go'da bunun için yerleşik benchmark desteği bile var (Test ve Benchmark). Ama tek başına yetmez:

• Sonuç donanıma bağlıdır. Aynı kod dizüstü bilgisayarında ve bir sunucuda farklı sürer.
• Sonuç girdiye bağlıdır. 100 elemanla yaptığın ölçüm, 10 milyon elemanda ne olacağını söylemez.
• Sonuç gürültülüdür. Arka plandaki süreçler, işlemci önbelleğinin durumu ve çöp toplayıcının ne zaman devreye girdiği süreyi oynatır.

Karmaşıklık analizi ise tek bir soruya odaklanır: girdi boyutu n büyüdükçe yapılan iş nasıl büyür? Bu soruyu henüz tek satır kod çalıştırmadan, kâğıt üzerinde yanıtlayabilir ve iki algoritmayı adil biçimde karşılaştırabilirsin. Ölçüm ile analiz birbirinin rakibi değil, tamamlayıcısıdır: analiz hangi yaklaşımın ölçekleneceğini söyler, ölçüm de sabit çarpanların gerçek dünyadaki etkisini gösterir.

İşlem sayma ve büyüme hızı

Analize başlamadan önce iki kavramı netleştirelim.

Girdi boyutu (n), problemin büyüklüğünü ölçen sayıdır: bir dilim (slice) için eleman sayısı, bir string için bayt ya da karakter sayısı, bir graf için düğüm ve kenar sayısı. Birbirinden bağımsız birden fazla boyut varsa her birine ayrı bir harf veririz (n ve m gibi).

Temel işlem, süresi girdi boyutuna bağlı olmayan adımdır: atama, karşılaştırma, aritmetik işlem, indeksle dilim elemanına erişim, fonksiyondan dönüş. Her birinin sabit bir sürede çalıştığını varsayarız. Bu bir basitleştirme; yine de büyüme hızını anlamak için fazlasıyla yeterli.

Bir fonksiyonu satır satır saymak

Bir dilimdeki sayıları toplayan şu fonksiyona bakalım. Yorumlar, n elemanlı bir dilim için her satırın kaç kez çalıştığını gösteriyor:

func sum(nums []int) int {
	total := 0               // 1 kez
	for _, v := range nums { // gövde n kez çalışır
		total += v // n kez
	}
	return total // 1 kez
}

Toplam iş T(n) = 1 + n + 1 = n + 2. Döngünün kendi kontrolünü de (sıradaki elemana geçmek, dilimin bitip bitmediğine bakmak) sayarsan belki 3n + 2 bulursun. Hangisini bulduğunun önemi yok, çünkü iki durumda da iş n ile doğru orantılı büyüyor: n iki katına çıkınca iş de yaklaşık iki katına çıkıyor. Birazdan göreceğin Big-O gösterimi tam olarak bu tür sayma farklarını görmezden gelmek için var.

Şimdi bir dilimde tekrar eden eleman olup olmadığını kontrol eden bir fonksiyona bakalım:

func hasDuplicate(nums []int) bool {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] == nums[j] { // asıl iş: karşılaştırma
				return true
			}
		}
	}
	return false
}

En kötü durumda, yani hiç tekrar yoksa, kaç karşılaştırma yapılır? i = 0 iken iç döngü n − 1 kez döner, i = 1 iken n − 2 kez ve bu sayı son turda 0'a iner:

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

n = 1.000 için bu 499.500 karşılaştırma demek; n = 1.000.000 için yaklaşık 500 milyar. sum fonksiyonunda n'yi bin katına çıkarmak işi de bin katına çıkarıyordu. Burada ise işi yaklaşık bir milyon katına çıkarıyor.

Büyümeyi gözünle gör

Formüller soyut kalabilir. Aşağıdaki program, sık karşılaşacağın dört döngü kalıbının kaç adım attığını gerçekten sayıyor. Her fonksiyon, en içteki satırın kaç kez çalıştığını döndürüyor:

package main

import "fmt"

// Tek döngü: n adım.
func linear(n int) int {
	steps := 0
	for range n {
		steps++
	}
	return steps
}

// i her adımda ikiye katlanır: yaklaşık log₂ n adım.
func logarithmic(n int) int {
	steps := 0
	for i := 1; i < n; i *= 2 {
		steps++
	}
	return steps
}

// Dışta n, içte log₂ n adım: n·log₂ n.
func linearithmic(n int) int {
	steps := 0
	for range n {
		for j := 1; j < n; j *= 2 {
			steps++
		}
	}
	return steps
}

// i < j olan bütün (i, j) çiftleri: n(n-1)/2 adım.
func quadratic(n int) int {
	steps := 0
	for i := range n {
		for j := i + 1; j < n; j++ {
			steps++
		}
	}
	return steps
}

func main() {
	fmt.Printf("%8s %8s %10s %12s %14s\n", "n", "log n", "n", "n log n", "n(n-1)/2")
	for _, n := range []int{10, 100, 1_000, 10_000} {
		fmt.Printf("%8d %8d %10d %12d %14d\n",
			n, logarithmic(n), linear(n), linearithmic(n), quadratic(n))
	}
}

n    log n          n      n log n       n(n-1)/2
      10        4         10           40             45
     100        7        100          700           4950
    1000       10       1000        10000         499500
   10000       14      10000       140000       49995000

Tabloyu satır satır oku: n her seferinde 10 katına çıkıyor. log n sütunu her seferinde yalnızca 3-4 artıyor. n sütunu 10 katına, n log n sütunu 10 katından fazlasına (çünkü log n çarpanı da büyüyor), n(n-1)/2 sütunu ise 100 katına çıkıyor. n = 10'da aradaki fark önemsiz görünürken n = 10.000'de karesel döngü, doğrusal olandan yaklaşık 5.000 kat daha fazla adım atıyor.

"Büyüme hızı" dediğimiz şey tam olarak bu: tek bir n için kaç adım atıldığı değil, n büyüdükçe adım sayısının nasıl değiştiği. Pratik bir düşünme aracı olarak kendine şu soruyu sorabilirsin: "n iki katına çıkarsa iş ne olur?"

Big-O, Big-Omega ve Big-Theta

n + 2 ya da n(n − 1)/2 gibi tam formüller sayma biçimine bağlıdır ve çoğu zaman gereğinden fazla ayrıntı içerir. Bizim asıl istediğimiz, bir fonksiyonu büyüme sınıfına göre etiketlemek. Bunun için üç gösterim kullanılır. Hepsinde f(n) incelediğimiz maliyet fonksiyonu, g(n) ise onu karşılaştırdığımız basit bir fonksiyondur (n, n², log n gibi).

Big-O: üst sınır

Tanım: Pozitif bir c sabiti ve bir n₀ eşiği bulunabiliyorsa, öyle ki her n ≥ n₀ için f(n) ≤ c·g(n) oluyorsa, f(n) = O(g(n)) yazarız.

Sözle söylersek: "Yeterince büyük n'ler için f, g'nin sabit bir katını hiçbir zaman aşmaz." Küçük n'lerde ne olduğuyla ilgilenmeyiz (n₀ bunun için var), sabit çarpanlarla da ilgilenmeyiz (c bunun için var).

Örnek olarak f(n) = 3n + 5 fonksiyonunun O(n) olduğunu gösterelim. c = 4 seçersek 3n + 5 ≤ 4n eşitsizliği düzenlendiğinde 5 ≤ n olur. Yani c = 4 ve n₀ = 5 ile tanım sağlanır. Tabloda da görebilirsin:

n = 5'e kadar f(n) daha büyük; o noktadan sonra 4n hep önde. Tanım "bir noktadan sonra" dediği için baştaki birkaç değer sonucu değiştirmez.

Big-O bir üst sınır olduğu için 3n + 5 = O(n²) de teknik olarak doğrudur; n² de bir noktadan sonra 3n + 5'in hep üstünde kalır. Ama bu bilgi pek işe yaramaz, tıpkı "bu yolculuk bir yıldan kısa sürer" demek gibi. Bu yüzden Big-O yazarken her zaman en sıkı sınırı vermeye çalışırız.

Big-Omega: alt sınır

Tanım: Pozitif bir c sabiti ve bir n₀ eşiği bulunabiliyorsa, öyle ki her n ≥ n₀ için f(n) ≥ c·g(n) oluyorsa, f(n) = Ω(g(n)) yazarız.

Big-Omega, "en az bu kadar hızlı büyür" demenin yoludur. 3n + 5 = Ω(n), çünkü c = 3 seçersek her n ≥ 1 için 3n + 5 ≥ 3n olur.

Alt sınırlar özellikle "bu problem bundan daha hızlı çözülemez" türünden sonuçlarda kullanılır. Örneğin karşılaştırmaya dayalı her sıralama algoritmasının en kötü durumda Ω(n log n) karşılaştırma yapmak zorunda olduğu kanıtlanmıştır (Verimli Sıralama Algoritmaları).

Big-Theta: sıkı sınır

Tanım: Pozitif c₁ ve c₂ sabitleri ile bir n₀ eşiği bulunabiliyorsa, öyle ki her n ≥ n₀ için c₁·g(n) ≤ f(n) ≤ c₂·g(n) oluyorsa, f(n) = Θ(g(n)) yazarız. Başka bir deyişle f hem O(g) hem de Ω(g)'dir.

hasDuplicate'in karşılaştırma sayısı olan n(n − 1)/2'nin Θ(n²) olduğunu gösterelim:

• Üst sınır: n(n − 1)/2 ≤ n²/2 olduğundan c₂ = 1/2 her n ≥ 1 için çalışır.
• Alt sınır: n ≥ 2 iken n − 1 ≥ n/2 olur, dolayısıyla n(n − 1)/2 ≥ n²/4. Yani c₁ = 1/4 ve n₀ = 2.

Fonksiyon n²'nin dörtte biri ile yarısı arasına sıkışıyor; büyüme hızı tam olarak n² ile aynı.

Sabitleri ve küçük terimleri atma

Tanımdaki c ve n₀ sayesinde maliyet formüllerini birkaç basit kuralla sadeleştirebiliriz.

Sabit çarpanları at

5n, n/2 ve 1000n'in üçü de O(n)'dir; tanımdaki c sabiti bu çarpanları zaten yutar. Pratikteki gerekçe de güçlü: sabit çarpan donanıma, derleyiciye, hatta işlemleri nasıl saydığına göre değişir, ama büyüme sınıfı değişmez. Bu yüzden O(2n) ya da O(n/2) yerine doğrudan O(n) yazarız.

Baskın terimi tut

T(n) = n² + 100n + 1000 gibi bir formülde n büyüdükçe hangi terimin belirleyici olduğuna bakalım:

Küçük n'de 100n ve 1000 terimleri baskın görünüyor, ama n büyüdükçe n² diğerlerini ezip geçiyor. Analiz büyük n'lerle ilgilendiği için yalnızca baskın terimi tutarız: T(n) = O(n²). Terimleri karşılaştırırken şu sıralamayı akılda tutmak işini kolaylaştırır:

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

Ardışık blokları topla, iç içe blokları çarp

Kodun art arda gelen parçalarının maliyetleri toplanır, iç içe parçaların maliyetleri çarpılır. Bir fonksiyon önce dilimi bir kez gezip (O(n)) sonra iç içe iki döngüyle bütün çiftlere bakıyorsa (O(n) × O(n) = O(n²)), toplam O(n) + O(n²) olur ve baskın terim kuralıyla O(n²)'ye sadeleşir. Üç kat iç içe bağımsız döngü ise O(n³) verir.

Farklı girdilere farklı harfler ver

func commonCount(a, b []string) int {
	count := 0
	for _, x := range a {
		for _, y := range b {
			if x == y {
				count++
			}
		}
	}
	return count
}

Bu fonksiyon O(n²) değil, len(a) = n ve len(b) = m için O(n·m)'dir. İki boyutu tek harfe indirmek ciddi yanılgılara yol açar: a 10, b 1.000.000 elemanlıysa gerçek iş 10 milyon adımdır, oysa "O(n²)" demek n'nin hangisi seçildiğine göre ya 100 ya da 10¹² adım anlamına gelir. Aynı mantıkla iki ayrı döngü art arda geliyorsa sonuç O(n + m) olur ve hiçbir terim atılamaz, çünkü hangisinin büyük olduğunu bilmiyoruz.

Logaritmanın tabanını yazma

log₂ n ile log₁₀ n arasında yalnızca sabit bir çarpan fark vardır: log₂ n = log₁₀ n / log₁₀ 2 ≈ 3,32 · log₁₀ n. Sabit çarpanları attığımız için taban önemsizleşir ve kısaca O(log n) yazarız. Dikkat: bu kural üsler için geçerli değildir. 3ⁿ / 2ⁿ = 1,5ⁿ oranı sınırsızca büyüdüğü için O(2ⁿ) ile O(3ⁿ) farklı sınıflardır.

Yaygın karmaşıklık sınıfları

Karşına çıkacak algoritmaların büyük çoğunluğu birkaç tanıdık sınıfa düşer. Tablonun son sütunu kaba bir kurala dayanıyor: modern bir işlemci, Go gibi derlenen bir dilde saniyede kabaca 10⁸ basit işlem yapabilir. Bu kesin bir sayı değildir; işin niteliğine, bellek erişim desenine ve donanıma göre birkaç kat oynayabilir. Ama bir yaklaşımın rahatça sığıp sığmayacağını ya da tamamen imkânsız olup olmadığını anlamak için çok işe yarar.

Kuralın nasıl kullanıldığına bir örnek: bir problemde n en fazla 10⁵ ise O(n²) bir yaklaşım yaklaşık 10¹⁰ işlem eder ve bir saniyeye sığmaz. O(n log n) bir yaklaşım ise 10⁵ · 17 ≈ 1,7·10⁶ işlemle rahatça sığar. Kısıtlardan hedef karmaşıklığı çıkarmayı Problem Çözme Stratejileri dersinde ayrıntılı işleyeceğiz.

Sınıflar arasındaki farkın ne kadar çarpıcı olduğunu sayılarla da görelim:

2¹⁰⁰ ≈ 1,27·10³⁰ işlemi saniyede 10⁸ hızla yapmak yaklaşık 4·10¹⁴ yıl sürer; bu, evrenin yaşının on binlerce katı. Üstel algoritmalar bu yüzden yalnızca çok küçük girdilerde kullanılabilir.

Aşağıdaki grafikte bu sınıfların eğrilerini yan yana görebilirsin. n büyüdükçe eğrilerin nasıl ayrıştığına dikkat et: küçük n'lerde hepsi birbirine yakın, hatta bazıları yer değiştiriyor; n arttıkça n² ve 2ⁿ eğrileri ötekilerden hızla kopuyor.

Döngüleri ve iç içe döngüleri analiz etme

Kodun büyük kısmı döngülerden oluşur ve çoğu döngü birkaç kalıptan birine uyar. Her kalıpta sorulacak soru aynı: döngü değişkeni hangi değerleri alıyor ve döngü kaç kez dönüyor?

Sabit adımla ilerleyen döngü: O(n)

for i := 0; i < n; i++ döngüsü n kez döner. Adım 1 yerine 2 ya da 5 olsa bile (i += 5) dönüş sayısı n/5 olur; sabit çarpanı attığımızda yine O(n) kalır. Aynı şekilde for i := range n ve n elemanlı bir dilim üzerinde range de, gövde O(1) iş yaptığı sürece O(n)'dir.

Katlanarak ilerleyen döngü: O(log n)

for i := 1; i < n; i *= 2 döngüsünde i sırasıyla 1, 2, 4, 8, … değerlerini, yani k. adımda 2ᵏ⁻¹ değerini alır. Döngü i < n olduğu sürece devam ettiği için dönüş sayısı yaklaşık log₂ n olur. n = 20 için adımları izleyelim:

adım :  1   2   3   4   5
i    :  1   2   4   8  16   → sıradaki değer 32 ≥ 20, döngü biter

5 adım; log₂ 20 ≈ 4,32 → yukarı yuvarlanınca 5

Aynı akıl yürütme i /= 2 ile küçülen döngüler için de geçerli. Bir sayının basamaklarını for x > 0 { x /= 10 } ile saymak O(log n) sürer, çünkü n'nin basamak sayısı yaklaşık log₁₀ n'dir. İkili arama da her adımda arama aralığını yarıya indirdiği için O(log n)'dir (Arama Algoritmaları).

Bağımsız iç içe döngüler: O(n·m)

Dıştaki döngü n kez, içteki m kez dönüyorsa ve bu iki sayı birbirine bağlı değilse gövde n·m kez çalışır. n = m olduğunda bu O(n²) olur. Dıştaki döngü n kez dönüp içteki döngü her seferinde j *= 2 ile log₂ n adım atıyorsa, aynı çarpım kuralıyla O(n log n) elde edersin; verimli sıralama algoritmalarının ve birçok böl ve fethet algoritmasının sınıfı budur.

Bağımlı iç içe döngüler: n(n − 1)/2

İç döngünün sınırı dış döngünün değişkenine bağlıysa dönüş sayılarını tek tek toplamak gerekir. hasDuplicate'teki j := i + 1 kalıbını n = 5 için açalım:

i = 0 :  j = 1 2 3 4   → 4 adım
i = 1 :  j =   2 3 4   → 3 adım
i = 2 :  j =     3 4   → 2 adım
i = 3 :  j =       4   → 1 adım
i = 4 :  j =           → 0 adım
                         ────────
                         10 adım = 5·4/2

Şekle dikkat et: adımlar n × n'lik bir karenin köşegeninin üstünde kalan üçgeni dolduruyor. Üçgen karenin yaklaşık yarısı olduğundan toplam n²/2 civarında, yani Θ(n²). İç döngü j := 0; j < i biçiminde olsaydı üçgenin diğer yarısını doldururdu ve sonuç yine n(n − 1)/2 olurdu.

Aldatıcı bir örnek: geometrik seri

Şu döngünün karmaşıklığı nedir?

for i := 1; i < n; i *= 2 {
	for j := 0; j < i; j++ {
		// O(1) iş
	}
}

İlk refleks şöyle düşünmektir: "Dış döngü log n kez döner, iç döngü en fazla n kez; çarparsak O(n log n)." Bu bir üst sınır olarak yanlış değil, ama sıkı da değil. İç döngü her seferinde tam i kez dönüyor ve i değerleri 1, 2, 4, …, 2ᵏ (2ᵏ, n'den küçük en büyük ikinin kuvveti). Toplam:

1 + 2 + 4 + … + 2ᵏ = 2ᵏ⁺¹ − 1 < 2n

Yani döngünün tamamı O(n). Geometrik bir serinin toplamı, en büyük teriminin iki katını geçmez. Bunu sayarak doğrulayalım:

package main

import "fmt"

func main() {
	for _, n := range []int{16, 1_000, 1_000_000} {
		steps := 0
		for i := 1; i < n; i *= 2 {
			for j := 0; j < i; j++ {
				steps++
			}
		}
		fmt.Printf("n = %7d → %7d adım (2n = %7d)\n", n, steps, 2*n)
	}
}

n =      16 →      15 adım (2n =      32)
n =    1000 →    1023 adım (2n =    2000)
n = 1000000 → 1048575 adım (2n = 2000000)

Bu küçük gözlem aklında kalsın; birazdan append'in amortize maliyetini kanıtlarken tam olarak aynı seriyi kullanacağız.

Gizli döngüler: fonksiyon çağrıları

Bir satırın O(1) göründüğüne aldanma; çağırdığın fonksiyonun içinde bir döngü olabilir. for _, x := range a döngüsünün içinde slices.Contains(b, x) çağırmak tek döngü gibi görünür, ama Contains her seferinde b'yi baştan tarar ve toplam maliyet O(n·m) olur. b'nin elemanlarını önce bir kümeye (map[int]struct{}) koyarsan kurulum O(m), her arama ortalama O(1) olur ve toplam O(n + m)'e iner (Haritalar). Sık kullanılan bazı ifadelerin maliyetleri:

String birleştirme satırı önemli bir tuzağa işaret ediyor: bir döngüde result += part yapmak her turda o ana kadar biriken bütün metni yeniden kopyalar ve toplamda O(n²) bayt kopyalamaya yol açabilir. strings.Builder bu yüzden var (String, Byte ve Rune).

Özyinelemeli fonksiyonların analizi

Kendini çağıran bir fonksiyonun maliyetini bulmanın en sezgisel yolu özyineleme ağacı çizmektir: her çağrı bir düğüm, o çağrının yaptığı çağrılar da onun çocuklarıdır. Toplam iş, her düğümün kendi içinde yaptığı işin (özyinelemeli çağrılar hariç) toplamıdır. Özyinelemenin kendisini Özyineleme dersinde, yineleme bağıntılarını ve Master teoremini Böl ve Fethet dersinde ayrıntılı göreceksin. Burada en sık karşılaşılan dört şekli tanıyalım.

Tek dal: doğrusal zincir

return n * factorial(n-1) satırıyla kendini çağıran bir faktöriyel fonksiyonunda factorial(4) → factorial(3) → factorial(2) → factorial(1) zinciri oluşur. Ağaç aslında düz bir çizgidir: n çağrının her biri O(1) iş yapar, toplam O(n). Bunu yineleme bağıntısı (recurrence relation) olarak T(n) = T(n − 1) + O(1) diye yazarız.

Yarıya inen tek dal: O(log n)

İkili aramanın özyinelemeli sürümü her çağrıda aralığı yarıya indirip yalnızca tek bir çağrı yapar: T(n) = T(n/2) + O(1). Zincirin uzunluğu, n'yi 1'e indirmek için gereken yarılama sayısıdır, yani log₂ n. Toplam O(log n).

İki dal: üstel patlama

func fib(n int) int {
	if n < 2 { // temel durum
		return n
	}
	return fib(n-1) + fib(n-2)
}

Her çağrı iki çağrı daha yapar. fib(4) için ağaç şöyle:

                    fib(4)
                /            \
           fib(3)            fib(2)
          /      \           /    \
      fib(2)    fib(1)   fib(1)  fib(0)
      /    \
  fib(1)  fib(0)

Toplam 9 çağrı var ve fib(2) iki kez baştan hesaplanıyor. Ağacın derinliği n, her seviyede düğüm sayısı en fazla iki katına çıkıyor; dolayısıyla toplam düğüm sayısı 2ⁿ mertebesini geçmez, yani O(2ⁿ). (Daha sıkı sınır Θ(φⁿ), burada φ ≈ 1,618 altın oran; sonuç yine üstel.) Aynı alt problemlerin tekrar tekrar çözülmesi, sonuçları bir haritada saklayan memoization ile önlenebilir. Çağrı sayılarını karşılaştıralım:

package main

import "fmt"

var calls int // çağrı sayacı (yalnızca gösterim için global)

func fib(n int) int {
	calls++
	if n < 2 {
		return n
	}
	return fib(n-1) + fib(n-2)
}

func fibMemo(n int, memo map[int]int) int {
	calls++
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v
	}
	memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
	return memo[n]
}

func main() {
	fmt.Printf("%4s %12s %12s\n", "n", "düz", "memoization")
	for _, n := range []int{5, 10, 20, 30} {
		calls = 0
		fib(n)
		plain := calls

		calls = 0
		fibMemo(n, map[int]int{})
		fmt.Printf("%4d %12d %12d\n", n, plain, calls)
	}
}

n          düz  memoization
   5           15            9
  10          177           19
  20        21891           39
  30      2692537           59

Düz sürümde n'ye 10 eklemek çağrı sayısını yaklaşık 123 katına çıkarıyor (φ¹⁰ ≈ 123). Memoization'lı sürümde ise çağrı sayısı 2n − 1: her değer yalnızca bir kez hesaplanıyor. Bu fikrin tamamını Dinamik Programlama I: Temeller dersinde işleyeceğiz. Alan karmaşıklığının neden O(n) olduğunu da biraz aşağıda, çağrı yığını bölümünde göreceksin.

İki dengeli dal: O(n log n)

Birleştirmeli sıralama (merge sort) diziyi iki yarıya böler, her yarıyı özyinelemeli olarak sıralar ve iki sıralı yarıyı O(n) sürede birleştirir: T(n) = 2T(n/2) + O(n). Ağacı seviye seviye toplayalım:

seviye 0   :               [   n   ]                → n iş
seviye 1   :         [ n/2 ]       [ n/2 ]          → 2 · n/2 = n iş
seviye 2   :     [n/4]   [n/4]   [n/4]   [n/4]      → 4 · n/4 = n iş
   …                          …                          …
son seviye :  [1] [1] [1] [1] … [1] [1] [1] [1]     → n · 1   = n iş

Her seviyede toplam iş n ve n'yi 1'e indirene kadar log₂ n kez yarıya böldüğümüz için yaklaşık log₂ n seviye var: toplam O(n log n). Genel kural şu: toplam süre, ağacın bütün düğümlerindeki işlerin toplamıdır; seviyeler eşit iş yapıyorsa bu, seviye sayısı çarpı seviye başına iştir. Bu şekli Verimli Sıralama Algoritmaları dersinde tekrar göreceksin.

En iyi, ortalama ve en kötü durum

Aynı n için bile farklı girdiler farklı miktarda iş gerektirebilir. Doğrusal aramayı düşün: aranan değer dilimin başındaysa hemen bulursun, sonundaysa ya da hiç yoksa bütün dilimi taramak zorundasın.

• En iyi durum: Hedef ilk sırada. 1 karşılaştırma: Θ(1).
• En kötü durum: Hedef son sırada ya da dilimde yok. n karşılaştırma: Θ(n).
• Ortalama durum: Bir varsayım gerektirir. Hedefin dilimde olduğunu ve her konumda eşit olasılıkla bulunduğunu varsayarsak ortalama karşılaştırma sayısı (1 + 2 + … + n) / n = (n + 1) / 2 olur; bu da Θ(n).

Üç durumu 10 elemanlık bir dilimde sayalım:

package main

import "fmt"

// linearSearch hedefi arar; bulduğu indeksle birlikte
// kaç karşılaştırma yaptığını da döndürür.
func linearSearch(nums []int, target int) (index, comparisons int) {
	for i, v := range nums {
		comparisons++
		if v == target {
			return i, comparisons
		}
	}
	return -1, comparisons
}

func main() {
	nums := []int{42, 7, 19, 3, 88, 51, 23, 64, 12, 95}

	_, best := linearSearch(nums, 42)
	_, worst := linearSearch(nums, 100) // dilimde yok
	fmt.Println("En iyi durum (ilk eleman):", best, "karşılaştırma")
	fmt.Println("En kötü durum (bulunamadı):", worst, "karşılaştırma")

	total := 0
	for _, target := range nums {
		_, c := linearSearch(nums, target)
		total += c
	}
	fmt.Printf("Ortalama (her eleman eşit olasılıkla aranırsa): %.1f karşılaştırma\n",
		float64(total)/float64(len(nums)))
}

En iyi durum (ilk eleman): 1 karşılaştırma
En kötü durum (bulunamadı): 10 karşılaştırma
Ortalama (her eleman eşit olasılıkla aranırsa): 5.5 karşılaştırma

Hangisini raporlamalı? Çoğu zaman en kötü durumu, çünkü bir garanti verir: girdi ne olursa olsun bundan kötüsü olmaz. Ortalama durum, girdiler gerçekten o varsayıma uyduğunda pratikteki davranışı iyi anlatır. Hızlı sıralamanın ortalama O(n log n) ama en kötü durumda O(n²) olması ya da hash tablolarında aramanın ortalama O(1) ama en kötü durumda O(n) olması bunun klasik örnekleridir (Hash Tabloları). En iyi durum ise nadiren işe yarar; "şanslıysak hızlıyız" demek hiçbir şeyi garanti etmez.

Alan karmaşıklığı

Zaman tek kaynak değil; bellek de sınırlı. Alan karmaşıklığı (space complexity), bir algoritmanın çalışırken kullandığı ek belleğin n'ye göre nasıl büyüdüğünü anlatır. Girdinin kendisinin kapladığı yer genellikle sayılmaz; sayılıyorsa bunu açıkça belirtmek gerekir.

// O(1) ek alan: dilim ne kadar büyük olursa olsun iki indeks değişkeni.
func reverseInPlace(s []int) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

// O(n) ek alan: girdiyle aynı boyutta yeni bir dilim.
func reversedCopy(s []int) []int {
	out := make([]int, len(s))
	for i, v := range s {
		out[len(s)-1-i] = v
	}
	return out
}

İlk fonksiyon ek bellek ayırmadan girdinin üzerinde çalışır; bu tür algoritmalara yerinde (in-place) algoritma denir. İkincisi girdiyle aynı boyutta yeni bir dilim ayırır ve O(n) ek alan kullanır.

Zaman ve alan çoğu zaman birbiriyle takas edilir. Tekrar eden eleman problemi için üç yaklaşımı karşılaştıralım:

Özyineleme ve çağrı yığını

Özyinelemeli fonksiyonlarda kolayca gözden kaçan bir bellek maliyeti vardır: çağrı yığını (call stack). Her çağrı, parametrelerini ve yerel değişkenlerini tutan bir çerçeve (frame) oluşturur ve bu çerçeve çağrı dönene kadar bellekte kalır.

func sumRec(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	return nums[0] + sumRec(nums[1:])
}

Bu fonksiyon hiç yeni dilim ayırmıyor (nums[1:] aynı alttaki diziyi paylaşır, kopyalamaz). Yine de alan karmaşıklığı O(n), çünkü en derin noktada n + 1 çağrı aynı anda yığında bekliyor:

sumRec([3 5 7]) en derin anındayken çağrı yığını:

  ┌──────────────────┐
  │ sumRec([])       │  ← temel durum: 0 döndürür
  │ sumRec([7])      │  bekliyor: 7 + ?
  │ sumRec([5 7])    │  bekliyor: 5 + ?
  │ sumRec([3 5 7])  │  bekliyor: 3 + ?
  │ main             │
  └──────────────────┘

Kural şu: özyinelemenin alan maliyeti, en büyük derinlik çarpı çerçeve başına alandır. Buna göre:

• factorial ve sumRec: derinlik n olduğundan O(n) alan.
• Özyinelemeli ikili arama: derinlik log₂ n olduğundan O(log n) alan. Döngüyle yazılmış sürümü ise O(1).
• fib: zaman O(2ⁿ), ama alan yalnızca O(n). Yığın aynı anda ağacın yalnızca kökten bir yaprağa uzanan tek bir yolunu tutar; bir dal bitince o dalın çerçeveleri serbest kalır.

Amortize analiz

Bazı işlemler çoğu zaman çok ucuz, arada bir ise pahalıdır. Böyle bir işlemin yalnızca tek seferlik en kötü maliyetine bakarsak gereğinden karamsar oluruz. Amortize analiz (amortized analysis), tek bir işleme değil bir işlem dizisinin toplam maliyetine bakar ve bunu işlem sayısına bölerek işlem başına düşen maliyeti bulur.

Günlük hayattan bir benzetme: kitaplığın dolduğunda iki kat büyüklükte yeni bir kitaplık alıp bütün kitapları taşıyorsun. Taşıma günü yorucu ama seyrek; üstelik kitaplık her seferinde iki katına çıktığı için taşıma günleri giderek daha da seyrekleşiyor. Bütün yıla yayınca kitap başına düşen taşıma zahmeti küçük bir sabit.

Dinamik dizide ekleme

Go dilimlerinin ve birçok dildeki dinamik dizilerin temelinde şu model yatar: sabit kapasiteli bir dizi tut; yer varsa elemanı yaz (maliyet 1); dizi doluysa iki kat kapasiteli yeni bir dizi ayır, eski k elemanı oraya kopyala (maliyet k) ve ardından yaz (maliyet 1). Kapasitesi 1 olan boş bir diziye art arda eleman ekleyelim:

Tek başına bakınca 9. ekleme 9 birimlik maliyetiyle O(n) görünüyor. Ama 9 eklemenin toplamı 1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 + 9 = 24, yani ekleme başına 3'ten az.

Toplama yöntemi

Bu gözlemi n ekleme için genelleştirelim. Toplama yöntemi (aggregate method), n işlemin toplam maliyetini doğrudan hesaplayıp n'ye böler:

• Yazmalar: Her ekleme bir kez yazar; toplam n.
• Kopyalamalar: Büyüme yalnızca eleman sayısı 1, 2, 4, …, 2ᵏ olduğunda (2ᵏ < n) gerçekleşir ve her seferinde o anki bütün elemanlar kopyalanır. Toplam 1 + 2 + 4 + … + 2ᵏ. Bu, döngü analizinde gördüğümüz geometrik seri: 2ᵏ⁺¹ − 1 < 2n.

Toplam maliyet n + 2n = 3n'den azdır, yani O(n). Bunu n işleme bölünce ekleme başına amortize maliyet O(1) çıkar.

Neden iki katı? Sabit artışla karşılaştırma

Kapasiteyi iki katına çıkarmak yerine her seferinde 10 eleman eklesek ne olurdu? Büyümeler 10, 20, 30, … elemanda gerçekleşir ve kopyalama toplamı 10 + 20 + 30 + … ≈ n²/20 olur. Bu O(n²), yani ekleme başına amortize O(n) demek. Farkı simülasyonla görelim:

package main

import "fmt"

// copiesDoubling, dolunca kapasitesini iki katına çıkaran bir dinamik
// diziye n eleman eklemenin toplam kaç eleman kopyaladığını hesaplar.
func copiesDoubling(n int) int {
	capacity, length, copies := 1, 0, 0
	for range n {
		if length == capacity {
			copies += length // eski elemanlar yeni diziye taşınır
			capacity *= 2
		}
		length++
	}
	return copies
}

// copiesAdditive, kapasiteyi her seferinde sabit step kadar artırır.
func copiesAdditive(n, step int) int {
	capacity, length, copies := step, 0, 0
	for range n {
		if length == capacity {
			copies += length
			capacity += step
		}
		length++
	}
	return copies
}

func main() {
	fmt.Printf("%9s | %9s %8s | %13s %9s\n", "n", "×2 kopya", "kopya/n", "+10 kopya", "kopya/n")
	for _, n := range []int{1_000, 10_000, 100_000, 1_000_000} {
		d := copiesDoubling(n)
		a := copiesAdditive(n, 10)
		fmt.Printf("%9d | %9d %8.2f | %13d %9.1f\n",
			n, d, float64(d)/float64(n), a, float64(a)/float64(n))
	}
}

n |  ×2 kopya  kopya/n |     +10 kopya   kopya/n
     1000 |      1023     1.02 |         49500      49.5
    10000 |     16383     1.64 |       4995000     499.5
   100000 |    131071     1.31 |     499950000    4999.5
  1000000 |   1048575     1.05 |   49999500000   49999.5

İki katına çıkarma stratejisinde eleman başına düşen kopyalama n ne olursa olsun 1 civarında sabit kalıyor. Sabit artışta ise bu oran n ile doğrusal büyüyor; bir milyon eleman için neredeyse 50 milyar kopyalama. Çıkan ders: amortize O(1) için büyüme çarpımsal olmalıdır. Çarpanın tam olarak 2 olması şart değil; 1,5 ya da 1,25 gibi 1'den büyük herhangi bir sabit çarpan da geometrik bir seri üretir ve amortize O(1) sonucunu korur.

Amortize ile ortalama aynı şey değil

İkisi de "işlem başına ortalama maliyet" gibi dursa da temelden farklıdır. Ortalama durum analizi girdilerin belirli bir dağılımdan geldiğini varsayar; şanssız bir girdide sonuç daha kötü olabilir. Amortize analizde ise olasılık yoktur: her işlem dizisi için toplam maliyet garantidir. n ekleme, hangi değerler eklenirse eklensin, en fazla 3n birim tutar.

Öte yandan amortize O(1), her bir işlemin hızlı olduğu anlamına gelmez. Büyüme anındaki ekleme yine O(n) sürer. Toplam iş hacmi önemliyse bu sorun değildir; ama her isteğin belirli bir sürenin altında yanıtlanması gereken, gecikmeye duyarlı sistemlerde bu ani sıçramalar önem kazanabilir.

Go'nun append'i

Go'nun append'i de aynı fikre dayanır, ama büyüme politikası biraz daha incelikli. Çalışma zamanının kaynak kodundaki kurala göre kapasite 256'nın altındayken yeni kapasite eskisinin iki katıdır. Daha büyük dilimlerde her büyümede kapasiteye (kapasite + 768) / 4 eklenir; böylece çarpan kademeli olarak 2'den 1,25'e yaklaşır. Hesaplanan değer ayrıca bellek ayırıcının boyut sınıflarına yukarı yuvarlanır. Çarpan her zaman 1'den büyük kaldığı için append amortize O(1)'dir.

Son boyutu önceden biliyorsan hiç büyüme yaşanmasın diye kapasiteyi baştan ayırabilirsin: make([]int, 0, n). Dilimlerin iç yapısını Diziler ve Dilimler dersinde, dinamik diziyi sıfırdan yazmayı ise Diziler ve Dinamik Diziler dersinde göreceksin.

Sık yapılan hatalar

• Big-O'yu en kötü durumla karıştırmak. O bir üst sınır gösterimidir; en iyi, ortalama ve en kötü durumun her biri için ayrı ayrı O, Ω veya Θ söylenebilir. Neyi analiz ettiğini ("en kötü durumda Θ(n)") açıkça belirt.
• Farklı girdileri tek harfe indirmek. İki farklı dilim üzerinde iç içe döngü O(n²) değil, O(n·m)'dir. Art arda iki döngü de O(n + m)'dir ve terimlerden biri atılamaz.
• Gizli maliyetleri görmemek. Döngü içindeki slices.Contains, copy, string birleştirme ya da her turda yapılan bir sıralama tek satır görünse de kendi başına en az O(n)'dir.
• Özyinelemenin yığın alanını unutmak. Hiç yeni veri yapısı ayırmayan özyinelemeli bir fonksiyon bile derinliği kadar yığın alanı kullanır.
• i *= 2 ile i += 2'yi karıştırmak. İlki logaritmik, ikincisi doğrusal döngüdür. Döngü değişkeninin nasıl değiştiğine her zaman dikkatle bak.
• Üst sınırları çarpıp sıkı sınır sanmak. Geometrik seri örneğindeki gibi, iç döngünün "en fazla n" kez dönmesi toplamın n log n olduğu anlamına gelmez; dönüş sayılarını gerçekten topla.
• Amortize O(1)'i "her işlem O(1)" sanmak. Büyüme anındaki tek bir append O(n) sürer. Gecikmeye duyarlı kodda kapasiteyi önceden ayırmayı düşün.
• Sabitleri tamamen önemsiz sanmak. Küçük girdilerde karmaşıklığı "daha kötü" olan basit bir algoritma daha hızlı olabilir. Karar vermeden önce ölç.

Alıştırmalar

func a(n int) {
	for i := n; i > 1; i /= 3 {
		// O(1) iş
	}
}

func b(n int) {
	for range n {
		for range 5 {
			// O(1) iş
		}
	}
}

func c(n int) {
	for i := 1; i*i <= n; i++ {
		// O(1) iş
	}
}

func d(n int) {
	for i := range n {
		for j := i; j > 0; j /= 2 {
			// O(1) iş
		}
	}
}

package main

import "fmt"

func a(n int) int {
	steps := 0
	for i := n; i > 1; i /= 3 {
		steps++
	}
	return steps
}

func b(n int) int {
	steps := 0
	for range n {
		for range 5 {
			steps++
		}
	}
	return steps
}

func c(n int) int {
	steps := 0
	for i := 1; i*i <= n; i++ {
		steps++
	}
	return steps
}

func d(n int) int {
	steps := 0
	for i := range n {
		for j := i; j > 0; j /= 2 {
			steps++
		}
	}
	return steps
}

func main() {
	for _, n := range []int{100, 10_000} {
		fmt.Printf("n = %5d: a = %d, b = %d, c = %d, d = %d\n", n, a(n), b(n), c(n), d(n))
	}
}

n =   100: a = 4, b = 500, c = 10, d = 573
n = 10000: a = 8, b = 50000, c = 100, d = 123617

package main

import "fmt"

// hasDuplicateNested: O(n²) zaman, O(1) ek alan.
func hasDuplicateNested(nums []int) (bool, int) {
	ops := 0
	for i := range nums {
		for j := i + 1; j < len(nums); j++ {
			ops++
			if nums[i] == nums[j] {
				return true, ops
			}
		}
	}
	return false, ops
}

// hasDuplicateMap: ortalama O(n) zaman, O(n) ek alan.
func hasDuplicateMap(nums []int) (bool, int) {
	ops := 0
	seen := make(map[int]struct{}, len(nums))
	for _, v := range nums {
		ops++
		if _, ok := seen[v]; ok {
			return true, ops
		}
		seen[v] = struct{}{}
	}
	return false, ops
}

func main() {
	nums := make([]int, 10_000)
	for i := range nums {
		nums[i] = i * 7 // hepsi farklı: en kötü durum
	}

	dup, ops := hasDuplicateNested(nums)
	fmt.Printf("iç içe döngü: tekrar=%v, %d karşılaştırma\n", dup, ops)

	dup, ops = hasDuplicateMap(nums)
	fmt.Printf("map ile:      tekrar=%v, %d arama\n", dup, ops)
}

iç içe döngü: tekrar=false, 49995000 karşılaştırma
map ile:      tekrar=false, 10000 arama

package main

import "fmt"

const mod = 1_000_000_007

var calls int

// powSlow: T(n) = T(n-1) + O(1) → O(n) zaman, O(n) yığın alanı.
func powSlow(x, n int) int {
	calls++
	if n == 0 {
		return 1
	}
	return x * powSlow(x, n-1) % mod
}

// powFast: T(n) = T(n/2) + O(1) → O(log n) zaman, O(log n) yığın alanı.
func powFast(x, n int) int {
	calls++
	if n == 0 {
		return 1
	}
	half := powFast(x, n/2)
	result := half * half % mod
	if n%2 == 1 {
		result = result * x % mod
	}
	return result
}

// powWasteful: yarım sonucu saklamaz, iki kez hesaplar.
// T(n) = 2T(n/2) + O(1) → yeniden O(n)!
func powWasteful(x, n int) int {
	calls++
	if n == 0 {
		return 1
	}
	result := powWasteful(x, n/2) * powWasteful(x, n/2) % mod
	if n%2 == 1 {
		result = result * x % mod
	}
	return result
}

func main() {
	for _, n := range []int{10, 100, 1000} {
		calls = 0
		r1 := powSlow(3, n)
		slow := calls

		calls = 0
		r2 := powFast(3, n)
		fast := calls

		calls = 0
		r3 := powWasteful(3, n)
		wasteful := calls

		fmt.Printf("n=%4d  aynı sonuç: %v  yavaş: %4d  hızlı: %2d  savurgan: %4d çağrı\n",
			n, r1 == r2 && r2 == r3, slow, fast, wasteful)
	}
}

n=  10  aynı sonuç: true  yavaş:   11  hızlı:  5  savurgan:   31 çağrı
n= 100  aynı sonuç: true  yavaş:  101  hızlı:  8  savurgan:  255 çağrı
n=1000  aynı sonuç: true  yavaş: 1001  hızlı: 11  savurgan: 2047 çağrı

for i := 1; i <= n; i++ {
	for j := i; j <= n; j += i {
		// O(1) iş
	}
}

package main

import (
	"fmt"
	"math"
)

func steps(n int) int {
	count := 0
	for i := 1; i <= n; i++ {
		for j := i; j <= n; j += i {
			count++
		}
	}
	return count
}

func main() {
	fmt.Printf("%8s %10s %12s %7s\n", "n", "adım", "n·ln n", "oran")
	for _, n := range []int{10, 100, 1_000, 10_000, 100_000} {
		s := steps(n)
		ref := float64(n) * math.Log(float64(n))
		fmt.Printf("%8d %10d %12.0f %7.3f\n", n, s, ref, float64(s)/ref)
	}
}

n       adım       n·ln n    oran
      10         27           23   1.173
     100        482          461   1.047
    1000       7069         6908   1.023
   10000      93668        92103   1.017
  100000    1166750      1151293   1.013

Kısa sınav

Özet

• Karmaşıklık analizi, girdi boyutu n büyüdükçe işin nasıl büyüdüğünü makineden bağımsız olarak ifade eder; ölçümün yerini almaz, ona yol gösterir.
• O üst sınır, Ω alt sınır, Θ sıkı sınırdır: her n ≥ n₀ için f(n) ≤ c·g(n) sağlanıyorsa f = O(g). Bu gösterimler en iyi ve en kötü durumdan bağımsız kavramlardır.
• Sabit çarpanları ve küçük terimleri at; ardışık blokları topla, iç içe blokları çarp; farklı girdilere farklı harfler ver.
• i++ doğrusal, i *= 2 logaritmik döngüdür. Bağımlı iç içe döngüler n(n − 1)/2 = Θ(n²) verir; geometrik seriler en büyük teriminin iki katını geçmez.
• Özyinelemede toplam iş ağaçtaki bütün düğümlerin işidir: tek dal O(n), yarılanan tek dal O(log n), iki dal O(2ⁿ), dengeli iki dal ve doğrusal birleştirme O(n log n).
• En kötü durum garanti verir; ortalama durum bir girdi varsayımına dayanır.
• Alan karmaşıklığı ek belleği ölçer ve özyinelemede yığın derinliğini de içerir.
• Kapasitesini çarpımsal büyüten bir dinamik dizide n ekleme toplam O(n) tutar, yani ekleme başına amortize O(1). "Saniyede kabaca 10⁸ basit işlem" kuralıyla bir yaklaşımın süre sınırına sığıp sığmayacağını hızla tahmin edebilirsin.