Asimptotik Gösterim

Önceki ders, ölçütü işlem sayısı olarak belirledi ama bir sorun bıraktı: bin elemanlık bir dizide 1000 mü, 1002 mi karşılaştırma yapıldığı önemsizdir. Bu ayrıntılar gerçekleştirime bağlıdır; algoritmanın kendisine ait olan, girdi büyüdükçe işlem sayısının hangi hızla arttığıdır.

Asimptotik gösterim, bu hızı yakalayan ve gerisini eleyen dildir.

Büyük O: Üst Sınır

$f$ ve $g$, pozitif tam sayılardan pozitif gerçel sayılara fonksiyonlar olsun.

$$f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \in \mathbb{N} : \forall n \geq n_0,\ f(n) \leq c \cdot g(n)$$

Sözle: yeterince büyük her $n$ için $f$, $g$’nin sabit bir katını aşmıyorsa, $f$ en fazla $g$ kadar hızlı büyür.

Tanımın iki niceleyicisi de gereklidir. Sabit $c$, çarpansal farkları eler — iki katı hızlı çalışan bir gerçekleştirim aynı sınıfta kalır. Eşik $n_0$ ise küçük girdilerdeki düzensizlikleri eler; asimptotik ifade, büyük girdiler hakkında bir iddiadır.

Bir örnek üzerinde açıkça gösterilebilir. $f(n) = 3n^2 + 5n + 20$ için $g(n) = n^2$ seçilirse, $c = 4$ ve $n_0 = 8$ değerleri tanımı sağlar:

def f(n: int) -> int:
    return 3 * n**2 + 5 * n + 20

c, n0 = 4, 8
print(f(7) <= c * 7**2)            # False  — eşiğin altında sağlanmıyor
print(f(8) <= c * 8**2)            # True
print(all(f(n) <= c * n**2 for n in range(n0, 10_000)))    # True

Yedide sağlanmaması bir sorun değildir: tanım, eşikten sonrası için bir şey söyler. Sekizden itibaren eşitsizlik hep geçerlidir; dolayısıyla $3n^2 + 5n + 20 = O(n^2)$ yazılır.

Büyük Omega: Alt Sınır

$$f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \geq n_0,\ f(n) \geq c \cdot g(n)$$

Büyük O bir tavan, büyük omega bir taban verir. “Bu algoritma en az şu kadar iş yapar” demek için kullanılır.

Alt sınırlar, tek bir algoritma için değil problem için konuşulduğunda güçlüdür: “karşılaştırmalı sıralama en az $\Omega(n \log n)$ karşılaştırma gerektirir” ifadesi, hiçbir karşılaştırmalı algoritmanın bu sınırın altına inemeyeceğini söyler. Bu tür bir sonuç, arama ve sıralama konusunda kanıt fikriyle birlikte ele alınacaktır.

Büyük Teta: Sıkı Sınır

$$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \ \text{ ve } \ f(n) = \Omega(g(n))$$

Teta, büyümenin tam olarak $g$ mertebesinde olduğunu söyler: hem tavan hem taban aynı fonksiyondur.

$3n^2 + 5n + 20$ ifadesi $\Theta(n^2)$’dir. Aynı ifade $O(n^3)$ de olur — üst sınır gevşek olabilir — ancak $\Theta(n^3)$ değildir.

Günlük kullanımda büyük O, çoğu zaman sıkı sınır kastedilerek yazılır. Bu bir kolaylıktır; kesin konuşulması gereken yerlerde teta tercih edilir.

Sadeleştirme Kuralları

Karmaşıklık ifadeleri birkaç kuralla sadeleşir.

Sabit çarpanlar elenir. $O(3n) = O(n)$. Sabit, tanımdaki $c$ tarafından zaten soğurulur.

Toplamda büyük terim kalır. $O(n^2 + n) = O(n^2)$. Ardışık iki bölümden pahalı olanı belirleyicidir.

Çarpımda çarpanlar korunur. İç içe döngülerde maliyetler çarpılır: $O(n) \cdot O(\log n) = O(n \log n)$.

Geçişlilik geçerlidir. $f = O(g)$ ve $g = O(h)$ ise $f = O(h)$’dir.

İfade	Sadeleşmiş	Gerekçe
$5n + 100$	$O(n)$	Sabitler ve sabit terim elenir
$n^2 + 1000n$	$O(n^2)$	Büyük terim baskın
$\log_2 n$ ile $\log_{10} n$	Aynı $O(\log n)$	Taban değişimi sabit çarpandır
$2^{n+1}$	$O(2^n)$	$2^{n+1} = 2 \cdot 2^n$
$n!$ ile $2^n$	Farklı sınıflar	Faktöriyel üstelden hızlı büyür

