Fonksiyonların büyümesi ve algoritma karmaşıklığı

Bu hafta vizenin son konusu. Soru tipleri belli ve mekanik: “Show that f is O(g), give witnesses”, “show that f is not O(g)”, “arrange in order of growth” ve “how many times is this line executed?”. Hepsinin bir şablonu var. Altın kurallar:

1. Big-O bir üst sınırdır. Saniye ölçmez, girdi büyüdükçe adım sayısının nasıl büyüdüğünü söyler.
2. Tanıkları (witnesses) ikisini birden yaz: $C$ ve $k$. Biri eksikse puan eksik.
3. Sabit çarpanlar ve küçük terimler önemsiz. $5n^2 + 100n$ ile $n^2$ aynı sınıfta.
4. “O değildir” ispatı her zaman çelişkiyle yapılır. Tanımı varsay, böl, sınırsız bir şeyin sabitten küçük olduğu sonucuna var.
5. Döngü sayarken önce dış döngünün tek bir turunu düşün, sonra turları topla.

Big-O tanımı

$f$ ve $g$ fonksiyonlar olsun. f(x) is O(g(x)) demek şu demek:

$\exists\, C, k \;\; \text{such that} \;\; |f(x)| \le C\,|g(x)| \;\; \text{whenever} \;\; x > k.$

$C$ ve $k$ sabitlerine tanık (witness) denir. Sezgi: bir noktadan sonra ($x > k$) $f$‘nin grafiği, $g$‘nin $C$ katının üstüne hiç çıkmaz. Başlangıçta ne yaptığı önemsiz.

Tanık çifti tek değildir. Bir çift çalışıyorsa daha büyük $C$ veya daha büyük $k$ da çalışır. Sınavda tek doğru çift istenmez, çalışan bir çift istenir.

$\Theta$ = hem $O$ hem $\Omega$. Bu yüzden $\Theta$ sorusunda iki ayrı eşitsizlik yazarsın.

Tanık bulma şablonu

Polinomlar için üç satırlık bir tarif var. Örnek: $f(x) = 4x^2 + 7x + 3$ is $O(x^2)$.

When x > 1 we have x < x^2 and 1 < x^2.
Hence 4x^2 + 7x + 3 <= 4x^2 + 7x^2 + 3x^2 = 14x^2 for x > 1.
So f(x) is O(x^2) with witnesses C = 14 and k = 1.

Hile: $x > 1$ iken küçük kuvvetleri en büyük kuvvete büyütmek serbest, çünkü ifadeyi büyütüyorsun ve eşitsizliğin yönü korunuyor. Sonra katsayıları topla: $4 + 7 + 3 = 14$.

TUZAK · “for x > 1” cümlesi. Eşitsizliğin hangi $x$‘ler için geçerli olduğunu yazmazsan $k$‘yı söylememiş olursun. $0 < x < 1$ aralığında $x > x^2$ olduğu için büyütme hilesi orada çalışmaz; $k = 1$ tam olarak bu yüzden.

Theta: alt sınır bedava

$f(n) = 3n^2 + 5n + 2$ is $\Theta(n^2)$:

• Üst sınır: $n > 1$ için $3n^2 + 5n + 2 \le 3n^2 + 5n^2 + 2n^2 = 10n^2$, yani $C_2 = 10$.
• Alt sınır: pozitif terimleri atınca ifade küçülür: $3n^2 + 5n + 2 \ge 3n^2$, yani $C_1 = 3$.

Sonuç: $n > 1$ için $3n^2 \le f(n) \le 10n^2$. Üç sabiti ($C_1 = 3$, $C_2 = 10$, $k = 1$) birlikte yaz.

Negatif katsayı varsa ($5n^2 - 3n$ gibi) alt sınır bedava değildir. O zaman $3n \le n^2$ gibi bir eşitsizlik kullanıp $k$‘yı büyütürsün. Vizede genelde pozitif katsayılı polinom gelir.

“O değildir” ispatı (çelişki)

Bir fonksiyonun $O(g)$ olmadığını göstermek için örnek yetmez; tanımın hiçbir $C, k$ ile sağlanamayacağını göstermen gerekir. Şablon çelişkidir. Örnek: $n^3$ is not $O(7n^2)$.

