问基于主定理的虚拟合并实例的渐近分析

EN

我们可以将正常合并排序所需的时间考虑如下(合并2个大小为n/2的列表，合并4个大小为n/4的列表，合并8个大小为n/8的列表，依此类推)：

2(n/2) + 4(n/4) + 8(n/8) + 16(n/16) + ... + n(1)

这可以简化为：

n + n + n + ... + n = O(nlogn)

对于您的新合并排序，我们有：

2(n/2)^2 + 4(n/4)^2 + 8(n/8)^2 + 16(n/16)^2 + ... + n(1)^2

这可以简化为：

n^2/2 + n^2/4 + n^2/8 + n^2/16 + ...

然后就变成了：

n^2(1/2 + 1/4 + 1/8 + 1/16 + ...) = O(n^2)

我希望这能吸引你的直觉。