Üçüncü satır sık sorulan bir noktayı yanıtlar: logaritmanın tabanı belirtilmez, çünkü taban değişimi yalnızca sabit bir çarpan üretir ve o çarpan elenir.

Sabit ve Eşiği Bulmak

Bir iddiayı kanıtlamak, uygun bir $c$ ve $n_0$ üretmek demektir. Polinomlar için mekanik bir yöntem vardır: her düşük dereceli terim, $n \geq 1$ için baskın terimle sınırlanır ve katsayılar toplanır.

$f(n) = 3n^2 + 5n + 20$ örneğinde $n \geq 1$ için $5n \leq 5n^2$ ve $20 \leq 20n^2$ yazılabilir. Toplandığında $f(n) \leq 28n^2$ çıkar; yani $c = 28$, $n_0 = 1$ da tanımı sağlayan geçerli bir çifttir.

Yukarıda $c = 4$ ile daha küçük bir sabit bulundu, ama gerekli değildi: tanım bir çiftin varlığını ister, en küçüğünü değil. Bu, asimptotik iddiaların neden kolay kanıtlandığını açıklar — kaba bir sınır bile yeterlidir.

Yaygın Yanlış Okumalar

“$O(n)$ demek, tam olarak $n$ işlem demek değildir.” Üst sınırdır; $3n$ ve $n/2$ ikisi de $O(n)$’dir.

“$O$ en kötü durum demek değildir.” İkisi ayrı eksenlerdir. En iyi, en kötü ve ortalama durumların her biri için ayrı ayrı $O$, $\Omega$ ve $\Theta$ yazılabilir. “En kötü durumda $O(n^2)$” ile “her durumda $O(n^2)$” farklı iddialardır.

“Küçük $O$ her zaman daha iyi değildir.” Asimptotik gösterim sabitleri elediği için, $O(n \log n)$ bir algoritma küçük girdilerde $O(n^2)$ bir algoritmadan yavaş olabilir. Bu, sıralama kütüphanelerinin küçük parçalara farklı algoritma uygulamasının nedenidir.

Gösterim bir eşitlik değildir. $f(n) = O(g(n))$ yazımı yerleşmiştir ama yanıltıcıdır; doğrusu $f \in O(g)$ biçiminde bir küme üyeliğidir. Bu nedenle eşitlik simetrik değildir: $O(n) = f(n)$ yazılmaz.

Girdi Büyüklüğü Nedir

Son bir tanım gerekir: $n$ neyi sayar? Yanıt probleme göre değişir ve belirtilmezse ifade anlamsızdır.

• Dizi işlemlerinde eleman sayısı.
• Metin algoritmalarında karakter sayısı.
• Çizge algoritmalarında hem düğüm hem kenar sayısı — bu yüzden maliyetler $O(V + E)$ gibi iki değişkenle yazılır.
• Sayısal algoritmalarda genellikle sayının bit uzunluğu; sayının kendisi değil.

Son madde ince bir ayrımdır. Bir sayının asal olup olmadığını sayıya kadar bölerek sınayan yöntem, girdi olarak sayının değeri alınırsa $O(\sqrt{N})$ görünür; oysa girdi $N$ değil, onu yazmak için gereken bit sayısıdır. Bit uzunluğu cinsinden aynı yöntem üsteldir. Bu ayrım, karmaşıklık kuramında sınıflandırmanın temelidir ve Hesaplama Kuramı kursunda ele alınır.

Özet

• Asimptotik gösterim, sabitleri ve düşük dereceli terimleri eleyerek büyüme hızını tutar.
• Büyük O üst sınır, büyük omega alt sınır, büyük teta sıkı sınır verir.
• Tanımdaki $c$ sabiti çarpansal farkları, $n_0$ eşiği küçük girdileri eler.
• Sadeleştirmede sabitler elenir, toplamda büyük terim kalır, çarpımda çarpanlar korunur; logaritmanın tabanı yazılmaz, çünkü taban değişimi sabit çarpandır.
• $O$ ile “en kötü durum” farklı eksenlerdir; küçük asimptotik sınıf, küçük girdilerde hızlı olmayı garanti etmez.
• Girdi büyüklüğünün ne sayıldığı açıkça belirtilmelidir.

Sonraki Adım

Büyük O ve omega, sınırın sıkı olup olmadığını söylemez: $n$ hem $O(n)$ hem $O(n^2)$’dir. Sonraki ders, sınırın kesinlikle gevşek olduğunu belirten küçük gösterimlerini tanımlayacak ve bunların hangi ifadeleri mümkün kıldığını gösterecek.