2022 大话--时间复杂度

已知T(n)=2T(n/2)+n;求O(n)?

总结网上的归纳，自己再写一遍：

T(n)=2T(n/2)+n                                第一次，即k=1

T(n/2)=2T((n/2)/2)+n/2                        第二次，即k=2

T((n/2)/2)=2T(((n/2)/2)/2)+(n/2)/2            第三次，即k=3

即：
T(n/20)=2T(n/21)+n/20 第一次，即k=1，t=2 ①
T(n/21)=2T(n/22)+n/21 第二次，即k=2，t=4 ②
T(n/22)=2T(n/23)+n/22 第三次，即k=3，t=8 ③

③式带入②式得：T(n/2)=2(2T(n/23)+n/22)+n/21=22T(n/23)+n ④；
②式代入①式得：T(n)=2(22T(n/23)+n)+n=23T(n/23)+3n ⑤；

三式得出T(n)=23T(n/23)+3n ⑤，故当有k个式子，且最后一个的式子表达是T(2)=2T(1)+2的时候，⑤式中的次幂3可换为k，即T(n)=2kT(n/2k)+kn ⑥，而这中间使2k=n，才得最后一个表达式代入总式内故得T(n)=2kT(1)+kn ⑦。

此时解开⑦式便可。
∵2k=n
∴k=log2n
∴T(n)=n+nlog2n
∴O(n)=nlog2n
 

假设某算法的计算时间表示为递推关系式 T(n)=3T(\dfrac{n}{2})+\Theta(n)T(n)=3T(2n​)+Θ(n)，T(1)=\Theta(1)T(1)=Θ(1)，则算法的时间复杂度为

1.  A. 

   \Theta(n)Θ(n)

    B. 

   \Theta(n^{\log_23})Θ(nlog2​3)

    C. 

   \Theta(n \log n)Θ(nlogn)

    D. 

   \Theta(n^{\log_23}\log n)Θ(nlog2​3logn)

百度安全验证


 

   关于归并排序时间复杂度 T（n） =2T（n/2）+O（n）_rocling的博客-CSDN博客_t(n)=2t(n/2)+n时间复杂度

图像 小部件