算法導論學習筆記[1] #20210709

• lec 2
• • 漸近記号
  • Solving recurrences
  • Master method

lec 2

Lecture 2

Asymptotic Notation; Recurrences; Substitution, Master Method

之後若無說明，則對數都以2為底。

漸近記号

Q0: O O O記号和 Θ \Theta Θ記号有何異同？

A0: 同：都考察某個常數 n 0 n_0 n0​之後的行為。都有上界。

異： f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))中 f ( n ) f(n) f(n)下界是0而不是 c 1 g ( n ) ( c 1 > 0 ) c_1g(n)(c_1>0) c1​g(n)(c1​>0)，是以 f , g f,g f,g可能不同階（具體地， 2 n 2 = O ( n 3 ) 2n^2=O(n^3) 2n2=O(n3)但是 n 3 = O ( 2 n 2 ) n^3=O(2n^2) n3=O(2n2)不成立。這說明這樣的“等号”一定程度上有些奇怪（bizarre））

注：更好的了解方式是認為 O ( g ( n ) ) O(g(n)) O(g(n))是一個函數集合，并記 f ( n ) ∈ O ( g ( n ) ) f(n)\in O(g(n)) f(n)∈O(g(n)). “等号”不對稱，确實不太好。

Q1: 解釋 f ( n ) = n 3 + O ( n 2 ) = O ( n 3 ) = O ( n 4 ) f(n)=n^3+O(n^2)= O(n^3)=O(n^4) f(n)=n3+O(n2)=O(n3)=O(n4).

A1:

第一個等号相當于更加精确地描述 f ( n ) f(n) f(n)的漸近行為，即減去 n 3 n^3 n3後剩餘的誤差項至多不超過 n 2 n^2 n2量級。

第二個等号：對于任意 h ( n ) = O ( n 2 ) h(n)=O(n^2) h(n)=O(n2)，有 n 3 + h ( n ) = O ( n 3 ) n^3+h(n)=O(n^3) n3+h(n)=O(n3). 這個等号其實相當于集合的包含于，它不對稱。

注：認為 O ( n 2 ) O(n^2) O(n2)是一個集合更加友善。實際上，A set in a formula (left hand side) represents an anonymous function in the set. 即看到 O ( n 2 ) O(n^2) O(n2)就設想把它換成具體的一個 h ( n ) h(n) h(n)滿足 h ( n ) = O ( n 2 ) h(n)=O(n^2) h(n)=O(n2). 課堂中将此與宏的替換類比。

第三個等号也是集合的包含于。注意包含于關系可以往一個方向傳遞，但不能反向。

Q2: O O O, Ω \Omega Ω, Θ \Theta Θ有何聯系？

A2: O ( g ( n ) ) ∩ Ω ( g ( n ) ) = Θ ( g ( n ) ) O(g(n))\cap \Omega(g(n))=\Theta(g(n)) O(g(n))∩Ω(g(n))=Θ(g(n))（都看成集合）

Q3: Θ \Theta Θ和 O O O對應的集合有交集，這不令人滿意。闡述“嚴格”不等對應的 o ( g ( n ) ) o(g(n)) o(g(n))和 ω ( g ( n ) ) \omega(g(n)) ω(g(n)).

A3: o ( g ( n ) ) = { f ( n ) ∣ ∀ c > 0 , ∃ N > 0 , ∀ n > N , f ( n ) < c g ( n ) } o(g(n))=\{f(n)|\forall c>0,\exists N>0,\forall n>N,f(n)<cg(n)\} o(g(n))={f(n)∣∀c>0,∃N>0,∀n>N,f(n)<cg(n)}. ω \omega ω類似（反向）。

注意是任意 c c c而不是存在 c c c，否則其實不能展現漸近意義上的“嚴格不等”。

顯然 Θ , o , ω \Theta,o,\omega Θ,o,ω對應的集合沒有交集。（但它們的并顯然不是全集）

注： O , ω O,\omega O,ω對應的集合之并也不是全集。（思考：為什麼？）

Solving recurrences

Q0: T ( n ) = 4 T ( n / 2 ) + n , T ( 1 ) = Θ ( 1 ) T(n)=4T(n/2)+n,T(1)=\Theta(1) T(n)=4T(n/2)+n,T(1)=Θ(1)中，根據 4 ( c n 3 / 8 ) + n < c n 3 4 (cn^3/8)+n<cn^3 4(cn3/8)+n<cn3（ n n n大）可以說明（）。

注意這裡省略了歸納的起點，并忽略了取整等問題。

為什麼同樣是歸納， 1 = O ( 1 ) , 2 = 1 + 1 = O ( 1 ) + 1 = O ( 1 ) , 3 = 2 + 1 = O ( 1 ) + 1 ⋯   , n = O ( 1 ) + 1 = O ( 1 ) 1=O(1),2=1+1=O(1)+1=O(1),3=2+1=O(1)+1\cdots,n=O(1)+1=O(1) 1=O(1),2=1+1=O(1)+1=O(1),3=2+1=O(1)+1⋯,n=O(1)+1=O(1)就顯得很奇怪？

A0: T ( n ) = O ( n 3 ) T(n)=O(n^3) T(n)=O(n3)

提示：在第二個例子中不存在一個對所有 n n n都一緻的常數。故準确來說，對于某一确定的 n 0 n_0 n0​有 n 0 = O ( 1 ) n_0=O(1) n0​=O(1)沒錯，但對于函數 f ( n ) = n f(n)=n f(n)=n就不能說 n = O ( 1 ) n=O(1) n=O(1).

Q1: 利用遞歸樹法猜測 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T(n)=4T(n/2)+n中 T T T的漸近行為，并做出證明（提示： c 1 n 2 + c 2 n c_1n^2+c_2n c1​n2+c2​n）

A1:

以此類推，得到 n + n / 2 ⋅ 4 + n / 4 ⋅ 16 + ⋯ = n + 2 n + 4 n + ⋯ ≈ 2 l o g n n = n 2 n+n/2\cdot 4+n/4\cdot 16+\cdots=n+2n+4n+\cdots\approx 2^{logn}n=n^2 n+n/2⋅4+n/4⋅16+⋯=n+2n+4n+⋯≈2lognn=n2. 注意樹有 l o g n logn logn層。

猜測 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2). 由于 T ( n ) ≤ c n 2 T(n)\le cn^2 T(n)≤cn2并不好歸納，故不妨采取 T ( n ) ≤ c 1 n 2 + c 2 n T(n)\le c_1n^2+c_2n T(n)≤c1​n2+c2​n歸納。實際上 c 2 c_2 c2​是負的。

注：估計 Ω ( n 2 ) \Omega(n^2) Ω(n2)比較簡單，直接 T ( n ) ≥ c n 2 T(n)\ge cn^2 T(n)≥cn2即可。

Q2: 接上，記 T ( 2 m ) = a m T(2^m)=a_m T(2m)=am​，你有什麼想法？（回憶數列題的做法）

A2: a m = 4 a m − 1 + 2 m , a m + 2 m = 4 ( a m − 1 + 2 m / 2 ) = 4 ( a m − 1 + 2 m − 1 ) a_m=4a_{m-1}+2^m,a_m+2^m=4(a_{m-1}+2^m/2)=4(a_{m-1}+2^{m-1}) am​=4am−1​+2m,am​+2m=4(am−1​+2m/2)=4(am−1​+2m−1)，則 b m : = a m + 2 m = O ( 4 m ) b_m:=a_m+2^m=O(4^m) bm​:=am​+2m=O(4m). 這裡配上 2 m 2^m 2m構造等比數列就是數列題的典型做法。

Q3: 對于 T ( n ) = T ( n / 4 ) + T ( n / 2 ) + n 2 T(n)=T(n/4)+T(n/2)+n^2 T(n)=T(n/4)+T(n/2)+n2用遞歸樹法猜測漸近行為。并用數學歸納法證明。

