Re: [理工] [DS]99中山 時間複雜度

[ybite (小犬)]

※ 引述《sroeud7l (Teddy Bear)》之銘言：
: 做到有關Time Complexity才發現概念不太清楚 看講義也不太瞭
: 網址如下http://www.lib.nsysu.edu.tw/exam/master/eng/elec/elec_99.pdf
: 資結在第11~13頁
: 2.求Ω(omega),不是只要在從中選最大者就好嗎
:   為何題目要求order n^4+8n?
他要求你用Asymptotic notation的定義去證明
他整個定義都給你了，你只要用那個定義證出來就可以啦
let f(n) = 40n^3+10nlogn+6, g(n) = n^4+8n
f(n) <= cg(n) → 40n^3+10nlogn+6 <= c(n^4+8n)

let c = 40, n0 = 1則原題中的定義應該就吻合了
（這個證明需要一點功夫，我一時之間講不出來qqqqq）
所以f(n) = O(g(n)) 對，原題是說Big O而非Big Omega Orz

: 8.use R1 => n^3+n^2log3n之後就不會了
這題怪怪的。需要高人求解qqqqq
我卡住的點是在R5上面。R5這樣設這個東西還有可能會是k(n^3)嗎？
照規則求出來頂多是K(a^n+a^n*n^3吧）？

: 10.結果array內容是
:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
: A: 2  4 28 26 24 22 20 18 16 14 12 10  8  6 30 32
:    這樣嗎?
應該沒錯！

: 11.是化成T(N)=T(n-2)+1去求嗎?
: 請大大多多指點了
應該是這樣吧？證明我想也許用歸納法去證會對？
答案應該十之八九是O(n)。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.127.178.2
推 sroeud7l:謝定正 是big-Oh 我搞錯-.-
→ sroeud7l:所以2.的證明 依大大的值c=40 ,n0=1
→ sroeud7l:再代入=> 40n^3+10nlogn+6<=40n^4+8n 解開方程式就得證了
推 sroeud7l:吧?
→ sroeud7l:若我重新取c=10 n0=4 => 40n^3+10nlogn+6<=10(n^4+8n)
→ sroeud7l:=> 40n^4-40n^3+80n-10nlogn-6>=0
→ sroeud7l:=> 10n(n^3-4n^2+8n-logn)-6>=0 , n>=4 n0=4(2,3也可)
→ sroeud7l:這樣可以嗎 感覺沒證的很完整
→ sroeud7l:再問11. T(n)是到T(1)=0結束嗎 還是?   感謝以上的回復:D