算法導論 — 思考題3-4 漸近記号的性質

（漸近記号的性質）假設 f ( n ) f(n) f(n)和 g ( n ) g(n) g(n)為漸近正函數。證明或反駁下面的每個猜測。

　　a. f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f(n)=O(g(n))蘊含 g ( n ) = O ( f ( n ) ) g(n) = O(f(n)) g(n)=O(f(n))。

　　b. f ( n ) + g ( n ) = Θ ( m i n ( f ( n ) , g ( n ) ) ) f(n) + g(n) = Θ({\rm min}(f(n), g(n))) f(n)+g(n)=Θ(min(f(n),g(n)))。

　　c. f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f(n)=O(g(n))蘊含 l g ( f ( n ) ) = O ( l g ( g ( n ) ) ) {\rm lg}(f(n)) = O({\rm lg}(g(n))) lg(f(n))=O(lg(g(n)))，其中對所有足夠大的 n n n，有 l g ( g ( n ) ) ≥ 1 {\rm lg}(g(n)) ≥ 1 lg(g(n))≥1且 f ( n ) ≥ 1 f(n) ≥ 1 f(n)≥1。

　　d. f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f(n)=O(g(n))蘊含 2 f ( n ) = O ( 2 g ( n ) ) 2^{f(n)} = O(2^{g(n)}) 2f(n)=O(2g(n))。

　　e. f ( n ) = O ( ( f ( n ) ) 2 ) f(n) = O((f(n))^2) f(n)=O((f(n))2)。

　　f. f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f(n)=O(g(n))蘊含 g ( n ) = Ω ( f ( n ) ) g(n) = Ω(f(n)) g(n)=Ω(f(n))。

　　g. f ( n ) = Θ ( f ( n / 2 ) ) f(n) = Θ(f(n/2)) f(n)=Θ(f(n/2))。

　　h. f ( n ) + o ( f ( n ) ) = Θ ( f ( n ) ) f(n) + o(f(n)) = Θ(f(n)) f(n)+o(f(n))=Θ(f(n))。

　　

　　解

　　a. 錯誤

　　例如， n = O ( n 2 ) n = O(n^2) n=O(n2)，然而 n 2 ≠ O ( n ) n^2 ≠ O(n) n2̸​=O(n)。

　　

　　b. 錯誤

　　例如， n + n 2 ≠ Θ ( n ) n + n^2 ≠ Θ(n) n+n2̸​=Θ(n)。

　　

　　c. 正确

　　 f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f(n)=O(g(n))，意味着存在正常量 c c c和 n 0 n_0 n0​，使得對所有 n ≥ n 0 n ≥ n_0 n≥n0​，有 f ( n ) ≤ c g ( n ) f(n) ≤ cg(n) f(n)≤cg(n)。對這個不等式兩邊取對數，得到 l g ( f ( n ) ) ≤ l g c + l g ( g ( n ) ) {\rm lg}(f(n)) ≤ {\rm lg}c + {\rm lg}(g(n)) lg(f(n))≤lgc+lg(g(n))。由于 l g c {\rm lg}c lgc是常數，可以取足夠大的正常量 c ′ c' c′，使得對所有 n ≥ n 0 n ≥ n_0 n≥n0​，有 l g c + l g ( g ( n ) ) ≤ c ′ l g ( g ( n ) ) {\rm lg}c + {\rm lg}(g(n)) ≤ c'{\rm lg}(g(n)) lgc+lg(g(n))≤c′lg(g(n))，即 l g ( f ( n ) ) ≤ c ′ l g ( g ( n ) ) {\rm lg}(f(n)) ≤ c'{\rm lg}(g(n)) lg(f(n))≤c′lg(g(n))。是以 l g ( f ( n ) ) = O ( l g ( g ( n ) ) ) {\rm lg}(f(n)) = O({\rm lg}(g(n))) lg(f(n))=O(lg(g(n)))成立。

　　

　　d. 錯誤

　　例如， n = O ( n / 2 ) n = O(n/2) n=O(n/2)，然而， 2 n ≠ O ( 2 n / 2 ) 2^n ≠ O(2^{n/2}) 2n̸​=O(2n/2)。

　　

　　e. 錯誤

　　我們可以構造一個函數，該函數是漸近小于 1 1 1的，例如， f ( n ) = 1 / n f(n)=1/n f(n)=1/n， ( f ( n ) ) 2 = 1 / n 2 (f(n))^2=1/n^2 (f(n))2=1/n2。顯然有

　　　　 l i m n → ∞ ⁡ ( f ( n ) ) 2 f ( n ) = l i m n → ∞ f ( n ) = l i m n → ∞ 1 n = 0 lim_{n→∞}⁡\frac{(f(n))^2}{f(n)}=lim_{n→∞}f(n)=lim_{n→∞}\frac{1}{n}=0 limn→∞​⁡f(n)(f(n))2​=limn→∞​f(n)=limn→∞​n1​=0

　　這說明 ( f ( n ) ) 2 = o ( f ( n ) ) (f(n))^2=o(f(n)) (f(n))2=o(f(n))，是以 f ( n ) ≠ O ( ( f ( n ) ) 2 ) f(n)≠O((f(n))^2) f(n)̸​=O((f(n))2)。

　　

　　f. 正确

　　3.1節已給出了這一結論。

　　

　　g. 錯誤

　　例如， 2 n ≠ Θ ( 2 n / 2 ) 2^n ≠ Θ(2^{n/2}) 2n̸​=Θ(2n/2)。

　　

　　h. 正确

　　對任意一個函數 g ( n ) = o ( f ( n ) ) g(n) = o(f(n)) g(n)=o(f(n))，當 n n n足夠大時，必有 0 ≤ g ( n ) &lt; f ( n ) 0 ≤ g(n) &lt; f(n) 0≤g(n)<f(n)。于是當 n n n足夠大時，有 f ( n ) ≤ f ( n ) + g ( n ) &lt; 2 f ( n ) f(n) ≤ f(n) + g(n) &lt; 2f(n) f(n)≤f(n)+g(n)<2f(n)，這說明 f ( n ) + g ( n ) = Θ ( f ( n ) ) f(n) + g(n) = Θ(f(n)) f(n)+g(n)=Θ(f(n))，即 f ( n ) + o ( f ( n ) ) = Θ ( f ( n ) ) f(n) + o(f(n)) = Θ(f(n)) f(n)+o(f(n))=Θ(f(n))。