T(n)=3T(n/2)+n的递推式求解 |
您所在的位置:网站首页 › 算法函数的渐进表达式求解 › T(n)=3T(n/2)+n的递推式求解 |
3T(n/2)+n 的递推式
主要定理公式求解
根据递推式 T(n)=3T(n/2)+n ;可知 a=3,b=2,f(n)=n;计算出来的结果是:
log
2
3
>
1
\log_2{3}>1
log23>1则有
n
l
o
g
2
3
+
c
>
f
(
n
)
n^{log_2{3}+c}>f(n)
nlog23+c>f(n),当c=0时。所以符合主定理公式的条件一, 所以,
T
(
n
)
=
n
log
2
3
=
O
(
n
l
o
g
3
)
T(n)=n^{\log_23}=O(n^{log3})
T(n)=nlog23=O(nlog3) 最后,附上主定里公式:
最后的结果是:线性对数阶 T ( n ) = n l o g 3 T(n)=n^{log3} T(n)=nlog3 结束 :如果小伙伴们有不同的意见,欢迎讨论 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |