作者a9999xyz (KLOSE)
看板TransCSI
標題Re: [問題] 關於多人多工
時間Mon Jul 7 10:39:21 2008
: 希望各位幫我解答: : 還有一題政大資管96關於Big O的
: T(1)=7, T(n+1)=3n+T(n),for all n>=1
: T(n+1)=3n + T(n)
: =3n + 3(n-1) + T(n-1)
: =3n + 3(n-1) + 3(n-2) + T(n-2)
: :
: :
: :
: =3n + 3(n-1) + 3(n-2) + 3(n-3) + 3(n-4) + ... + 3(n-(n-1)) + T(1)
: =3( n(n+1)/2 ) + 7
能不能解釋一下是怎麼從上面的式子判斷他為O(n^2)的呢?
感謝!
Y
: 所以是 O(n^2)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.170.108.190
1F：推 s90366770607:把n(n+1)/2展開就會出現n^2 07/07 11:55
2F：→ a9999xyz:同張考卷上有另一題是Σ(i=1~n)K的i次方 07/07 19:18
3F：→ a9999xyz:請問這個要怎麼看? 07/07 19:18
4F：推 avogau:O( K^n ) 07/08 00:09
5F：→ avogau:簡單的說看最高次那一項為何 07/08 00:10
6F：→ avogau:如果有演算法或資料結構的書 通常最前面那章會講解 07/08 00:11
7F：→ a9999xyz:嗯!感謝樓上專業講解~我了解了~感謝 07/08 00:39
8F：推 tobedesigner:大師定理，可以出招嗎？？？ 07/24 23:20
9F：推 avogau:這一題不能用 Master Method 吧 08/29 21:05