A3: T ( n ) = n 2 + T ( n / 2 ) + T ( n / 4 ) = n 2 + n 2 / 2 2 + n 2 / 4 2 + T ( n / 4 ) + T ( n / 8 ) + T ( n / 8 ) + T ( n / 16 ) = ⋯ = n 2 + a n 2 + a 2 n 2 + ⋯ = O ( n 2 ) T(n)=n^2+T(n/2)+T(n/4)=n^2+n^2/2^2+n^2/4^2+T(n/4)+T(n/8)+T(n/8)+T(n/16)=\cdots=n^2+an^2+a^2n^2+\cdots=O(n^2) T(n)=n2+T(n/2)+T(n/4)=n2+n2/22+n2/42+T(n/4)+T(n/8)+T(n/8)+T(n/16)=⋯=n2+an2+a2n2+⋯=O(n2). （容易證明出現幾何級數）

樹此處就不畫了。注意遞歸樹和不斷用省略号寫是一個意思。

為了嚴格證明（歸納），直接設 T ( n ) < c n 2 T(n)<cn^2 T(n)<cn2即可。

另一方面 Ω ( n 2 ) \Omega(n^2) Ω(n2)顯然（ T ( n ) ≥ n 2 T(n)\ge n^2 T(n)≥n2）。

Master method

Q0: 對于主方法， T ( n ) + a T ( n / b ) + f ( n ) T(n)+aT(n/b)+f(n) T(n)+aT(n/b)+f(n)中的 a , b , f a,b,f a,b,f有何要求？為什麼？

A0: a ≥ 1 , b > 1 , f a\ge 1,b>1,f a≥1,b>1,f漸近地恒為正（即在 n n n足夠大時 f ( n ) f(n) f(n)為正）

f ( n ) f(n) f(n)漸近地恒為正其實從數學的本質上講不一定是必要的，隻是為了友善做出的假設。當然，對于非恒正的函數我們需要擴充漸近記号的定義。并且 f f f不恒為正時就難以得出 Θ \Theta Θ而隻可能得到 O O O. 實際算法中， f f f常常指建立“子問題”，合并“子結果”的開銷，一般來說是正的。

容易發現 f f f恒正遞增時，對 0 < a < 1 0<a<1 0<a<1時隻有兩種情況：即 f ( n ) f(n) f(n)有界時 T ( n ) = O ( 1 ) T(n)=O(1) T(n)=O(1)， f ( n ) f(n) f(n)無界時 T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n)). 這種情況相對來說比較平凡。且實際算法中 a < 1 a<1 a<1難以有實際意義。

一旦 a ≥ 1 a\ge 1 a≥1，設 f ( n ) f(n) f(n)有正的下界，那麼如果 b ≤ 1 b\le 1 b≤1，則 T ( n ) T(n) T(n)顯然發散。在實際中，這也無法導出任何有意義的遞歸算法。

Q1: 主方法Case 1: f ( n ) = O ( n l o g b a − ϵ ) f(n)=O(n^{log_b a-\epsilon}) f(n)=O(nlogb​a−ϵ)，則 T ( n ) = Θ ( n l o g b a ) T(n)=\Theta(n^{log_b a}) T(n)=Θ(nlogb​a). 請舉例說明 f ( n ) = o ( n l o g b a ) f(n)=o(n^{log_b a}) f(n)=o(nlogb​a)不一定可行的根源在哪裡。

A1: （特别地找一個例子）考慮 T ( n ) = T ( n / 2 ) + f ( n ) T(n)=T(n/2)+f(n) T(n)=T(n/2)+f(n)則 T ( n ) ≈ ∑ k = 1 l o g 2 n f ( 2 k ) T(n)\approx\sum_{k=1}^{log_2n}f(2^k) T(n)≈∑k=1log2​n​f(2k). 如果 f ( n ) = 1 f(n)=1 f(n)=1則求和發散，如果 f ( n ) = n 0 − ϵ f(n)=n^{0-\epsilon} f(n)=n0−ϵ則求和收斂（實際上這裡得到的是收斂的等比級數）。

總之， T ( n ) = Θ ( n l o g b a ) T(n)=\Theta(n^{log_b a}) T(n)=Θ(nlogb​a)是否成立的關鍵是正項級數的斂散性。這就容易看出其實 T ( n ) = T ( n / 2 ) + f ( n ) , f ( n ) = O ( l n − 1 − ϵ n ) T(n)=T(n/2)+f(n),f(n)=O(ln^{-1-\epsilon}n) T(n)=T(n/2)+f(n),f(n)=O(ln−1−ϵn)也能推出 T ( n ) = O ( 1 ) T(n)=O(1) T(n)=O(1)，但 T ( n ) = T ( n / 2 ) + f ( n ) , f ( n ) = O ( l n − 1 n ) = o ( 1 ) T(n)=T(n/2)+f(n),f(n)=O(ln^{-1} n)=o(1) T(n)=T(n/2)+f(n),f(n)=O(ln−1n)=o(1)顯然就不行。

Q2: 回顧Q1，說出主方法Case 2: f ( n ) = Θ ( n l o g b a l o g k n ) , k ≥ 0 f(n)=\Theta(n^{log_b a}log^k n),k\ge 0 f(n)=Θ(nlogb​alogkn),k≥0在考察 T ( n ) = 2 T ( n / 2 ) + f ( n ) T(n)=2T(n/2)+f(n) T(n)=2T(n/2)+f(n)時，相當于考察什麼正項級數的漸近性質？

A2: ∑ i = 0 l o g n n ( l o g n − i ) k \sum_{i=0}^{logn}n(logn-i)^k ∑i=0logn​n(logn−i)k，在 n n n足夠大時，顯然 i i i較小的一部分（比如說一半）求和就起到了占常數比例的作用。具體地， ∑ i = 0 l o g n n ( l o g n − i ) k > ∑ i = 0 l o g n / 2 n ( l o g n 2 ) k = Θ ( n l o g k + 1 n ) \sum_{i=0}^{logn}n(logn-i)^k>\sum_{i=0}^{logn/2} n(\frac{logn}2)^k=\Theta(nlog^{k+1}n) ∑i=0logn​n(logn−i)k>∑i=0logn/2​n(2logn​)k=Θ(nlogk+1n).

Q3: 主方法Case 3: f ( n ) = Ω ( n l o g b a + ϵ ) , a f ( n / b ) ≤ c f ( n ) , c < 1 f(n)=\Omega (n^{log_b a+\epsilon}),af(n/b)\le cf(n),c<1 f(n)=Ω(nlogb​a+ϵ),af(n/b)≤cf(n),c<1，則 T ( n ) = Θ ( f ( n ) ) T(n)=\Theta(f(n)) T(n)=Θ(f(n)). regularity condition即 a f ( n / b ) ≤ c f ( n ) , c < 1 af(n/b)\le cf(n),c<1 af(n/b)≤cf(n),c<1用在了什麼地方？

A3: 一共有不超過 1 + c + c 2 + ⋯ + c l o g b n 1+c+c^2+\cdots+c^{log_b n} 1+c+c2+⋯+clogb​n個（有限個） f ( n ) f(n) f(n)，則 T ( n ) T(n) T(n)中除去遞歸出口外所有開銷之和與 f ( n ) f(n) f(n)同量級。

注：不嚴格地說，如果畫出遞歸樹，那麼主方法的Case 1, 2, 3分别對應着開銷集中在葉子、開銷平均分攤、開銷集中在根結點。實際意義分别是計算開銷集中在遞歸出口、分散在計算全過程、集中在最大的“歸并”。

注：稍微嚴格地，前一段所說的“集中”其實指的是開銷有一常數比例部分集中在葉子。課程中強調"The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight."

Q4: 接上，遞歸出口那部分的開銷怎麼辦？

A4: T ( n ) = a T ( n / b ) + f ( n ) = a 2 T ( n / b 2 ) + ⋯ = ⋯ T(n)=aT(n/b)+f(n)=a^2T(n/b^2)+\cdots=\cdots T(n)=aT(n/b)+f(n)=a2T(n/b2)+⋯=⋯，最後遞歸出口對應的開銷項應該是 a l o g b n = n l o g b a a^{log_bn}=n^{log_b a} alogb​n=nlogb​a量級。

