資料結構›Ch1 演算法基礎第 3 題/共 57 題
3. 漸進符號、複雜度分析
#DS-01-003難漸進符號複雜度分析
For positive functions and on . If and , how many of the following statements are true?
- for any
參考答案與解析
答案 (D) 3。逐句檢查:①g(n)=Ω(f(n)) 與 f(n)=O(g(n)) 本來就是同一件事的兩種寫法,true。②x·log(1+x) 是遞增函數,f(n)≤c·g(n) 代入後 f·log(1+f) ≤ c·g·log(1+c·g),log 裡的常數倍不影響量級,仍是 O(g·log(1+g)),true。③2^{f(n)}=O(2^{g(n)}) 一般不成立:反例 f(n)=2n=O(n)=O(g(n))(g(n)=n),但 2^{2n}=4^n 不是 O(2^n),false。④(f(n))^k=O((g(n))^k)(0<k<1):因為 x^k 是遞增函數且 (c·g)^k=c^k·g^k,常數被吸收,true。共 3 句為真。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