Bölüm 2: Algoritma Analizi
Klasik Soru · Algoritmalar ve Ölçüm
Soru 1: Katlama Deneyi
Bir algoritma için aynı bilgisayarda yapılan katlama deneyinde tablodaki süreler ölçülmüş olsun. T(n) hangi büyüme sınıfındadır ve n = 32.000 için süre yaklaşık ne olur?
| n | 2.000 | 4.000 | 8.000 | 16.000 |
|---|---|---|---|---|
| süre (ms) | 3 | 24 | 190 | 1.530 |
Cevabı göster
Oranlar: 24/3 = 8, 190/24 ≈ 7,9, 1530/190 ≈ 8,1 → T(2n)/T(n) ≈ 8 = 2³ → T(n) ≈ c·n³, kübik.
Tahmin: T(32.000) ≈ 8 · 1.530 ≈ 12.240 ms ≈ 12 s.
Bu sonuç donanıma, JVM'e ve yüke bağlıdır; yalnızca denenen girdileri kapsar ve algoritmanın tamamen kodlanmasını gerektirir. Bu sınırlar yüzünden ilkel işlemleri sayarak yapılan analiz tercih edilir: donanımdan bağımsızdır, tüm girdiler için geçerlidir ve kod çalıştırılmadan yapılır.
Klasik Soru · Algoritmalar ve Ölçüm
Soru 2: İlkel İşlemleri Saymak
n öğeli dizide negatifSay en iyi ve en kötü durumda kaç ilkel işlem yapar ve hangi girdiler bu durumlara yol açar? Satır satır sayınız.
int negatifSay(int[] a) { int s = 0; for (int i = 0; i < a.length; i++) if (a[i] < 0) s++; return s; }
Cevabı göster
| İfade | Kaç kez? |
|---|---|
s = 0, i = 0 | 1 + 1 |
i < a.length | n + 1 |
a[i] < 0 | n |
s++ | 0 … n |
i++ | n |
return | 1 |
En iyi: 3n + 4 (hiç negatif yok). En kötü: 4n + 4 (tüm öğeler negatif). İki durumda da Θ(n); sabitler donanıma bağlı olduğundan atılır.
Çoktan Seçmeli · Asimptotik Gösterim
Soru 3: Büyüme Hızları
Büyük n için fonksiyonların yavaştan hızlıya doğru büyüme sıralaması hangisidir?
n = 1.000 için: log₂n ≈ 10, n = 1.000, n log₂n ≈ 9.966, n² = 10⁶, 2ⁿ ≈ 10³⁰¹. B çeldiricidir çünkü n = 2, 3, 4 gibi küçük değerlerde 2ⁿ ≤ n² olabilir; ama büyük n'de 2ⁿ her polinomu geçer (n = 100'de 2ⁿ adım ~4·10¹³ yıl sürer).
Çoktan Seçmeli · Asimptotik Gösterim
Soru 4: Asimptotik Gösterim Yanılgıları
Aşağıdaki ifadelerden hangisi doğrudur?
O, Ω, Θ sınır gösterimleridir; en iyi/ortalama/en kötü durum ayrı kavramdır ve her duruma uygulanabilir (B yanlış). log₂ n = log₁₀ n / log₁₀ 2: yalnız sabit çarpan farkı → ikisi de O(log n). O(1) sabiti büyük olabilir; küçük n'de 1000 adımlık sabit iş, n adımlık işten yavaştır.
Çoktan Seçmeli · Asimptotik Gösterim
Soru 5: Amortize Analiz
Büyüyen bir dizide (ör. ArrayList) sona ekleme çoğunlukla tek adımdır; dizi dolunca tüm öğeler iki kat büyük yeni bir diziye kopyalanır (O(n)). Bu işlem için en doğru ifade hangisidir?
Kopyalamalar 1 + 2 + 4 + … < 2n öğe tutar; uzun bir işlem dizisinin toplam maliyeti işlem sayısına bölünür → ekleme başına sabit. Tek bir ekleme yine O(n) olabilir, bu yüzden C yanlıştır; amortize analiz olasılık varsaymaz (D yanlış).
Çoktan Seçmeli · Asimptotik Gösterim
Soru 6: En Kötü Durum Girdisi
Tüm öğe çiftlerini karşılaştırıp ilk eşit çifti bulduğunda true döndüren tekrarVar(a) için en kötü durumu hangi girdi oluşturur?
Tekrar yoksa erken dönüş hiç olmaz; n(n − 1)/2 çiftin hepsi karşılaştırılır → Θ(n²). A ve B ilk karşılaştırmada true döner (en iyi durum, Θ(1)). Sıralı olmak tek başına sonucu değiştirmez; D'de tekrar bulunduğu anda metot biter.
Klasik Soru · Koddan Karmaşıklığa
Soru 7: Döngülerden Karmaşıklığa
n = 16 için kod bittiğinde s kaçtır ve kodun Büyük O karmaşıklığı nedir?
int s = 0; for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) s++; for (int k = 0; k < 100; k++) s++;
Cevabı göster
s = 164.
- İç döngü j = 1, 2, 4, 8 → ⌈log₂16⌉ = 4 tur; dış döngü 16 tur → iç içe olduğundan çarpılır: 16 · 4 = 64 → O(n log n).
- İkinci döngü n'den bağımsız 100 tur → O(1).
Ardışık bloklarda maliyetler toplanır, en büyüğü kalır: O(n log n) + O(1) = O(n log n). “İç içe döngü = n²” kuralı burada geçerli değildir.
Klasik Soru · Koddan Karmaşıklığa
Soru 8: Üç Döngü Kalıbı
Her parçanın sonunda s yaklaşık kaçtır ve Büyük O karmaşıklığı nedir?
// (1) for (int i = n; i > 0; i /= 2) s++; // (2) for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) s++; // (3) for (int i = 0; i < n; i += 2) for (int j = 0; j < 10; j++) s++;
Cevabı göster
(1) i her turda yarıya iner: ⌊log₂ n⌋ + 1 tur → O(log n).
(2) İç döngü i kez döner: 0 + 1 + … + (n − 1) = n(n − 1)/2 → O(n²). İç döngünün dış değişkene bağlı olması sınıfı değiştirmez.
(3) Dış döngü n/2 tur, iç döngü sabit 10 tur: 5n → O(n). İç içe döngü her zaman n² demek değildir.
Adım Adım Çalıştırma · Koddan Karmaşıklığa
Soru 9: İkili Arama İzleme
a = {3, 7, 11, 15, 19, 24, 30, 36} dizisinde ikiliArama(a, 8) kaç tur döner, lo ve hi nasıl değişir ve ne döndürür?
Arama aralığı tüm dizi: lo = 0, hi = 7.
1. tur: mid = (0 + 7) / 2 = 3, a[3] = 15.
15 > 8 → hedef sol yarıda: hi = 2. Sağ yarı elendi.
2. tur: mid = (0 + 2) / 2 = 1, a[1] = 7.
7 < 8 → hedef sağda: lo = 2.
3. tur: mid = (2 + 2) / 2 = 2, a[2] = 11.
11 > 8 → hi = 1.
2 ≤ 1 yanlış → aralık boş, döngü biter.
return −1, 3 tur. n = 8'de en kötü ⌊log₂8⌋ + 1 = 4 tur; n = 10⁶'da 20 → O(log n).
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; }
Çoktan Seçmeli · Koddan Karmaşıklığa
Soru 10: Orta İndis Taşması
Çok büyük bir dizide ikili arama yapılırken aşağıdaki satırlar çalışıyor. Çıktı nedir?
int lo = 1_500_000_000; int hi = 2_000_000_000; int m1 = (lo + hi) / 2; int m2 = lo + (hi - lo) / 2; System.out.println(m1 + " " + m2);
lo + hi = 3,5·10⁹, int sınırını (≈ 2,1·10⁹) aşar ve sessizce negatife sarar; Java tam sayı taşmasında hata fırlatmaz (D yanlış). lo + (hi - lo) / 2 hiçbir ara adımda sınırı aşmaz, güvenlidir.
Çoktan Seçmeli · Alan ve Doğruluk
Soru 11: Ek Bellek
Aşağıdaki metotlardan hangisinin ek alan karmaşıklığı O(n)'dir? (Girdi dizisinin kendisi sayılmaz.)
C, sonucu tutmak için n hücrelik yeni bir dizi ayırır → O(n) ek bellek. A, B ve D yalnızca birkaç değişken (en büyük, iki indis, lo / hi / mid) kullanır → O(1).
Çoktan Seçmeli · Asimptotik Gösterim
Soru 12: Θ için c₁, c₂ ve n₀
f(n) = 3n + 10 = Θ(n) için her n ≥ n₀'da c₁·n ≤ f(n) ≤ c₂·n olmalıdır. Hangi seçim bunu göstermez?
c₁ ≤ 3 iken alt sınır hep sağlanır. Üst sınır: 3n + 10 ≤ c₂·n ⇔ n ≥ 10 / (c₂ − 3). D'de n ≥ 5 gerekir; n = 4'te f(4) = 22 > 20. A (n ≥ 10), B (n ≥ 1) ve C (n ≥ 2) geçerlidir. c ve n₀ tek değildir; D'de n₀ = 5 seçilseydi geçerli olurdu.
Klasik Soru · Asimptotik Gösterim
Soru 13: Ω'yı Tanımla Göstermek
f(n) = n²/2 − 3n olsun.
- c = 1/4 alarak f(n) = Ω(n²) olduğunu gösteriniz. Bu c için en küçük n₀ kaçtır?
- f(n) = O(n) olmadığını tanımı kullanarak gösteriniz.
- f için hangi Θ ifadesi yazılabilir?
Cevabı göster
1. n²/2 − 3n ≥ n²/4 ⇔ n²/4 ≥ 3n ⇔ n ≥ 12. n₀ = 12 (n = 11'de f = 27,5 < 121/4 = 30,25).
2. c ve n₀ olsaydı her n ≥ n₀ için n²/2 − 3n ≤ c·n, yani n ≤ 2c + 6 olurdu; n = max(n₀, 2c + 7) bunu bozar → f(n) ≠ O(n).
3. f(n) ≤ n²/2 → O(n²). 1. ile birlikte Θ(n²): n ≥ 12 için n²/4 ≤ f(n) ≤ n²/2.
Çoktan Seçmeli · Asimptotik Gösterim
Soru 14: Dağılıma Göre Ortalama Durum
10 öğeli bir dizide doğrusal arama yapılıyor; hedef her zaman dizide. Hedefin 1. ve 2. konumda olma olasılığı ayrı ayrı 0,3; kalan 8 konumun her birinde 0,05'tir. i. konumdaki hedef i karşılaştırmayla bulunuyorsa ortalama durumda beklenen karşılaştırma sayısı kaçtır?
Beklenen değer = Σ olasılık × maliyet = 0,3·1 + 0,3·2 + 0,05·(3 + 4 + … + 10) = 0,9 + 0,05·52 = 3,5. A eşit olasılık varsayımıdır ((n + 1)/2); ortalama durum seçilen dağılıma bağlıdır. C yalnızca ilk iki konumun ortalamasıdır, kalan 0,4 olasılık unutulmuştur. D en kötü durumdur.
Klasik Soru · Asimptotik Gösterim
Soru 15: Başarısız Aramayla Ortalama
n öğeli dizide doğrusal arama yapılıyor. Hedef q olasılıkla dizide yoktur (n karşılaştırma); varsa n konumdan her birinde eşit olasılıklıdır (i. konum i karşılaştırma).
- Beklenen karşılaştırma sayısını n ve q cinsinden yazınız.
- n = 8, q = 0,5 için hesaplayınız.
- q = 0 ve q = 1 neye karşılık gelir? Ortalama durum hangi sınıftadır?
Cevabı göster
1. Dizideyse ortalama (1 + … + n) / n = (n + 1)/2; iki durum olasılıklarıyla ağırlıklandırılır:
E = (1 − q)·(n + 1)/2 + q·n
2. E = 0,5 · 4,5 + 0,5 · 8 = 2,25 + 4 = 6,25 karşılaştırma.
3. q = 0: hedef hep dizide, E = (n + 1)/2. q = 1: hedef yok, E = n (en kötü durum). Her q için E doğrusal → Θ(n); dağılım yalnız sabiti değiştirir.