复杂性分析练习

Question

mcSort(A,l,r)  
  if r-l+1<4   
      then QuickSort(A,l,r)  
      else mcSort(A,l,r-3)  
           mcSort(A,l+3,r)

这个练习要求我对上述算法的复杂性进行分析。

我的想法是

T(n)=2T(n-3)+θ(1)

经过k次迭代，我们有：

T(n)=2^k * T(n-3k)+θ(1)*k  

因此，当3k=n这样k=n/3时，我们有

= 2^(n/3) * θ(1) + θ(n) = θ(2^(n/3))  

这是正确和精确的吗？

Answer 1

经过k次迭代，我们有： T(n)=2^k * T(n-3k)+θ(1)*k

不完全正确，因为在每次展开之后，添加的θ(1)倍数会加倍：

​

​

在这里，我们使用了几何级数求和的标准公式。注意，后面的术语不是k，而是2^k。但是，您的停止条件n = 3k是正确的，因此：

​

​

因此，您的最终结果是正确的，即使其中一个推理步骤是错误的。