Big O gösteriminde sabitler göz ardı edilir, çünkü Big O belirli bir bilgisayardaki kesin süreyi değil, girdi büyüdükçe maliyetin hangi eğilimle arttığını ifade eder. Sabit bir çarpan ya da eklenen küçük bir değer bu eğilimin biçimini değiştirmez, yalnızca ölçeğini oynatır. Bu yüzden 3n + 5 işlemi O(n), 4n² + 2n + 1 işlemi O(n²) olarak yazılır.
Kısaca: Big O, kodun kaç saniyede çalışacağını değil, girdi büyüdüğünde maliyetin nasıl ölçekleneceğini anlatır. Aşağıda bunu önce sayılarla, sonra kuralla görüyoruz.
Baskın terim nedir: n büyüdükçe 3n + 5 ve 4n² + 2n + 1'de ne kalır?
Bir algoritmanın yaptığı işlem sayısının 3n + 5 olduğunu düşün. Burada n girdinin boyutu. Formülü bir kenara bırakıp değerlere bakalım:
- n = 10 için toplam 35. Sabit 5, toplamın yaklaşık yedide biri.
- n = 100 için toplam 305. Aynı 5 artık yüzde ikinin altında bir paya düştü.
- n = 1000 için toplam 3005. 5'in payı binde birkaç düzeyinde, yani gözle görülmez.
n büyüdükçe toplamı fiilen 3n belirliyor; 5 sabit kaldığı için etkisi eriyor. İşte bu yüzden Big O'da sabit eklentiler atılır.
Üç kavramı şöyle adlandırabiliriz:
- Baskın terim: n yeterince büyüdüğünde toplamın değerini en çok belirleyen, en hızlı büyüyen terim.
- Düşük dereceli terim: Baskın terimden daha yavaş büyüyen terimler. 3n + 5 içinde 5, 4n² + 2n + 1 içinde 2n ve 1.
- Sabit katsayı: Baskın terimin önündeki çarpan. 3n içindeki 3, 4n² içindeki 4.
Aynı mantığı 4n² + 2n + 1 için kuralım. n = 1000 olduğunda toplam 4.000.000 + 2.000 + 1 olur. İşlemlerin neredeyse tamamı 4n² teriminden geliyor; 2n ve 1'in payı görünmez düzeyde. Sabit 4 ise toplamı dört kat büyütüyor ama büyümenin biçimini değiştirmiyor: n iki katına çıktığında n² dört katına, 4n² de yine dört katına çıkar. 4 çarpanı yalnızca ölçeği belirler, eğriyi başka bir eğriye çevirmez.
Bir ifadeyi Big O'ya indirme sırası
- Baskın terimi bul: n büyürken en hızlı artan terimi seç.
- Diğer terimleri at: Daha yavaş büyüyen düşük dereceli terimleri çıkar.
- Sabit çarpanı at: Kalan terimin önündeki katsayıyı sil.
3n + 5 için baskın terim 3n, geriye 3n kalır, çarpan atılınca n gelir: O(n). 4n² + 2n + 1 için baskın terim 4n², çarpan atılınca n²: O(n²).
O(1), O(n) ve O(n²) yan yana: sabit çarpan sınıfı neden değiştirmez?
Üç büyüme sınıfını girdiyi 10 kat büyüterek karşılaştıralım. O(1)'de maliyet yerinde kalır. O(n)'de maliyet yaklaşık 10 kat artar. O(n²)'de maliyet yaklaşık 10 × 10 = 100 kat artar. Sınıfı belirleyen şey, girdi büyürken maliyetin hangi oranla arttığıdır.
Şimdi sabit çarpana bakalım. 3n ile n arasındaki oran her n için tam olarak 3'tür. n = 10'da 30'a karşı 10, n = 1000'de 3000'e karşı 1000 görürsün; aradaki fark sabit bir kat olarak kalır. Girdi 10 katına çıktığında hem n hem 3n yine 10 katına çıkar. İki ifade aynı hızda büyüdüğü için aynı sınıfa girer.
Sabit çarpanın sınıfı değiştirememesinin sebebi budur. Çarpan ne kadar büyük olursa olsun oran sabit kalır. Şimdi 100n ile n² örneğine bakalım. n = 10'da 100n = 1000, n² = 100; büyük sabitli doğrusal ifade daha pahalı görünür. n = 100'de ikisi de 10.000 olur. n = 1000'de 100n = 100.000 iken n² = 1.000.000'dur. n = 10.000'de 1.000.000'a karşı 100.000.000 elde edersin. Küçük n değerlerinde 100'lük çarpan baskın görünse de, n büyüdükçe n²'nin ürettiği fark kapanmaz, açılır. Hiçbir sabit çarpan, daha hızlı büyüyen bir terimi sonsuza kadar geride tutamaz.
Bunu iç içe iki döngüyle de düşünebilirsin: her biri n kez dönen iç içe döngüde işlem sayacı n = 10 için 100, n = 100 için 10.000, n = 1000 için 1.000.000 değerini verir. Bu sayıları bir sonraki bölümde çalışan bir örnekle birlikte göreceğiz.
İki döngüyle işlem sayacı: aynı iş, farklı sabit
Aşağıdaki iki fonksiyon aynı listenin toplamını bulur. Döngü A her eleman için 1 işlem sayar. Döngü B her eleman için 3 işlem (okuma, ekleme, güncelleme) ve başında 5 sabit hazırlık işlemi sayar. Zaman ölçmeyiz, yalnızca işlemleri sayarız.
def dongu_a(liste):
toplam = 0
sayac = 0
for x in liste:
toplam += x
sayac += 1 # her eleman için 1 işlem
return toplam, sayac
def dongu_b(liste):
toplam = 0
sayac = 5 # sabit hazırlık işlemleri
for x in liste:
sayac += 1 # okuma
toplam += x
sayac += 1 # ekleme
sayac += 1 # güncelleme
return toplam, sayac
for n in (10, 100, 1000):
liste = list(range(n))
toplam_a, sayac_a = dongu_a(liste)
toplam_b, sayac_b = dongu_b(liste)
print(n, toplam_a == toplam_b, sayac_a, sayac_b)Beklenen çıktı:
10 True 10 35
100 True 100 305
1000 True 1000 3005İki döngü de aynı toplamı üretir. A'nın sayacı n, B'nin sayacı 3n + 5 olur.
| n | Döngü A sayacı | Döngü B sayacı | B / A oranı |
|---|---|---|---|
| 10 | 10 | 35 | 3,5 |
| 100 | 100 | 305 | 3,05 |
| 1000 | 1000 | 3005 | 3,005 |
Oran 3'e yaklaşır, çünkü + 5 payı n büyüdükçe önemsizleşir. B her zaman yaklaşık 3 kat fazla iş yapar, ama n 10 kat büyüyünce iki sayaç da yaklaşık 10 kat büyür. Büyüme biçimi aynıdır: ikisi de O(n).
Sabitleri ne zaman atarım, ne zaman dikkate alırım?
Big O ile gerçek çalışma süresi aynı şey değildir. Big O, kodun kaç saniyede çalışacağını değil, girdi büyüdüğünde maliyetin nasıl ölçekleneceğini anlatır. Sabit katsayı bu ölçeklenme eğilimini değiştirmediği için gösterimde yer almaz. Ama pratikte seçim yaparken o sabit işine yarayabilir. Sabiti atmak, onu yok saymak değil, sorunun hangi katmanına baktığını bilmektir.
Karar vermek için şu kontrol listesini kullanabilirsin:
- Sabitleri atarım: farklı büyüme sınıflarındaki algoritmaları büyük girdide kıyaslarken (örneğin O(n) ile O(n²)).
- Sabitleri atarım: bir algoritmanın ölçeklenme eğilimini anlatırken.
- Sabitleri dikkate alırım: aynı sınıftaki iki çözüm arasında seçim yaparken.
3nilenher zaman 3 kat fark eder. - Sabitleri dikkate alırım: girdi küçük ve sınırlıyken.
1000n + n²ifadesinde n = 10 için ilk terim 10000, ikincisi 100'dür; n² ancak n yeterince büyüyünce öne geçer. - Sabitleri dikkate alırım: gerçek ölçüm gerektiğinde. Sorunun nerede olduğunu profil çıkarma gösterir, Big O tek başına göstermez.
Sabit atmanın gizlediği şey, büyüme sınıfı aynı olan çözümler arasındaki farktır. Yine de bu fark her durumda belirleyici olmayabilir; hangisinin işe yarayacağı girdinin boyutuna ve çalıştığı ortama göre değişebilir. Kavramı kendin sınamak istersen dilden bağımsız Algoritmik Düşünme Testi iyi bir ölçü olabilir.
c ve n0 ile formal tanım: sezginin matematiksel karşılığı
Şimdiye kadar "baskın terim kalır, sabit çarpan düşer" dedik. Ders kitaplarındaki tanım bu sezgiyi tek bir eşitsizliğe çevirir: Pozitif bir c sabiti ve bir n0 eşiği bulabiliyorsan ve n ≥ n0 olan her n için f(n) ≤ c · g(n) sağlanıyorsa, f(n) = O(g(n)) yazılır. Bu tanım f(n)'nin g(n)'nin sabit katı kadar bir üst sınırın altında kaldığını söyler. Bu yüzden günlük kullanımda Big O bir üst sınır anlamına gelir. Alt ve üst sınırı birlikte, yani sıkı sınırı anlatmak istenirse Theta gösterimi kullanılır.
İki örneği adım adım kontrol edelim.
Örnek 1: 3n + 5 = O(n)
c = 4 seçelim. 3n + 5 ≤ 4n eşitsizliği, iki taraftan 3n çıkarınca 5 ≤ n olur. Yani eşitsizlik n ≥ 5 için sağlanır; n0 = 5 alabiliriz. Kontrol: n = 5'te 3·5 + 5 = 20 ve 4·5 = 20, eşitlik var. n = 4'te 17 ≤ 16 sağlanmaz, bu yüzden eşik 4 olamaz.
Örnek 2: 4n² + 2n + 1 = O(n²)
c = 5 seçelim. 4n² + 2n + 1 ≤ 5n² eşitsizliği, 4n²'yi çıkarınca 2n + 1 ≤ n² olur. n = 3'te n² = 9, 2n + 1 = 7 olduğundan 9 ≥ 7 sağlanır. n = 2'de n² = 4, 2n + 1 = 5 olur ve 4 ≥ 5 sağlanmaz. Bundan sonraki n değerlerinde n² daha hızlı büyüdüğü için eşitsizlik bozulmaz. Böylece n0 = 3 olur.
c ve n0 neyi temsil eder?
c, sabit çarpanı ifade eder: "Gerçek maliyet, g(n)'nin belli bir katını aşmaz" demenin yoludur. Hangi sabit çarpanla başlarsan başla, yeterince büyük bir c seçebildiğin için sabit çarpan sınıfı değiştirmez. n0 ise küçük girdileri dışarıda bırakır. Eşitsizliğin başta sağlanmaması önemli değildir; önemli olan belli bir noktadan sonra hep sağlanmasıdır. Düşük dereceli terimler de çoğunlukla bu eşiğin içinde eriyip gider.
Kavramı kendi başına pekiştirmek için üç mini alıştırma
Cevaplara bakmadan önce kâğıt üzerinde dene.
- İfadeyi indir: 2n² + 3n + 7'nin Big O karşılığını yaz ve gerekçesini tek cümleyle açıkla. Kontrol için c = 3 ile n0 bulmayı da deneyebilirsin. Cevap O(n²); baskın terim 2n² olur, sabit 2 düşer. c = 3 için eşitsizlik 3n + 7 ≤ n² hâline gelir ve n ≥ 5'ten itibaren sağlanır.
- Sayacı tahmin et: Aşağıdaki iç içe döngü n = 10, 100 ve 1000 için sayacı kaça çıkarır? Önce elle tahmin et, sonra çalıştır.
- Ayrışma noktasını bul: 1000n ile n² hangi n değerinde eşitlenir, sonrasında hangisi büyür? n = 500, 1000 ve 2000 değerlerini yerine koyarak kendin dene.
def say(n):
sayac = 0
for i in range(n):
for j in range(n):
sayac += 1
return sayac
for n in (10, 100, 1000):
print(n, say(n))Beklenen çıktı: 10 100, 100 10000, 1000 1000000. Girdi 10 kat büyüdüğünde sayaç 100 kat büyür; n² davranışı tam olarak budur.
Üçüncü alıştırmada n = 1000'de iki ifade de 1.000.000 olur. n = 500'de 1000n = 500.000 iken n² = 250.000'dir. n = 2000'de ise 1000n = 2.000.000 iken n² = 4.000.000'dir. Yani n² küçük girdilerde daha ucuz görünür, 1000'den sonra ise geride kalmaz. Becerini farklı sorularla ölçmek istersen ücretsiz bilgi testleri merkezindeki seviye testlerini deneyebilirsin.
Sık Sorulan Sorular
O(2n) ile O(n) aynı mıdır?
Evet. Buradaki 2n, 2 ile n'nin çarpımıdır ve 2 sabit bir çarpandır. f(n) = 2n için c = 2 ve herhangi bir n0 ile 2n ≤ 2 · n sağlanır, dolayısıyla sınıf O(n) kalır. 2n ise üstel bir büyümedir ve bununla karıştırılmamalıdır.
Düşük dereceli terimler hiçbir zaman önemli olmaz mı?
Küçük girdilerde ya da girdinin hep sınırlı kaldığı durumlarda önemli olabilir. Big O, n büyüdükçe maliyetin hangi eğilimle arttığını anlatır; küçük n için ayrıntılı bir ölçüm sunmaz. Bu yüzden terimler Big O'da atılır, ama gerçek bir projede girdi boyutunu bilmek yine de gerekir.
Sabit katsayısı büyük bir O(n) algoritma, sabit katsayısı küçük bir O(n²) algoritmadan yavaş olabilir mi?
Evet, belli bir girdi boyutuna kadar olabilir. Örneğin 1000n ile n² karşılaştırıldığında n < 1000 için n² daha az işlem yapar. n = 1000'de ikisi eşitlenir ve sonrasında n² büyür. Bu, hangi algoritmanın pratikte daha hızlı olacağının tek başına Big O'dan okunamayacağını gösterir; işlem sayacıyla kendi girdi aralığında karşılaştırma yapabilirsin.
Sabitleri atmak, onları önemsiz saymak anlamına gelmez; yalnızca büyüme sınıfını karşılaştırırken aynı dili kullanmanı sağlar. Bir sonraki algoritmayı incelediğinde önce baskın terimi bul, sonra gerektiğinde c ve n0 ile kendi cevabını sına.