Proof. Suppose, for contradiction, that n^3 is O(7n^2).
Then there are constants C and k with n^3 <= C * 7n^2 for all n > k.
Dividing both sides by n^2 > 0 gives n <= 7C for all n > k.
But this fails for any integer n > max(k, 7C).
This is a contradiction, so n^3 is not O(7n^2). ∎

Türkçesi: bölme işleminden sonra “sınırsız büyüyen $n$, sabit $7C$‘den hep küçük” gibi saçma bir sonuç çıkıyor. Hangi $C$‘yi seçersen seç, $n = 7C + 1$ ve sonrası bunu bozar. Mesela $C = 50$ için $n = 351$: $351^3 > 350 \cdot 351^2$.

İPUCU · aynı şablon üstellerde. $4^n$ is not $O(2^n)$: $4^n \le C\cdot 2^n$ varsay, iki tarafı $2^n$‘e böl, $2^n \le C$ çıkar. $2^n$ sınırsız. Çelişki.

Büyüme sıralaması

Küçükten büyüğe, ezberlenecek zincir:

$1 \;<\; \log n \;<\; \sqrt{n} \;<\; n \;<\; n\log n \;<\; n^2 \;<\; n^3 \;<\; 2^n \;<\; 3^n \;<\; n!$

Kurallar:

• Toplamda en hızlı büyüyen terim kazanır: $n^2 + 1000n + \log n$ is $O(n^2)$.
• Çarpımda sınırlar çarpılır: $(n^2 + 3)\log n$ is $O(n^2 \log n)$.
• Logaritmanın tabanı önemsiz: $\log_2 n = (\log_2 10)\log_{10} n$, sadece sabit çarpan.
• Üsse sabit eklemek önemsiz, üssü çarpmak önemli: $2^{n+3} = 8\cdot 2^n$ is $O(2^n)$; ama $2^{2n} = 4^n$ değil.
• Tabanı 1’den büyük her üstel, her polinomu sonunda geçer: $(1.1)^n$ bile $n^{100}$‘ü geçer.

Algoritmaların karmaşıklığı

Zaman karmaşıklığı (time complexity): algoritmanın yaptığı temel işlem (karşılaştırma, toplama) sayısının girdi boyutu $n$‘e göre ifadesi. Genelde en kötü durum (worst-case) sorulur: girdi ne kadar kötü olursa olsun en fazla kaç işlem.

Örnekler: 50 elemanlı listede olmayan bir sayıyı linear search 50 karşılaştırmayla arar. 1024 elemanlı sıralı listede binary search (aralık 1 elemana inene kadar) $1024 \to 512 \to \dots \to 1$, yani 10 tur. 10 elemanlı ters sıralı listede bubble sort $9 + 8 + \dots + 1 = 45$ karşılaştırma yapar.

Döngü sayma: adım adım

for i := 1 to n
    for j := i to n
        x := x + 1

Önce tek bir dış turu düşün: $i$ sabitken $j$, $i$‘den $n$‘e gider, yani $n - i + 1$ tur.

i = 1  ->  n tur
i = 2  ->  n - 1 tur
...
i = n  ->  1 tur
Toplam: n + (n-1) + ... + 1 = n(n+1)/2

$n = 8$ için $\frac{8 \cdot 9}{2} = 36$. Big-O tahmini: $\frac{n(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n \le n^2$ ($n \ge 1$), yani $O(n^2)$. Yarım $n^2$ bile olsa sınıf $n^2$.

Döngü değişkeni çarpılarak büyüyorsa ($i := 2i$) tur sayısı logaritmiktir. Bölünerek küçülüyorsa ($i := \lfloor i/2 \rfloor$) yine logaritmik.

Sık yapılan hatalar

for i := 1 to n
    for j := 1 to 2n
        x := x + 1

i := 1; j := 64
while i < j
    m := floor((i + j) / 2)
    if x > a_m then i := m + 1
    else j := m

i := 1
while i <= n
    i := 2 * i

for i := 1 to n
    for j := 1 to i
        for k := 1 to j
            s := s + 1