algorithm - Mergesort：更改分割点时计算复杂度如何变化？

Question

我必须从我的算法书中做一个练习。假设实现了一个合并排序，以将一个数组拆分为 α，α 的范围为 0.1 到 0.9。

这是计算分割点的原始方法

middle = fromIndex + (toIndex - fromIndex)/2;

我想把它改成这样：

factor = 0.1; //varies in range from 0.1 to 0.9
middle = fromIndex + (toIndex - fromIndex)*factor;

所以我的问题是：

score 4 · Accepted Answer

这确实改变了实际复杂度，但不会改变渐近复杂度。

如果你考虑一下你会得到的新的递归关系，它会是

T(1) = 1

T(n) = T(αn) + T((1 - α)n) + Θ(n)

纵观递归树，树的每一层仍有每层总共有 Θ(n) 个工作，但层数会更多。具体来说，假设 0.5 ≤ α < 1。那么在 k 次递归调用之后，递归中剩余的最小块的大小将具有大小 n α ^k。当它达到大小一时，重复停止。求解，我们得到：

n α ^k = 1

α ^k = 1/n

k log α = -log n

k = -log n / log α

k = log n / log (1/α)

换句话说，改变 α 会改变递归深度的对数项上的常数因子。当 α = 0.5 时，上述方程最小化（因为我们受到 α ≥ 0.5 的限制），因此这将是最佳的分割方式。然而，选择其他拆分仍然会给出运行时 Θ(n log n)，尽管具有更高的常数项。

希望这可以帮助！

1 回答 1