Re: [理工] [演算法] 找數學式子規則並比大小
※ 引述《mqazz1 (無法顯示)》之銘言：
: 演算法名校攻略秘笈 第四版 1-21頁
: For each pair of two functions,
: given below,
: if f(n) = Ｏ(g(n)),
: f(n) = Ω(g(n)),
: f(n) = Θ(g(n)),
: or neither
: (Note: ln n = log(e)(n). )
: ============================================
: (5) f(n) = log(n^(0.01n)) g(n) = log(n!)
log(n!) = Θ(nlogn)
log(n^(0.01n)) = 0.01 * n * log n = Θ(nlogn)
f(n) = Θ(g(n))
: (6) f(n) = n + n/2 + n/4 + ... + 1 g(n) = n + 2n/2 + 3n/4 + ... + (ln n)
From 2g(n) - g(n), we can get that g(n) = 3n + n/2 + n/4 + ...
so g(n) > f(n) f(n) = Ｏ(g(n))
But I'm not sure about this question.
: (7) f(n) = 1 + 1/2 + ... + 1/(2^n) g(n) = n
f(n) = 2 - (1/2)^n
limit f(n)/g(n) = 0 --> f(n) = Ｏ(g(n))
n->infinite
: 請問這三題應該怎麼下手呢?
: 謝謝!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.152.25