T(n)=3T(n/2)+n的递推式求解
3T(n/2)+n 的递推式主要定理公式求解根据递推式 T(n)=3T(n/2)+n ;可知 a=3,b=2,f(n)=n;计算出来的结果是：log23>1\log_2{3}>1log23>1则有nlog23+c>f(n)n^{log_2{3}+c}>f(n)nlog23+c>f(n),当c=0时。所以符合主定理公式的条件一，所以，T(n)=nlo...
3T(n/2)+n 的递推式
主要定理公式求解
根据递推式 T(n)=3T(n/2)+n ;可知 a=3,b=2,f(n)=n;计算出来的结果是：
log23>1\log_2{3}>1log23>1则有nlog23+c>f(n)n^{log_2{3}+c}>f(n)nlog23+c>f(n),当c=0时。所以符合主定理公式的条件一，
所以，T(n)=nlog23=O(nlog3)T(n)=n^{\log_23}=O(n^{log3})T(n)=nlog23=O(nlog3)
最后，附上主定里公式：
递归式求解
求总和为 T(n)=∑k=0k=log2n−1(32)k×n+3log2nΦ(1)T(n)=\sum_{k=0}^{k=log_2n-1}({\frac{3}{2}})^k\times n+3^{log_2n}\Phi(1)T(n)=k=0∑k=log2n−1(23)k×n+3log2nΦ(1) T(n)=2×3log2n−n+3log2nΦ(1)=2×3log2nT(n)=2\times3^{\log_2n}-n+3^{log_2n}\Phi(1)=2\times3^{log_2n}T(n)=2×3log2n−n+3log2nΦ(1)=2×3log2n
因为3log2n=(2log23)log2n=(2log2n)log23=nlog233^{log_2n}=(2^{log_23})^{log_2n}=(2^{log_2n})^{log_23}=n^{log_23}3log2n=(2log23)log2n=(2log2n)log23=nlog23所以T(n)=nlog3T(n)=n^{log3}T(n)=nlog3
最后的结果是：线性对数阶
T(n)=nlog3T(n)=n^{log3}T(n)=nlog3
结束 ：如果小伙伴们有不同的意见，欢迎讨论
226156564@qq.com
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
14
0- 0
已为社区贡献3条内容
所有评论(0)