4

基于比较的排序是nlog(n)的大欧米茄，所以我们知道合并排序不能是O(n)。不过，我找不到以下证明的问题：

命题P(n)：对于长度为n的列表，合并排序需要O(n)时间。

P(0)：对空列表进行合并排序只返回空列表。

强归纳：假设P(1), ..., P(n-1)并尝试证明P(n)。我们知道，在递归归并排序的每一步，两个近似“半列表”被归并排序，然后被“压缩”。通过归纳，每个半列表的合并排序需要O(n/2) 时间。拉上拉链需要O(n)时间。因此，该算法具有M(n) = 2M(n/2) + O(n)的递归关系，即2O(n/2) + O(n)即O(n)。

4

3 回答 3

7

比较线性搜索是 O(1) 的“证明”。

  1. 空数组的线性搜索是 O(1)。
  2. 对非空数组的线性搜索比较第一个元素 (O(1))，然后搜索数组的其余部分 (O(1))。O(1) + O(1) = O(1)。

这里的问题是，为了使归纳起作用，必须有一个对假设和结论都起作用的大 O 常数。这是不可能的，你的证明也不可能。

于 2011-11-14T20:37:38.993 回答
4

“证明”仅涵盖单遍，不涵盖log n遍。

重复仅显示与前一次通过成本相比的通过成本。正确地说，递归关系应该具有累积成本而不是增量成本。

您可以通过查看http://en.wikipedia.org/wiki/Merge_sort上的示例合并排序来查看证明失败的地方

于 2011-11-14T20:30:13.193 回答
3

这里是关键：所有引用特定 n 值的归纳步骤必须引用特定函数 T(n)，而不是 O() 表示法！

O(M(n)) 表示法是关于整个函数从问题大小到性能保证的行为的陈述（渐近地，随着 n 无限制地增加）。归纳的目标是确定性能界限 T(n)，然后可以将其简化（通过删除常数和低阶因子）到 O(M(n))。

特别是，您的证明的一个问题是，对于给定的 n，您不能从纯粹关于 O() 的陈述回到关于 T(n) 的陈述。O() 表示法允许您忽略整个函数的常数因子；它不允许您在递归地构造相同的函数时一遍又一遍地忽略一个常数因子......

你仍然可以使用 O() 表示法来简化你的证明，通过演示：

T(n) = F(n) + O(something less significant than F(n))

并以通常的归纳方式传播这个谓词。但是你需要保留 F() 的常数因子：这个常数因子直接关系到你的分而治之递归的解决方案！

于 2011-11-15T00:18:54.270 回答