这个归纳证明,mergesort是O(n)有什么问题？

Question

基于比较的排序是nlog(n)的大o,因此我们知道mergesort不能是O(n).不过,我无法通过以下证据找到问题:

命题P(n):对于长度为n的列表,mergesort需要O(n)时间.

P(0):空列表上的合并排序只返回空列表.

强诱导:假设P(1),...,P(n-1)并试图证明P(n).我们知道在递归mergesort的每一步,两个大约"半列表"被合并,然后"压缩".每个半列表的合并排序通过归纳获得O(n/2)时间.拉紧需要O(n)时间.因此该算法具有M(n)= 2M(n/2)+ O(n)的递归关系,其为2O(n/2)+ O(n),其为O(n).

Answer 1

比较线性搜索为O(1)的"证据".

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

这里的问题是,为了使归纳起作用,必须有一个大O常数,它既适用于假设,也适用于结论.这在这里是不可能的,你的证据是不可能的.