作者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