推 Purlas:我懂了!謝謝解答 03/17 00:34
※ 引述《Purlas (皮拉斯)》之銘言：
: 1.
: n^2-2n=Ω(n^2）
: 這題我認為找不到C0跟n使之0成立，對嗎?
: 2.log^2(n)=小o(n^1/3)
: 這一題我也找不到C0跟n0使之成立，對嗎?
: 如何證明?
: 還是其實有? 感謝解答!
用limit法證
1.
2
f(n) = n - 2n
2
g(n) = n
f(n)
lim ─── = 1
n→∞ g(n)
故 f(n) = Θ(g(n))
所以 f(n) = Ω(g(n))
2.
2
f(n) = log n
(1/3)
g(n) = n
( L'Hospital's Rule )
f(n) f'(n) 2(logn)‧(1 / ln2)‧(1/n)
lim ─── = lim ──── = lim ───────────── (底數用2)
n→∞ g(n) n→∞ g'(n) n→∞ (-2/3)
(1/3) ‧ n
[ 6(logn) ]' 6
= lim ─────────── = lim ─────────── = 0
n→∞ (1/3) n→∞ 2 (4/3)
[ (ln2)‧ n ]' (ln2) ‧ n
故 f(n) = o (g(n))
有錯麻煩更正 感謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.40.207.32