归并排序是 O(n) 的归纳证明有什么问题？
基于比较的排序是nlog(n)的大欧米伽，所以我们知道归并排序不可能O(n)< /强>。尽管如此，我无法通过以下证明找到问题：
Proposition P(n): For a list of length 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)。
Comparison based sorting is big omega of nlog(n), so we know that mergesort can't be O(n). Nevertheless, I can't find the problem with the following proof:
Proposition P(n): For a list of length n, mergesort takes O(n) time.
P(0): merge sort on the empty list just returns the empty list.
Strong induction: Assume P(1), ..., P(n-1) and try to prove P(n). We know that at each step in a recursive mergesort, two approximately "half-lists" are mergesorted and then "zipped up". The mergesorting of each half list takes, by induction, O(n/2) time. The zipping up takes O(n) time. So the algorithm has a recurrence relation of M(n) = 2M(n/2) + O(n) which is 2O(n/2) + O(n) which is O(n).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
比较线性搜索为 O(1) 的“证明”。
这里的问题是，为了使归纳法发挥作用，必须有一个大 O 常数既适用于假设又适用于结论。这在这里是不可能的，对于你的证明也是不可能的。
Compare the "proof" that linear search is O(1).
The problem here is that, for the induction to work, there must be one big-O constant that works both for the hypothesis and the conclusion. That's impossible here and impossible for your proof.
“证明”仅涵盖单次传递，不涵盖 log n 次传递。
重复仅显示一次传递的成本与前一次传递的成本的比较。为了正确起见，递归关系应该具有累积成本而不是增量成本。
您可以通过查看示例合并排序来了解证明的失败之处 http://en.wikipedia.org/维基/Merge_sort
The "proof" only covers a single pass, it doesn't cover the log n number of passes.
The recurrence only shows the cost of a pass as compared to the cost of the previous pass. To be correct, the recurrence relation should have the cumulative cost rather than the incremental cost.
You can see where the proof falls down by viewing the sample merge sort at http://en.wikipedia.org/wiki/Merge_sort
关键在于：所有引用 n 的特定值的归纳步骤都必须引用特定的函数 T(n)，而不是 O() 表示法！
O(M(n)) 表示法是关于整个函数从问题大小到性能保证的行为的陈述（渐近地，随着 n 无限制地增加）。归纳的目标是确定性能界限 T(n)，然后可以将其简化（通过删除常数和低阶因子）至 O(M(n))。
特别是，您的证明的一个问题是您无法从纯粹关于 O() 的陈述返回到关于给定 n 的 T(n) 的陈述。 O() 表示法允许您忽略整个函数的常数因子；它不允许您在递归构造相同函数时一遍又一遍地忽略常数因子...
您仍然可以使用 O() 表示法来简化您的证明，通过演示：
并以通常的归纳方式传播该谓词。但是你需要保留 F() 的常数因子：这个常数因子对你的分而治之递归的解决方案有直接影响！
Here is the crux: all induction steps which refer to particular values of n must refer to a particular function T(n), not to O() notation!
O(M(n)) notation is a statement about the behavior of the whole function from problem size to performance guarantee (asymptotically, as n increases without limit). The goal of your induction is to determine a performance bound T(n), which can then be simplified (by dropping constant and lower-order factors) to O(M(n)).
In particular, one problem with your proof is that you can't get from your statement purely about O() back to a statement about T(n) for a given n. O() notation allows you to ignore a constant factor for an entire function; it doesn't allow you to ignore a constant factor over and over again while constructing the same function recursively...
You can still use O() notation to simplify your proof, by demonstrating:
and propagating this predicate in the usual inductive way. But you need to preserve the constant factor of F(): this constant factor has direct bearing on the solution of your divide-and-conquer recurrence!