复杂性分析练习
Complexity analysis exercise
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))
这是否正确准确？
after k iterations we have:
T(n)=2^k * T(n-3k)+θ(1)*k
不太正确，因为每次展开后 θ(1) 的倍数加倍：
我们使用标准公式求和几何级数的地方。请注意，尾随项不是 k，而是 2^k。不过，您的停止条件 n = 3k 是正确的，因此：
因此您的最终结果是正确的，即使其中一个推理步骤是错误的。
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))
这是否正确准确？
after k iterations we have:
T(n)=2^k * T(n-3k)+θ(1)*k
不太正确，因为每次展开后 θ(1) 的倍数加倍：
我们使用标准公式求和几何级数的地方。请注意，尾随项不是 k，而是 2^k。不过，您的停止条件 n = 3k 是正确的，因此：
因此您的最终结果是正确的，即使其中一个推理步骤是错误的。