algorithm - 链接列表上合并排序的运行时间？

Question

我遇到了这段代码来对链接列表执行合并排序。作者声称它的运行时间为 O(nlog n)..这是它的链接... http://www.geeksforgeeks.org/merge-sort-for-linked-list/ 我的说法是它至少需要 O(n^2) 时间......这是我的论点......看，你划分列表(无论是数组还是链表)，记录 n 次(指递归树)，在每个分区中，给定一个大小为 i=n, n/2, ..., n/2^ 的列表k，我们将花费 O(i) 时间来划分原始/已经划分的列表..因为 sigma O(i)= O(n)，我们可以说，我们需要 O(n) 时间来划分任何给定的调用分区(马虎)，所以考虑到执行单个分区所花费的时间，现在出现的问题是总共要发生多少个分区，我们观察到每个级别 i 的分区数等于 2^i ，所以求和 2^0+2^1+....+2^(lg n ) 给我们 [2(lg n)-1] 作为总和，它只是 (n-1) 简化，这意味着我们称分区 n-1，(让我们将其近似为 n)次，复杂度至少是 n^2 的大欧米茄..如果我错了，请告诉我哪里...谢谢:)

然后在一些回顾之后，我将主方法应用于递归关系，其中我将 1 的 theta 替换为用于这种类型的合并排序的数组上的常规合并排序的 1 的 theta(因为除法和组合操作每次取 n 次的 theta)，运行时间结果是 (n lg n) 的 theta ...我还注意到每个级别的成本是 n(因为 2 power i * (n/(2pow i)))...水平..暗示它的 theta (n lg n).....我刚刚解决了我自己的问题吗？请帮助我自己有点困惑..

Answer 1

大小为 n 的输入列表的递归复杂度定义为

T(n) = O(n) + 2 * T(n / 2)

展开这个我们得到:

T(n) = O(n) + 2 * (O(n / 2) + 2 * T(n / 4))
     = O(n) + O(n) + 4 * T(n / 4)

再次展开我们得到:

T(n) = O(n) + O(n) + O(n) + 8 * T(n / 8)

显然这里有一个模式。因为我们可以精确地重复这个展开 O(log n) 次，所以我们有

T(n) = O(n) + O(n) + ... + O(n)   (O(log n) terms)
     = O(n log n)