102年關務 資料結構 - 考試

※ 引述《asdd (我愛胖穎穎)》之銘言：
: 下列哪兩個敘述是錯的
: (A)0.5n^2+100n=O(n^2) (B)1000=O(1) (C)0.5n+5logn=O(n^2)
: (D)2n^2+5^n=O(2^n) (E)n^7+1.5^n=O(n^7) (F)3n^2+nlog^4 n=O(nlog^4 n)
: 請問這題大家怎麼選?我個人覺得(D) (E) (F)都錯 可是題目只要兩個.....
:
(D)感謝各位大大指正，此題不能用羅比達
2^n 2 n
lim _______ = lim ( ___ ) = 0
n→∞ 5^n n→∞ 5

所以2^n = o(5^n)，可推得2^n = O(5^n)

5^n 5 n
lim ____ = lim ( ___ ) = ∞
n→∞ 2^n n→∞ 2

所以5^n = ω(2^n)，可推得5^n = Ω(2^n)，(D)是錯的

(E)感謝各位大大指正
n^7 7* n^6
lim _____ = lim ______________ = ... =
n→∞ 1.5^n n→∞ 1.5^n * ln1.5

7*6*5*4*3*2*1 n^0
________________ lim _______ = 0
ln^7 1.5 n→∞ 1.5^n

所以n^7 = o(1.5^n)，可推得n^7 = O(1.5^n)，(E)是錯的

(F)
nlog^4 n log^4 n 4*(1/n) log^3 n
lim __________ = lim ________ = lim _______________ = ... =
n→∞ 3* n^2 n→∞ 3* n^1 n→∞ 3* n^0

4*3*2*1* log^0 n
lim __________________ = 0
n→∞ 3* n^1

所以nlog^4 n = o(3* n^2),可推得nlog^4 n = O(3* n^2)，(F)是錯的

--