algorithm - 归并排序的大O复杂度

Question

我有一个关于合并排序的 Big Oh 的讲座，我很困惑。

显示的是:

0 合并 [<----- n -------->] = n

1 合并 [<--n/2--][-n/2--->] = (n/2 + n/2) = n

2 合并 [n/4][n/4][n/4][n/4] = 2(n/4 + n/4) = n

....

log(n) 合并 = n

总计 = (n + n + n + ... + n) = lg n= O(n log n)

我不明白为什么 (n + n + ... + n) 也可以表示为 n 的以 2 为底的对数，以及它们如何得到 2 次合并 = 2(n/4 + n/4)

Answer 1

在 1 次合并的情况下，您有两个要排序的子数组，其中每个子数组花费的时间与要排序的 n/2 成正比。从这个意义上讲，要对这两个子数组进行排序，您需要的时间与 n 成正比。

类似地，当您进行 2 次合并时，有 4 个子数组需要排序，其中每个子数组将花费与 n/4 成正比的时间，这将再次加起来为 n.

类似地，如果您有n 合并，则将花费与n 成正比的时间来对所有子数组进行排序。从这个意义上说，我们可以将合并排序所花费的时间写成如下。

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

你会明白这个递归调用可以深入(比如到 h 的高度)直到 n/(2^h) = 1。通过在此处取对数，我们得到h=log(n)。这就是 log(n) 出现的原因。这里的log取自基数2。

由于您有 log(n) 个步骤，其中每个步骤花费的时间与 n 成正比，因此花费的总时间可以表示为，

n * log(n)

在大 O 表示法中，我们将其作为上限 O(nlog(n))。希望你明白了。

递归树的下图将进一步启发您。