Running time nedir?
Saniye bilgisayara ve dile göre değişir. Biz onun yerine basic operation sayısını sayarız: comparison, assignment, addition. Her biri constant time sürer. $n$ input size, $T(n)$ de $n$ boyutlu bir input'ta yapılan operation sayısıdır.
Karşında bir adversary olduğunu düşün. Sen algoritmayı ve bir $T(n)$ bound'unu söylüyorsun, adversary en kötü input'u seçiyor. Algoritma her input'ta $T(n)$ içinde bitiyorsa bound doğrudur. Bu yüzden worst-case bound her input için geçerli bir garantidir.
Her soru worst case sorusu değildir. "Bu özel input'ta running time ne?" diye de sorulabilir: bir bloğu ters çevrilmiş array, bütün element'leri eşit array, zaten sorted array. Önce input'un ne olduğunu oku, sonra say.
CS161 notlarındaki örnek: MergeSort en fazla $11n\log n + 11n$ operation yapar, InsertionSort yaklaşık $n^2/2$. Constant'lar (11, ½) dile ve makineye göre değişir. Onları atar, yalnızca growth rate'e bakarız. Buna asymptotic analysis denir.
Adversary oyunu: en kötü input hangisi?
Adversary'nin yerine sen geç. Küçük bir array'in bütün permütasyonlarını InsertionSort'a ver ve her birinde kaç comparison ($A[j] > key$ testi) yapıldığını say. Worst-case bound, bu sayıların en büyüğüdür.
Önce tahmin et: $n = 5$ için en kötü input kaç comparison yapar, en iyi input kaç? En kötüsü hangi input?
Growth rate
Oynat'a bas. $n$ büyüdükçe function'ların arası açılıyor. Çubuklar logarithmic scale'de çizildiği için gerçek fark göründüğünden çok daha büyük.
$1 \prec \log n \prec \sqrt n \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n!$
Kısaca: constant < log < square root < polynomial < exponential.
log n nereden çıkar? $n$'i 1'e inene kadar kaç kez ikiye bölebilirsin? $n=32$ için 5, $n=1024$ için 10. Her adımda yarıya inen bir şey varsa orada $\log n$ vardır. Bu derste log'un base'i hep 2.
$n = 1024$ iken $n\log n$ kaçtır?
Makine süresi
Operation sayısını saniyeye çevirince fark somutlaşır. Makinenin saniyede $10^8$ basic operation yaptığını varsay ve $n$'i kaydır.
Önce tahmin et: $n = 10^7$ iken $n^2$ operation yapan algoritma bir dakikada biter mi, yoksa günler mi sürer?
Çubuklar süreyi logarithmic scale'de, en yavaş algoritmaya göre gösterir.
O, Ω, Θ definition'ları
Öyle bir constant $c$ ve başlangıç noktası $n_0$ seçebilirim ki $n_0$'dan sonra $T$ hep $c\cdot f$'nin altında kalır.
"Bir $c$ ve bir $n_0$ vardır, öyle ki her $n \ge n_0$ için…" Doğrusu bu. "Her $c$ için bir $n_0$ vardır" küçük $o$'nun definition'ıdır (Bölüm 6). $c$ ve $n_0$'ı sen seçersin, ikisi de $n$'e bağlı olamaz.
Grafikte gör
Örnek seç, $c$'yi kaydır. Yeşil bölge $T(n) \le c\cdot f(n)$'in hep sağlandığı yer. Bölgenin başladığı nokta $n_0$. Kırmızı noktalar inequality'nin bozulduğu $n$'ler. $n_0$'ın solundaki gri alan önemsiz bölge: definition oraya hiç bakmaz.
$f(n) = O(g(n))$ ise aşağıdakilerden hangisi her zaman doğrudur?
Proof kalıbı: O olduğunu göster
- Hedef inequality'yi yaz: $T(n) \le c\cdot f(n)$.
- Her term'i $f(n)$'e doğru büyüt. $n \ge 1$ iken $n \le n^2 \le n^3$ gibi inequality'leri kullan.
- $c$ ve $n_0$'ı sayı olarak yaz, "for all $n \ge n_0$" ile bitir.
$c = 2,\ n_0 = 1$: $n \ge 1$ iken $n^2 \le n^3$, yani $2n^2 \le 2n^3$. Başka seçim de olur: $c=1,\ n_0=2$ için $2n^2 \le n^3 \iff 2 \le n$. Tek bir doğru $(c, n_0)$ yok, bir tane bulman yeter.
İki tarafı $n^2$'ye böl: $2 + \tfrac1n \le c$. $n \ge 1$ iken $\tfrac1n \le 1$, yani $c = 3,\ n_0 = 1$.
$2n^2 + 10 = O(n^2)$: $c = 3,\ n_0 = 4$ ($10 \le n^2 \iff n \ge 4$).
$n^3 + n^2 + n + 2026 = O(n^3)$: $c = 4,\ n_0 = 2026$. $n \ge 2026$ iken her term $\le n^3$ (çünkü $2026 \le n \le n^3$), toplam $\le 4n^3$.
Ders: Constant term büyükse $n_0$'ı da o kadar büyük seç.
Degree'si $k$ olan her polynomial $O(n^k)$'dir. $a^* = \max_i |a_i|$ ve $n_0 = 1$ seç: her term $\le a^* n^k$, toplam $\le (k+1)a^* n^k$, yani $c = (k+1)a^*$.
"Let $f(n) \ge 0$, $g(n) \ge 0$ be two functions, and $a > 0$ be a constant. State whether the statements below are true or not. For each statement that you think is true, show that it is true with a formal argument based on the definitions of asymptotic notations. For false statements, give a counter-example.
(b) If $f(n) = O(n^a)$, then $f(2n) = O(n^a)$."
İpucu 1
Varsayımı definition ile yaz: her $m \ge n_0$ için $f(m) \le c\,m^a$. Bu inequality'yi $m = 2n$ için kullanabilir misin? $n \ge n_0$ ise $2n$ de $n_0$'dan büyük mü?
İpucu 2
$(2n)^a = 2^a n^a$. $a$ sabit olduğu için $2^a$ da bir constant.
Çözümü göster
True.
$f(n) = O(n^a)$ olduğu için bir $c > 0$ ve bir $n_0$ vardır, öyle ki her $m \ge n_0$ için $0 \le f(m) \le c\,m^a$.
$n \ge n_0$ olsun. O zaman $2n \ge n \ge n_0$, yani inequality'yi $m = 2n$ için yazabiliriz:
$$f(2n) \le c\,(2n)^a = (2^a c)\, n^a .$$$c' = 2^a c$ ve aynı $n_0$ ile her $n \ge n_0$ için $0 \le f(2n) \le c'\, n^a$. Definition sağlanıyor, yani $f(2n) = O(n^a)$. ∎
Neden çalıştı? Argümanı iki katına çıkarmak bir polynomial'ı yalnızca constant factor kadar büyütür. Exponential function'da bu bozulur (Bölüm 5'teki S3(a)).
(Sorunun bu bölümle ilgili kısmı; yönerge S3(b) ile aynı.) "(d) If $f(n) \ge 1$, then $f(n) + a = O(f(n))$."
İpucu 1
Hedef: $f(n) + a \le c\,f(n)$. Constant $a$'yı $f(n)$ cinsinden yukarıdan sınırlaman lazım. $f(n) \ge 1$ şartı tam bunun için verilmiş.
İpucu 2
$f(n) \ge 1$ ve $a > 0$ ise $a = a \cdot 1 \le a\,f(n)$.
Çözümü göster
True. $c = a + 1$ ve $n_0 = 1$ seç.
Her $n \ge 1$ için $f(n) \ge 1$ ve $a > 0$ olduğundan $a \le a\,f(n)$. O zaman
$$0 \le f(n) + a \le f(n) + a\,f(n) = (a+1)\,f(n).$$Definition $c = a+1,\ n_0 = 1$ ile sağlanıyor, yani $f(n) + a = O(f(n))$. ∎
$f(n) \ge 1$ şartı olmasa ne olur? Bölüm 5'teki 2019-20 quiz S2(b) tam olarak bunu soruyor ve orada cevap False.
$5n^2 + 3n + 7 = O(n^2)$ için hangi $(c, n_0)$ çifti çalışmaz?
Disprove kalıbı: O değil
- "Diyelim ki $T = O(f)$. O zaman bir $c$ ve $n_0$ vardır, öyle ki $\forall n \ge n_0$: $T(n) \le c\,f(n)$."
- Sadeleştir: bir tarafta sınırsız büyüyen bir ifade, öbür tarafta constant $c$ kalsın.
- "$n = \max(n_0, \ldots)$ seçince sol taraf $c$'yi geçer. Contradiction."
Diyelim ki her $n \ge n_0$ için $n^k \le c\, n^{k-1}$. İki tarafı böl: $n \le c$. Ama $n = \max(n_0, c+1)$ için $n > c$. Contradiction. ∎
| İfade (slayt) | Sonuç | Neden |
|---|---|---|
| $10^9 n^2 = O(n^2)$ | Doğru | $c = 10^9$. Constant ne kadar büyük olursa olsun sorun değil. |
| $100 n^{1.9999} = O(n^2)$ | Doğru | $c = 100,\ n_0 = 1$. |
| $10^{-9} n^{2.0001} = O(n^2)$ | Yanlış | $10^{-9} n^{0.0001} \le c$ gerekir ama sol taraf sınırsız büyür. |
| $10^{-8} n^2 = \Theta(n)$ | Yanlış | Ω(n) doğru ama O(n) yanlış: $10^{-8} n \le c_2$ contradiction verir. |
$16^n$'in $O(2^n)$ olmadığını göster.
İpucu 1
$16^n = (2^4)^n$. $16^n \le c\, 2^n$ inequality'sinin iki tarafını $2^n$'e böl.
İpucu 2
Geriye $8^n \le c$ kalır. $8^n$ sınırsız büyür, $n > \log_8 c$ seçince contradiction çıkar.
(Sorunun bu bölümle ilgili kısmı; ifadenin doğru mu yanlış mı olduğuna karar ver.) "Considering functions $f(n) \ge 0$, $g(n) \ge 0$ and constant $b > 0$.
b. $f(n) + b = O(f(n))$"
İpucu 1
Bölüm 4'teki pratik vize S3(d) ile karşılaştır. Orada $f(n) \ge 1$ şartı vardı. Burada sadece $f(n) \ge 0$ var. $f$ sıfıra yaklaşırsa ne olur?
İpucu 2
$f(n) = \frac1n$ dene. $\frac1n + b \le c \cdot \frac1n$ inequality'sinin iki tarafını $n$ ile çarp.
Çözümü göster
False. Counterexample: $f(n) = \frac1n$ (her $n \ge 1$ için $f(n) \ge 0$).
Diyelim ki $\frac1n + b = O(\frac1n)$. O zaman bir $c$ ve $n_0$ vardır, öyle ki her $n \ge n_0$ için $\frac1n + b \le \frac{c}{n}$. İki tarafı $n$ ile çarp:
$$1 + b\,n \le c .$$$b > 0$ olduğu için sol taraf sınırsız büyür. $n = \max(n_0,\ \lceil c/b \rceil + 1)$ seçince $b\,n > c$, yani $1 + b\,n > c$. Contradiction. ∎
Daha kısa bir counterexample: $f(n) = 0$. O zaman $b \le c \cdot 0 = 0$ gerekir, ama $b > 0$.
Ders: $f$ bir pozitif constant'ın altına inebiliyorsa constant $b$ onu domine eder. $f(n) \ge 1$ gibi bir şart varsa ifade doğru olur (S3(d)).
"Let $f(n) \ge 0$, $g(n) \ge 0$ be two functions, and $a > 0$ be a constant. State whether the statements below are true or not. For each statement that you think is true, show that it is true with a formal argument based on the definitions of asymptotic notations. For false statements, give a counter-example.
(a) $f(2n) = \Theta(f(n))$."
İpucu 1
Polynomial'larda doğru: $(2n)^2 = 4n^2 = \Theta(n^2)$. Daha hızlı büyüyen bir function dene.
İpucu 2
$f(n) = 2^n$ ise $f(2n) = 2^{2n} = 4^n$. $4^n / 2^n$ neye gider?
Çözümü göster
False. Counterexample: $f(n) = 2^n$. O zaman $f(2n) = 2^{2n} = 4^n$.
$4^n = \Theta(2^n)$ olsaydı $4^n = O(2^n)$ de olurdu: bir $c$ ve $n_0$ için her $n \ge n_0$'da $4^n \le c\,2^n$. İki tarafı $2^n$'e böl: $2^n \le c$. $n = \max(n_0,\ \lceil \log c \rceil + 1)$ seçince $2^n > c$. Contradiction. Yani $f(2n) \ne \Theta(f(n))$. ∎
Θ'nın bozulan tarafı O tarafı. Ω tarafı ($4^n \ge 2^n$) sağlanıyor ama Θ için ikisi birden gerekir.
(Sorunun bu bölümle ilgili kısmı; yönerge S3(a) ile aynı.) "(c) If $f(n) = O(g(n))$, $\log(f(n)) \ge 0$ and $\log(g(n)) \ge 0$, then $\log(f(n)) = O(\log(g(n)))$"
İpucu 1
$\log g(n)$ sıfır olabilir. O zaman $c \cdot \log g(n)$ kaç olur?
İpucu 2
Constant function'lar da function'dır: $f(n) = 2$, $g(n) = 1$ dene.
Çözümü göster
False. Counterexample: $f(n) = 2$, $g(n) = 1$.
- Şartlar sağlanıyor: $f(n) = 2 \le 2 \cdot g(n)$, yani $c = 2,\ n_0 = 1$ ile $f = O(g)$. Ayrıca $\log f(n) = 1 \ge 0$ ve $\log g(n) = 0 \ge 0$.
- Sonuç sağlanmıyor: $\log f = O(\log g)$ için her $n \ge n_0$'da $1 \le c \cdot 0 = 0$ gerekir. Bu hiçbir $c$ için doğru değil.
İfadeyi bozan, $\log g(n)$'nin 0'da kalması. $g(n) \ge 2$ (yani $\log g(n) \ge 1$) şartı olsaydı ifade doğru olurdu: $c \ge 1$ alırsak $\log f \le \log c + \log g \le (\log c + 1)\log g$.
Θ proof'u, o ve ω
$c_1 n^2 \le \tfrac12 n^2 - 2n \le c_2 n^2$. $n^2$'ye böl: $c_1 \le \tfrac12 - \tfrac2n \le c_2$.
- Sağ taraf: her $n\ge1$ için $\tfrac12 - \tfrac2n \le \tfrac12$, yani $c_2 = \tfrac12$.
- Sol taraf: $n = 5$'te $\tfrac12 - \tfrac25 = \tfrac1{10}$ ve $n$ büyüdükçe artıyor, yani $c_1 = \tfrac1{10},\ n_0 = 5$.
Θ için iki inequality'yi ayrı kur, iki constant ve tek bir $n_0$ ver (iki $n_0$'ın büyüğü).
(Sorunun bu bölümle ilgili kısmı; ifadenin doğru mu yanlış mı olduğuna karar ver.) "Considering functions $f(n) \ge 0$, $g(n) \ge 0$ and constant $b > 0$.
a. $\max\{f(n), g(n)\} = \Theta(f(n) + g(n))$"
İpucu 1
İki sayıdan büyüğü, ikisinin toplamını geçebilir mi? $f$ ve $g$'nin negatif olmadığını unutma.
İpucu 2
Toplam, büyüğün en fazla iki katıdır: $f + g \le 2\max\{f, g\}$.
Çözümü göster
True. $h(n) = \max\{f(n), g(n)\}$ diyelim. $c_1 (f+g) \le h \le c_2 (f+g)$ olacak şekilde constant'lar arıyoruz.
- Upper bound: $f, g \ge 0$ olduğu için büyüğe öbürünü eklemek onu küçültmez: $h(n) \le f(n) + g(n)$. Yani $c_2 = 1$.
- Lower bound: $f \le h$ ve $g \le h$, topla: $f + g \le 2h$, yani $\tfrac12 (f+g) \le h$. Yani $c_1 = \tfrac12$.
$c_1 = \tfrac12,\ c_2 = 1,\ n_0 = 1$ ile her $n \ge 1$ için $\tfrac12 (f(n)+g(n)) \le \max\{f(n),g(n)\} \le f(n)+g(n)$. Θ definition'ı sağlanıyor. ∎
Not: Dosyada satır içinde "→FALSE" yazıyor. Bu işaret yanlış: $\max \le f+g \le 2\max$ olduğu için ifade doğru (True). ($b$ bu şıkta kullanılmıyor, (b) şıkkı için verilmiş.)
- $f = o(g)$: her $c>0$ için bir $n_0$ vardır ki $f < c\,g$. Sezgi: $\lim f/g = 0$. Örnek: $2n = o(n^2)$ ama $2n^2 \ne o(n^2)$.
- $f = \omega(g)$: $\lim f/g = \infty$.
- Benzetme: $O \approx\ \le$, $o \approx\ <$, $\Theta \approx\ =$, $\Omega \approx\ \ge$, $\omega \approx\ >$.
"Find 2 functions $f(n)$ and $g(n)$ that satisfy each of relationship. If no such $f$ and $g$ exist, explain why?
a. $f(n) \in O(g(n))$ and $f(n) \notin \Theta(g(n))$
b. $f(n) \in \Theta(g(n))$ and $f(n) \in O(g(n))$
c. $f(n) \in \Theta(g(n))$ and $f(n) \notin O(g(n))$
d. $f(n) \in \Omega(g(n))$ and $f(n) \notin O(g(n))$"
İpucu 1
Θ, O ile Ω'nın birlikte sağlanması demek. (a)'da O var ama Θ yok. O zaman eksik olan hangisi?
İpucu 2
(c)'de Θ'nın definition'ını aç: $c_1 g \le f \le c_2 g$. Sağdaki inequality tek başına neyin definition'ı?
Çözümü göster
- $f = n,\ g = n^2$. O: $n \ge 1$ iken $n \le 1 \cdot n^2$ ($c = 1,\ n_0 = 1$). Θ değil, çünkü Ω tarafı bozuk: $c\,n^2 \le n$ demek $n \le 1/c$ demek, $n > 1/c$ seçince contradiction.
- $f = n,\ g = n$. $c_1 = c_2 = 1,\ n_0 = 1$ ile $f = \Theta(g)$. Θ zaten O'yu içerdiği için $f = O(g)$ de doğru.
- Böyle $f, g$ yok. $f \in \Theta(g)$ ise bir $c_1, c_2, n_0$ için her $n \ge n_0$'da $c_1 g(n) \le f(n) \le c_2 g(n)$. Sağdaki inequality, $c = c_2$ ile O'nun definition'ının ta kendisi. Yani $\Theta(g) \subseteq O(g)$ ve $f \notin O(g)$ olamaz.
- $f = n^2,\ g = n$. Ω: $n \ge 1$ iken $n^2 \ge 1 \cdot n$. O değil: $n^2 \le c\,n$ demek $n \le c$ demek, $n = \max(n_0, c+1)$ seçince contradiction.
(Sorunun bu bölümle ilgili kısmı.) "True or False (10 points total). Circle your final answers.
(c) $\log n$ is $o(n^{.01})$
(d) $\log n$ is $\omega(\log\log n)$"
İpucu 1
o ve ω için limite bak: $\lim_{n\to\infty} f(n)/g(n)$ 0 mı, ∞ mu?
İpucu 2
(c)'de $\log n = \ln n / \ln 2$ yaz ve L'Hôpital uygula. (d)'de $m = \log n$ koy.
Çözümü göster
(c) True. Pay ve payda sonsuza gidiyor, L'Hôpital uygulanır:
$$\lim_{n\to\infty} \frac{\log n}{n^{0.01}} = \lim_{n\to\infty} \frac{\frac{1}{n \ln 2}}{0.01\, n^{-0.99}} = \lim_{n\to\infty} \frac{100}{\ln 2 \cdot n^{0.01}} = 0 .$$Limit 0 ise her $c > 0$ için bir $n_0$ vardır ki $n \ge n_0$'da $\log n < c\,n^{0.01}$. Bu o'nun definition'ı.
Tuzak: küçük $n$'de tablo tersine görünür. $n = 2^k$ koyunca $\log n = k$ ve $n^{0.01} = 2^{k/100}$ olur. $k \le 996$ için $k$ daha büyük, yani $\log n$ ancak $n = 2^{997}$ civarında geride kalıyor. Definition yalnızca $n \ge n_0$'a baktığı için cevap yine True.
(d) True. $m = \log n$ koy. $n \to \infty$ iken $m \to \infty$ ve
$$\frac{\log n}{\log\log n} = \frac{m}{\log m} \to \infty ,$$çünkü (c)'deki sonuca göre log, her polynomial'dan (burada $m^1$'den) yavaş büyür. Limit ∞ olduğu için $\log n = \omega(\log\log n)$.
Kurallar ve tuzaklar
- Sum: $f = O(h)$ ve $g = O(h)$ ise $f+g = O(h)$. Proof: $f \le c_1 h$ ($n\ge n_1$), $g \le c_2 h$ ($n \ge n_2$) ⇒ $f+g \le (c_1+c_2)h$, $n \ge \max(n_1,n_2)$.
- Product: $f = O(F)$, $g = O(G)$ ⇒ $fg = O(FG)$. Nested loop'larda çarparsın.
- Constant factor: $c\cdot f = \Theta(f)$.
- Symmetry: $f = O(g) \iff g = \Omega(f)$.
- "MergeSort is $O(n^2)$" doğru ama yanıltıcı: O bir upper bound'dur ve burada tight değildir. Tight cevap $\Theta(n\log n)$. (Hocanın class-prep sorusu 11)
- "En az $O(n^2)$" anlamsız: lower bound söylemek için Ω kullan.
- $f = O(g)$ olması $2^f = O(2^g)$ demek değildir: $f = 2n,\ g = n$ ⇒ $4^n$ vs $2^n$, ratio $2^n$ ve sınırsız büyür. (CS161 concept check)
- Küçük $n$'ler önemsiz: definition yalnızca $n \ge n_0$'a bakar.
- "$\le$" ile verilen bir recurrence yalnızca O verir, Θ vermez.
"(a) (5 points) Suppose that $f(n) = O(n)$ and $g(n) = O(n\log n)$. Prove or disprove: $f(n) + g(n) = O(n\log n)$."
İpucu 1
Önce $f$ için de $n \log n$ cinsinden bir upper bound yaz: $n \le n\log n$ hangi $n$'den itibaren doğru?
İpucu 2
$n \ge 2$ iken $\log n \ge 1$. Sonra sum rule'daki gibi constant'ları topla, $n_0$ olarak en büyüğünü al.
Çözümü göster
Prove (ifade doğru).
- $f(n) = O(n)$: bir $c_1, n_1$ vardır, her $n \ge n_1$ için $0 \le f(n) \le c_1 n$.
- $g(n) = O(n\log n)$: bir $c_2, n_2$ vardır, her $n \ge n_2$ için $0 \le g(n) \le c_2\, n\log n$.
- $n \ge 2$ iken $\log n \ge 1$, yani $n \le n\log n$. O zaman $f(n) \le c_1 n \le c_1\, n\log n$.
- $n_0 = \max(n_1, n_2, 2)$ al. Her $n \ge n_0$ için $$0 \le f(n) + g(n) \le c_1\, n\log n + c_2\, n\log n = (c_1 + c_2)\, n\log n .$$
$c = c_1 + c_2$ ve $n_0 = \max(n_1, n_2, 2)$ ile definition sağlanıyor: $f(n) + g(n) = O(n\log n)$. ∎
Puan kaybettiren yer genelde 3. adım: $n = 1$'de $n\log n = 0$ olduğu için $n_0$'a 2'yi eklemeyi unutmak.
Function'ları growth rate'e göre sıralamak
Function'ları growth rate'e göre sıralama sorusunda (HW1 tablosu, concept check) önce her function'ı tanıdık bir biçime çevir.
| Identity | Örnek |
|---|---|
| $\log(n^k) = k\log n$ | $\log(n^{10}) = 10\log n = \Theta(\log n)$ |
| $2^{\log n} = n$ | $2^{3\log n} = n^3$ |
| $2^{(\log n)/2} = \sqrt n$ | Exponent'teki ½ square root demek |
| $a^{\log b} = b^{\log a}$ | $3^{\log n} = n^{\log 3} \approx n^{1.58}$ |
| $n^{1/\log n} = 2$ | Çünkü $n = 2^{\log n}$. Sonuç bir constant: $\Theta(1)$ |
| $\log(n!) = \Theta(n \log n)$ | $n! \le n^n$ ve $n! \ge (n/2)^{n/2}$ |
| $\log_a n = \dfrac{\log_b n}{\log_b a}$ | Base değiştirmek yalnızca constant factor getirir, Θ değişmez |
- Log'un her kuvveti her polynomial function'dan yavaş büyür: $(\log n)^{100} \prec n^{0.01}$.
- Her polynomial her exponential function'dan yavaş büyür: $n^{100} \prec 1.01^n$.
- Exponential function'larda base önemlidir: $2^n \prec 3^n$; $(7/8)^n \to 0$.
- Emin değilsen iki function'ın log'unu karşılaştır ya da $\lim f/g$'ye bak.
Doğru sıra hangisi? $\ \log(n^5),\ (\log n)^2,\ 2^{\log n},\ n^{\log 3}$
Loop sayma kalıpları
"Find the Big-Oh time complexity of the following code fragment" sorusu her yıl çıkıyor. Bir örnek seç ve oynat. Counter operation sayısını, grid de hangi $(i, j)$ çiftlerinin çalıştığını gösteriyor.
| Kalıp | Iteration | Θ |
|---|---|---|
for i = 1..10 | 10 | $\Theta(1)$ × body |
for i = 1..n / i += 2 | $n$ / $n/2$ | $\Theta(n)$ |
i *= 2 ya da i /= 2 | $\approx \log n$ | $\Theta(\log n)$ |
i*i <= n | $\sqrt n$ | $\Theta(\sqrt n)$ |
for j = a..b | $b - a + 1$ | Başlangıca bak! j = n..n+5 6 iteration yapar, $n$ değil |
| ardışık loop'lar | topla | $\Theta(\max)$ |
| nested, bağımsız | çarp | $n \cdot m$ |
| inner loop'un bound'u outer loop değişkenine bağlı | $\Sigma$ kur | formülle closed form'a getir |
Sınav şablonu: (1) içten dışa her loop'un iteration sayısı, (2) $\Sigma$ ile toplam, (3) formülle closed form, (4) dominant term ve Θ. "Show your work" puanı adımlara veriliyor.
"(c) (10 points) Find the big-Oh time complexity of the following code fragment:"
int sum = 0;
for (int i = 1; i <= 10; i++) {
for (int j = n; j <= n + i + 2; j++) {
sum++;
sum++;
}
}
for (int i = 0; i < n; i += 2) {
sum++;
}İpucu 1
İlk bloktaki inner loop'un başlangıcına bak: $j$, $n$'den başlıyor. $b - a + 1$ ile iteration sayısını yaz. Sonuç $n$'e bağlı mı?
İpucu 2
İkinci loop'ta $i = 0, 2, 4, \dots$ ve $i < n$. Bu aralıkta kaç çift sayı var?
Çözümü göster
- Inner loop: $j = n, \dots, n+i+2$, yani $(n+i+2) - n + 1 = i + 3$ iteration. Her iteration'da 2 tane
sum++. - İlk blok: $\displaystyle\sum_{i=1}^{10} 2(i+3) = 2\Big(\sum_{i=1}^{10} i + 30\Big) = 2(55 + 30) = 170$. Bu sayı $n$'e bağlı değil: $\Theta(1)$.
- İkinci loop: $i = 0, 2, 4, \dots$ ve $i < n$, yani $\lceil n/2 \rceil$ iteration, her birinde 1
sum++. - Toplam: ardışık blokları topla: $170 + \lceil n/2 \rceil$ tane
sum++. Dominant term $n/2$.
Cevap: $O(n)$. Bu bound tight, yani running time $\Theta(n)$. Kontrol: $n = 10$ için sum'ın son değeri $170 + 5 = 175$.
Tuzak: inner loop'u "$n$ kez döner" sanmak. Yine $O(n)$'e varırsın ama gerekçe yanlış olur. Puan $i + 3$ sayımına veriliyor. Yukarıdaki stepper'da "Constant outer loop + kayan başlangıç" örneği bu sorunun küçültülmüş hâli.
Function kendini çağırıyorsa loop saymak yetmez. $T(n) = (\text{kendi işi}) + T(\text{subproblem})$ biçiminde bir recurrence kur, sonra çöz. Bu bir sonraki konu.
Bu kodun Θ'sı ne? for i = 1..n: for j = i..n: for k = 1..10: x++
Sınavda nasıl soruluyor
- 2023-24 S3(a): $f = O(n)$, $g = O(n\log n)$ ⇒ $f+g = O(n\log n)$? Definition ile proof (Bölüm 7).
- 2023-24 S3(c): 10 kez dönen bir outer loop, içinde
j = n'denn + i + 2'ye giden bir loop ve ikisum++; ardındani += 2ile ilerleyen ikinci bir loop. Iteration sayısı $b-a+1$, constant bound, ardışık loop'lar. - 2019-20 S1: O / Θ / o ilişkilerini sağlayan function çiftleri bul.
- 2019-20 quiz S2: "$\max\{f,g\} = \Theta(f+g)$", "$f(n)+b = O(f(n))$" doğru mu, gerekçesiyle.
- Pratik vize S3: $f(2n) = \Theta(f(n))$ her $f$ için doğru mu? Counterexample: $f = 2^n$.
- HW1 S3–4: O/Ω/Θ tablosu ($\log(n!)$ vs $\log(n^n)$, $n^{1/\log n}$, $8^n$ vs $4^n$) ve iki definition proof'u.
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
$n^3 \ne O(n^2)$ proof'unda contradiction hangi adımda çıkar?
for (i = 1; i*i <= n; i++) x++; kaç iteration yapar?
$\log(n!)$ ile $n\log n$ arasındaki ilişki ne?
"$f = O(g)$ ise $g = O(f)$." Doğru mu?