資料結構›Ch1 演算法基礎
第 3 題/共 57 題
◀ DS 3/57
3. 漸進符號、複雜度分析
#DS-01-003難漸進符號複雜度分析

For positive functions f(n)f(n) and g(n)g(n) on N\mathbb{N}. If f(n)=O(g(n))f(n) = O(g(n)) and f(n)=Ω(1)f(n) = \Omega(1), how many of the following statements are true?

  • g(n)=Ω(f(n))g(n) = \Omega(f(n))
  • f(n)⋅log⁡(1+f(n))=O(g(n)⋅log⁡(1+g(n)))f(n) \cdot \log(1+f(n)) = O(g(n) \cdot \log(1+g(n)))
  • 2f(n)=O(2g(n))2^{f(n)} = O(2^{g(n)})
  • (f(n))k=O((g(n))k)(f(n))^k = O((g(n))^k) for any 0<k<10 < k < 1
📄 台大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎
本章題號 · 1–20 / 57