algorithm - 在虚构的归并排序示例中使用主定理进行渐近分析

Question

假设我们有一个虚构的合并排序，其中合并操作的成本为 O(n^2)而不是 O(n) .那么根据主定理，我们有:

T(n) <= aT(n/b) + O(n^d)
T(n) <= 2T(n/2) + O(n^2)

自 a < b^d ，我们发现:

T(n) = O(n^d)
T(n) = O(n^2)

然而，直觉上，大 O 应该是 T(n) = O(n^2 logn) 也是有道理的因为每次递归都会对数字执行二次(n^2)搜索。例如，在线性搜索的情况下，合并排序是 O(n logn) .有谁知道为什么绑定(bind)不是 O(n^2 logn) ？这可能与每次递归时搜索量减半有关吗？

Answer 1

我们可以将正常合并排序所花费的时间想象如下(我们合并 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)

我希望这能引起您的直觉。