我有一个关于合并排序的 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)
最佳答案
在 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))
。希望你明白了。
关于algorithm - 归并排序的大O复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43335561/