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

Question

我必须根据我的算法书做一个练习。假设实现归并排序以按 α 拆分数组，α 的范围为 0.1 到 0.9。

这是计算 split 点的原始方法

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

我想把它改成这样:

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

所以我的问题是:

1. 这会影响计算复杂度吗？
2. 对递归树深度有何影响？

Answer 1

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

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

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的限制)，所以这将是最优的 split 方式。然而，选择其他拆分仍然会给出运行时 Θ(n log n)，尽管具有更高的常数项。

希望这对您有所帮助!