Bir algoritmanın zaman karmaşıklığını hesaplamak için önce girdinin boyutunu (n) seçer, kodun n'ye bağlı olarak kaç temel işlem yaptığını sayar, sonra sabit çarpanları ve düşük dereceli terimleri atıp en hızlı büyüyen terimi bırakırsın. Elde ettiğin sonuç Big O gösterimidir. Big O saniyeyi değil, girdi büyüdükçe işin ne hızla büyüdüğünü anlatır. Aşağıda üç kısa Python örneğiyle işlem sayısını elle sayıp bu yöntemi adım adım uygulayacaksın.
Önce n'yi seç: giriş boyutu ve sabit işlem neden O(1)?
Her kodda ilk soru şudur: Neyin büyümesi işi büyütür? Cevap n'dir. Bir listeyi işleyen kodda n eleman sayısıdır. Bir metni tarayan kodda metnin uzunluğu, bir sayıyı tekrar tekrar bölen kodda ise sayının kendi değeri n olabilir. Koddan önce n'yi açıkça yazmak, sonraki sayımların tutarlı kalmasını sağlar.
Atama, toplama ya da listede tek bir indeksle erişim gibi işlemler n'den bağımsızdır. Bunlar O(1), yani sabit sayılır. "Sabit" kelimesi "hızlı" demek değildir; "n büyüse de aynı kalır" demektir.
def ilk_eleman(liste):
return liste[0]
kucuk = [7, 3, 9]
buyuk = list(range(10_000_000))
print(ilk_eleman(kucuk))
print(ilk_eleman(buyuk))7
0Fonksiyon iki listede de aynı işi yapar: bir indeks erişimi ve bir return. Liste 3 elemanlı da olsa 10 milyon elemanlı da olsa adım sayısı değişmez. Listeyi oluşturmak ise n'ye bağlı bir iştir ama o iş fonksiyonun dışında kalır; biz yalnızca fonksiyonun içini sayıyoruz.
Formal tanım da bu sezgiyle uyumludur: f(n) = O(g(n)) demek, yeterince büyük n değerlerinden sonra, uygun bir c sabitiyle çarpılmış g(n)'nin f(n)'nin üstünde kaldığı anlamına gelir. Bu yüzden sabit çarpanlar Big O'yu değiştirmez.
Tek döngü: işlem sayısı n ile birlikte büyür
Bir listedeki sayıları tek for döngüsüyle toplayan fonksiyonla başlayalım:
def toplam_alan(liste):
toplam = 0
for sayi in liste:
toplam += sayi
return toplam
print(toplam_alan([4, 8, 15]))27
Döngüdeki toplama sayısı: 3Çıkarımı sırayla yapalım:
- n'yi seç: listenin eleman sayısı. Örnekte n = 3.
- Döngü kaç kez döner? n kez.
- Gövde ne kadar iş yapar? Tur başına 1 toplama, yani sabit.
- Başlangıç ve bitiş işleri:
toplam = 0vereturnda sabit.
Toplam işlem yaklaşık T(n) = n + 2 olur. Büyük n için "+ 2" önemsizdir, geriye n kalır: O(n).
Gövdede tur başına 3 işlem olsaydı T(n) = 3n + 2 çıkardı. Çarpan 3 de sabit olduğu için düşer ve sonuç yine O(n) olur. O(n) ile O(3n) arasında Big O açısından fark yoktur; ikisi de "girdi iki katına çıkınca iş yaklaşık iki katına çıkar" der.
İç içe döngü: iç döngü dıştakine bağlıysa toplam işlem nasıl bulunur?
Şimdi listedeki her çifti yalnızca bir kez gezen ve değerleri birbirinden farklı çiftleri sayan bir fonksiyon yazalım. Dış döngü i ile, iç döngü i + 1'den başlayarak ilerler:
def farkli_cift_say(liste):
n = len(liste)
sayac = 0
for i in range(n):
for j in range(i + 1, n):
if liste[i] != liste[j]:
sayac += 1
return sayac
print(farkli_cift_say([1, 2, 2, 3]))5
Karşılaştırma sayısı: 6Burada n = 4. İç döngü, i değerine göre sırasıyla 3, 2, 1 ve 0 kez döner. Toplam karşılaştırma 3 + 2 + 1 + 0 = 6 olur. Bu çiftlerden yalnızca (2, 2) aynı değerlidir, kalan 5 çift farklıdır, bu yüzden çıktı 5'tir.
Genel olarak iç döngü n-1, n-2, ..., 1, 0 kez döner. Bu toplam şöyle yazılır:
(n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 = n²/2 - n/2
Formülü küçük değerlerle doğrulayabilirsin: n = 4 için 4·3/2 = 6, n = 5 için 5·4/2 = 10. Sabit çarpan 1/2 ve düşük dereceli terim n/2 atılınca geriye n² kalır: O(n²).
Bağımlılığı kontrol etmek neden gerekli?
İç döngü dıştakinden bağımsız olsaydı, yani for j in range(n) yazsaydık, iş tam n × n = n² olurdu: n = 4 için 16, n = 5 için 25 karşılaştırma. Bağımlı sürüm bunun yaklaşık yarısı kadar iş yapar (6 ve 10). Bu örnekte iki sürüm de O(n²) sınıfına düşer, çünkü yarı çarpan Big O'da kaybolur.
Yine de "iç içe iki döngü her zaman n²'dir" kuralı güvenilir değildir. İç döngü for j in range(10) gibi sabit sayıda dönüyorsa toplam iş 10n olur ve sonuç O(n)'dir. Bu yüzden iç döngünün sınırını okuyup neye bağlı olduğuna bakmak, hesabın ayrı ve zorunlu bir adımıdır.
Ardışık bloklar ve if dalları: hangi terim baskın, hangi durum sayılır?
Kodda iki kural işine yarar: iç içe olanlar çarpılır, art arda olanlar toplanır. Bir fonksiyonda önce n adımlık bir döngü, ardından n × n adımlık bir çift döngü, en sonda da tek bir atama olsun. İşlem sayımı şöyle çıkar:
- Birinci blok: n işlem
- İkinci blok: n × n = n² işlem
- Üçüncü blok: 1 işlem
- Toplam: n² + n + 1
n = 1000 için bu 1.000.000 + 1.000 + 1 = 1.001.001 eder. Toplamın neredeyse tamamını n² belirler. n büyüdükçe n ve 1 terimlerinin payı daha da küçülür. Bu yüzden düşük dereceli terimleri ve sabitleri atarsın, geriye O(n²) kalır.
if ve else dallarında genellikle en pahalı dal esas alınır. Bir dal tek bir karşılaştırmayla bitiyor (O(1)), diğeri listeyi baştan sona geziyorsa (O(n)) üst sınır O(n) olur. Çünkü hangi dala gireceğini girdi belirler ve Big O'da en kötü durumu güvenceye almak istersin.
Burada iki sınır var. Big O bir üst sınır anlatır. Bir algoritmanın en iyi ya da ortalama durumu bundan daha iyi olabilir ve bu durumlar ayrıca analiz edilir. Ayrıca bu sayım yöntemi tek yol değildir, daha ince analiz teknikleri de vardır. Ancak tipik ders ve mülakat kodlarının çoğu için toplama, çarpma ve baskın terimi seçme akışı yeterli bir başlangıç sağlar.
n'yi her turda ikiye bölen döngü neden O(log n) çıkar?
Üçüncü örnekte döngü değişkeni her turda yarıya iner. Fonksiyon, n'nin kaç turda 1'e düştüğünü sayar:
def tur_say(n):
tur = 0
while n > 1:
n //= 2
tur += 1
return tur
print(tur_say(16))
print(tur_say(1000))Beklenen çıktı:
4
9n = 16 için değerler 16, 8, 4, 2, 1 şeklinde ilerler ve 4 tur sürer. n = 1000 için 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1 dizisi oluşur ve 9 tur gerekir. Sezgi şu: n kaç kez ikiye bölününce 1'e iner? n iki katına çıkarsa döngüye yalnızca bir tur eklenir. 16'dan 32'ye geçişte tur sayısı 4'ten 5'e çıkar. Büyüme bu kadar yavaş olduğu için sınıf O(log n) diye yazılır. Logaritmanın tabanı Big O'da sabit bir çarpan olduğundan düşer, bu yüzden 2 tabanını yazmana gerek kalmaz. İkili arama gibi algoritmalar bu yarıya indirme fikrini kullanır.
Her döngüde sorman gereken soru şu: döngü değişkeni toplamsal mı azalıyor, çarpımsal mı? Her turda 1 azalan ya da 1 artan döngü O(n) işlem yapar. Her turda yarıya inen (ya da iki katına çıkan) döngü O(log n) işlem yapar.
Yaygın büyüme sınıfları ve Big O'nun sınırları
Aşağıdaki tablo, n iki katına çıktığında işlem sayısının nasıl davrandığını özetler. Tabloda süre değil, yalnızca büyüme davranışı yer alır.
| Büyüme sınıfı | n iki katına çıkınca işlem sayısına ne olur | Tipik kod görünümü |
|---|---|---|
| O(1) | Değişmez | Listede indeksle erişim, tek bir atama |
| O(log n) | Yalnızca bir adım eklenir | Değeri her turda yarıya indiren döngü |
| O(n) | İki katına çıkar | Tek döngü, listeyi baştan sona gezmek |
| O(n log n) | İki katından biraz fazla artar | Verimli sıralama algoritmaları |
| O(n²) | Dört katına çıkar | İç içe iki döngü |
| O(2^n) | Kendi karesine çıkar (n yalnızca 1 artsa bile iki katına çıkar) | Bir kümenin tüm alt kümelerini üretmek |
Big O bir üst sınırdır, kesin bir ölçüm değildir. Küçük n değerlerinde atılan sabitler ve düşük dereceli terimler pratikte fark yaratabilir. Aynı algoritmanın en iyi ve ortalama durumu da en kötü durumdan farklı olabilir. Bellek kullanımını anlatan uzay karmaşıklığı ise ayrı bir konudur. İkili arama, for döngüsü ve uzay karmaşıklığı gibi başlıklara ayrıca bakmak istersen blog arşivimizdeki yazıları gezebilirsin.
Koddan Big O çıkarırken izleyebileceğin inceleme listesi
Önceki üç örnekte yaptığımız işi altı adımlık bir sıraya dökebilirsin. Bu, her kodda işe yarayan sezgisel bir yöntemdir; tek doğru yol değildir, ama düzenli bir bakış alışkanlığı kazandırır.
- n'yi seç: Neyin büyümesi işi büyütüyor? Tek döngü toplamında liste uzunluğu, ikiye bölen
whileörneğinde başlangıçtaki sayı. - Döngü sınırlarını oku: Döngü n kez mi dönüyor, n/2 kez mi, yoksa her turda çarpımsal olarak mı küçülüyor? İkiye bölen döngü son durumdadır.
- Bağımlılığı kontrol et: İç döngünün sınırı dıştaki sayaca bağlı mı? Bağımlı iç içe çift sayımı örneğinde bağlıydı, bu yüzden toplam tam n x n olmadı.
- Blokları topla: Art arda gelen bloklar toplanır, iç içe gelenler çarpılır. Döngü gövdesindeki işlem sayısıyla tur sayısını çarparak toplamı yaz.
- Sabitleri at: 3n işlemi de n işlemi de n ile orantılı büyür; çarpanlar ve sabit işler Big O'da düşer.
- Baskın terimi bırak: n büyüdükçe en hızlı büyüyen terim belirleyicidir. n² + n + 5 için bu n²'dir.
Bir sonraki fonksiyonunu yazarken listeyi baştan sona uygulamayı dene: önce n'yi adlandır, sonra tur sayılarını elle çıkar. Dilden bağımsız düşünme becerini ölçmek istersen ücretsiz Algoritmik Düşünme Testi'ni çözebilirsin.
Karmaşıklık analizi bir kez oturduğunda, kodu çalıştırmadan önce işin nereye doğru büyüyeceğini görmek rutin bir alışkanlığa dönüşür.
