Re: [考題] 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)是錯的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.167.195
推
04/02 01:21, , 1F
04/02 01:21, 1F
推
04/02 02:46, , 2F
04/02 02:46, 2F
→
04/02 02:47, , 3F
04/02 02:47, 3F
推
04/02 08:00, , 4F
04/02 08:00, 4F
推
04/02 09:16, , 5F
04/02 09:16, 5F
→
04/02 09:27, , 6F
04/02 09:27, 6F
推
04/02 10:18, , 7F
04/02 10:18, 7F
→
04/02 10:26, , 8F
04/02 10:26, 8F
推
04/02 11:42, , 9F
04/02 11:42, 9F
推
04/02 12:04, , 10F
04/02 12:04, 10F
推
04/02 12:27, , 11F
04/02 12:27, 11F
感謝各位大大指正
※ 編輯: meya 來自: 140.135.40.212 (04/02 15:46)
→
04/03 15:21, , 12F
04/03 15:21, 12F
討論串 (同標題文章)
Examination 近期熱門文章
PTT職涯區 即時熱門文章
51
109