基于比较的排序是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)。