Big-O ve Zaman/Alan Analizi: Adım Adım Algoritma Örnekleri

Big-O ve Zaman/Alan Analizi: Adım Adım Rehber

Algoritma analizi, bir programın çalışma zamanı ve hafıza gereksinimlerinin girdi boyutuna göre nasıl değiştiğini ortaya koyar. Bu amaçla en yaygın kullanılan gösterim Big-O notasyonudur. Big-O, bir algoritmanın büyüme oranını, özellikle büyük girdiler için davranışını ifade eder; kavramsal açıklamalar ve örnekler için bkz. Birhan Karahasan ve Mehmet Ali Uçar.

Zaman vs. Alan Karmaşıklığı – Temel Fark

Zaman karmaşıklığı (time complexity), bir algoritmanın çalışma adımlarının sayısının girdi büyüklüğüyle nasıl değiştiğini gösterir. Alan karmaşıklığı (space complexity) ise algoritmanın ek hafıza kullanımını ölçer. Analiz yaparken genellikle en kötü durum (worst-case) ele alınır, ancak en iyi ve ortalama durumlar da önemli olabilir.

Big-O Hesaplama İçin İzlenecek Adımlar

Algoritmayı adım adım yazın veya pseudocode çıkarın.
Her temel işlemin kaç kez çalıştığını sayın (döngüler, özyinelemeler, çağrılan fonksiyonlar).
Sabit çarpanları ihmal edin (örneğin 2n → n).
Daha düşük dereceli terimleri göz ardı edin (n + n² → n²).
Karmaşıklığı en baskın terime göre yazın (ör. O(n²), O(log n)).

Adım Adım Örnekler

Aşağıda sık karşılaşılan karmaşıklık sınıfları için kısa pseudocode ve adım adım analizler yer alıyor.

1) O(1) — Sabit Zaman

Örnek: Dizinin belirli bir indeksine erişim.

Pseudocode:

return arr[index]

Açıklama: İşlem dizinin büyüklüğünden bağımsız olarak sabit sayıda adımda tamamlanır. Zaman karmaşıklığı O(1). Bellek kullanımı da ek veri tutmuyorsanız O(1) olarak kalır.

2) O(n) — Doğrusal Zaman

Örnek: Dizide belirli bir değeri arama (linear search).

Pseudocode:

for i from 0 to n-1:
if arr[i] == x:
return i
return -1

Açıklama: En kötü durumda tüm elemanlara bakılır; adım sayısı n ile doğru orantılıdır. Zaman O(n), ek alan O(1).

3) O(n²) — Karesel Zaman

Örnek: İki iç içe döngü ile tüm çiftleri kontrol etmek (basit karşılaştırma/sıralama aşamaları).

Pseudocode:

for i from 0 to n-1:
for j from 0 to n-1:
do constant_work()

Açıklama: İç döngü her dış döngü adımında n kez çalışır; toplam adım sayısı ~n * n = n². Zaman O(n²). Eğer sabit ek yapı kullanılmıyorsa alan O(1).

4) O(log n) — Logaritmik Zaman

Örnek: Sıralı dizide binary search. Her adım arama alanını yaklaşık yarıya indirir.

Pseudocode (özet):

low = 0; high = n-1
while low <= high:
  mid = (low + high) / 2
  if arr[mid] == x: return mid
  else if arr[mid] < x: low = mid+1
  else high = mid-1
return -1

Açıklama: Her yinelemede arama aralığı yarıya iner; adım sayısı ~log2(n) ile orantılıdır. Zaman O(log n), alan genelde O(1) (iteratif çözüm).

5) O(2ⁿ) — Üstel Zaman

Örnek: Naif özyinelemeli Fibonacci hesaplaması.

Pseudocode:

function fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)

Açıklama: Her çağrı iki yeni çağrı üretir; çağrı ağacı büyür ve toplam çağrı sayısı yaklaşık 2ⁿ seviyesine ulaşır. Zaman O(2ⁿ). Alan ise özyinelemeye bağlı olarak O(n) (call stack) olabilir.

Pratik Optimizasyon Örneği: O(n²) → O(n)

Senaryo: Bir dizide tekrar eden (duplicate) öğe var mı kontrol etmek için çift döngü kullanıyorsunuz (O(n²)). Bunu bir hash set kullanarak O(n) zamanı ve O(n) alanı ile çözebilirsiniz.

Pseudocode (optimize edilmiş):

set = empty
for each element in arr:
if element in set: return true
add element to set
return false

Açıklama: Her eleman için set sorgusu ortalama O(1) olduğundan toplam O(n) zamana düşer. Bu yaklaşım ek hafıza gerektirir (O(n)). Gerçek dünyada set/map yapılarının ortalama ve en kötü durum davranışını ayırt etmek gerekir (ortalama O(1), bazı durumlarda çarpışma nedeniyle O(n)). Bu konu hakkında daha fazlası için kaynak incelenebilir.

Sık Yapılan Hatalar ve Dikkat Edilmesi Gerekenler

Sabit faktörleri aşırı önemsemek: 1000n ile 2n arasındaki fark, n çok büyük olmadıkça pratikte farklı görünse de Big-O açısından her ikisi de O(n) kabul edilir.
Ortalama vs En kötü durum: Bazı veri yapıları (ör. hash tablosu) ortalama iyi performans sunar; en kötü durum farklı olabilir.
Amortize edilmiş karmaşıklık: Dinamik dizilerde push/append işlemi genelde amortize O(1)’dir; tek seferde maliyet yüksek olabilir ama uzun vadede ortalama sabittir.
Gerçek dünya etkileri: Algoritmanın gerçek süreleri derleyici, dil, bellek hiyerarşisi (cache) ve sabit faktörlere bağlıdır; Big-O sadece büyüme eğilimini gösterir.

Adım Adım Analiz Kontrol Listesi (Uygulama İçin)

Pseudocode veya akış çıkarın.
Döngülerin ve özyinelemenin derinliğini sayın.
Sabitleri kaldırın, düşük dereceli terimleri çıkarın.
Alan kullanımı için ek veri yapılarını ve call stack etkisini değerlendirin.
Gerekiyorsa ortalama/alışılmış durum ve en kötü durumu ayrı hesaplayın.

Kaynaklar ve Daha Fazla Okuma

Bu rehberdeki temel kavramlar ve örnekler için bakılabilecek kaynaklar:

Sonuç

Big-O notasyonu, algoritmaların ölçeklenebilirliğini anlamak için güçlü bir araçtır. Analiz adımlarını öğrenmek ve örnekler üzerinde pratik yapmak (lineer arama, iç içe döngüler, binary search, naïf rekürsiyon, hashing ile optimizasyon) sizin için pratik bir temel sağlayacaktır. Teorik analiz ile gerçek dünya ölçümlerini birlikte değerlendirmek en sağlıklısıdır.