注：這能看出其實主方法Case 3的條件 f ( n ) = Ω ( n l o g b a + ϵ ) f(n)=\Omega(n^{log_b a+\epsilon}) f(n)=Ω(nlogb​a+ϵ)可以弱化為 f ( n ) = Ω ( n l o g b a ) f(n)=\Omega(n^{log_b a}) f(n)=Ω(nlogb​a).

Q5: regularity condition實際上和 Θ ( n l o g b a + ϵ ) , Θ ( n l o g b a ) \Theta(n^{log_b a+\epsilon}),\Theta(n^{log_b a}) Θ(nlogb​a+ϵ),Θ(nlogb​a)間具有一定的密切聯系。請簡要說明。

A5: 如果 f ( n ) = Θ ( n l o g b a + ϵ ) , ϵ ≥ 0 f(n)=\Theta(n^{log_b a+\epsilon}),\epsilon\ge 0 f(n)=Θ(nlogb​a+ϵ),ϵ≥0，則随着 k k k增大，由 Θ \Theta Θ的定義容易得 f ( n ) a k f ( n / b k ) = Θ ( b k ϵ ) \frac{f(n)}{a^kf(n/b^k)}=\Theta(b^{k\epsilon}) akf(n/bk)f(n)​=Θ(bkϵ).（對于足夠大的一切 n n n，關于 k k k的漸近行為都如此。注意這不是關于 n n n的漸近行為）

再考察regularity condition的一個必要條件是 f ( n ) a k f ( n / b k ) = Ω ( c − k ) \frac{f(n)}{a^kf(n/b^k)}=\Omega(c^{-k}) akf(n/bk)f(n)​=Ω(c−k)，這就知道了 f ( n ) = Θ ( n l o g b a ) f(n)=\Theta(n^{log_b a}) f(n)=Θ(nlogb​a)能推出regularity condition一定不成立。

而 f ( n ) = Θ ( n l o g b a + ϵ ) f(n)=\Theta(n^{log_b a+\epsilon}) f(n)=Θ(nlogb​a+ϵ)的情況，可以考慮 c 1 n l o g b a + ϵ = f m ( n ) ≤ f ( n ) ≤ f M ( n ) = c 2 n l o g b a + ϵ c_1n^{log_b a+\epsilon}=f_m(n)\le f(n)\le f_M(n)=c_2n^{log_b a+\epsilon} c1​nlogb​a+ϵ=fm​(n)≤f(n)≤fM​(n)=c2​nlogb​a+ϵ，并令 T m ( n ) = a T m ( n / b ) + f m ( n ) , T M ( n ) = a T M ( n / b ) + f M ( n ) T_m(n)=aT_m(n/b)+f_m(n),T_M(n)=aT_M(n/b)+f_M(n) Tm​(n)=aTm​(n/b)+fm​(n),TM​(n)=aTM​(n/b)+fM​(n)，根據 f f f和 T T T間某種意義上的“單調”關系，我們隻需考察 T m T_m Tm​和 T M T_M TM​的漸近行為，于是就能得到其實 f ( n ) = Θ ( n l o g b a + ϵ ) f(n)=\Theta(n^{log_b a+\epsilon}) f(n)=Θ(nlogb​a+ϵ)就足以單獨作為主定理Case 3的條件。（注意是 Θ \Theta Θ而不是 Ω \Omega Ω）

注：對比 Θ ( b k ϵ ) , ϵ > 0 \Theta(b^{k\epsilon}),\epsilon>0 Θ(bkϵ),ϵ>0和 Ω ( c − k ) \Omega(c^{-k}) Ω(c−k)，我們可以發現 Θ ( n l o g b a + ϵ ) \Theta(n^{log_ba+\epsilon}) Θ(nlogb​a+ϵ)其實就是大尺度平均意義下的regularity condition.

Q6: 如果 f ( n ) = ω ( n l o g b a + ϵ ) f(n)=\omega(n^{log_b a+\epsilon}) f(n)=ω(nlogb​a+ϵ)那麼 f ( n ) f(n) f(n)可能不滿足regularity condition嗎？

A6: 可能。比如 f f f不單調的情況。反例是平凡的。