樹排序：時間複雜度

爲什麼平均情況下的時間複雜度爲tree sortO(n log n)？樹排序：時間複雜度

維基百科：

添加一個項目到二叉搜索樹是平均的O（log n）的過程（在大O表示法），因此增加n項複雜度爲O（N日誌N ）處理

但我們並不是每次都將項目添加到n項目的樹中。我們從一棵空樹開始，逐漸增加樹的大小。

所以它看起來更像

log1 + log2 + ... + logn = log (1*2*...*n) = log n!

我缺少的東西？

來源

2016-08-02 rapt

之所以O(log(n!)) = O(nlog(n))是由兩部分組成的答案。一是擴大O(log(n!))，

log(1) + log(2) + ... + log(n)

我們既可以在這裏同意log(1)，log(2)，和所有的數字高達log(n-1)都小於log(n)。因此，下面的不等式可以製成，

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)

現在的答案的另一半取決於一個事實，即從1到n的數字的一半是小於n/2大。這意味着，log(n!)將比n/2*log(n/2)又名總和log(n!)的前半部分較大，

log(1) + log(2) + ... + log(n) => log(n/2) + log(n/2) + ... + log(n/2)

原因是，的log(1) + log(2) + ... + log(n)上半年log(1) + log(2) + ... + log(n/2)，其小於n/2*log(n/2)作爲證明由第一不等式，從而通過加上總和log(n!)的後半部分，可以證明它大於n/2*log(n/2)。

所以這兩個不等式，它可以證明O(log(n!)) = O(nlog(n))

來源

2016-08-02 04:44:05

爲什麼O定義需要第二個不等式？另外，我認爲維基百科中的解釋是誤導性的：在實踐中，複雜性是log（n！）。它不會比log（n^n）更糟糕的事實很酷，但我們也可以說它不會比log（n^n^n）更糟糕。 – rapt

@rapt，因爲根據大O符號，下界的'n/2 * log（n/2）'和'nlog（n）'是一樣的，所以你有不等式'O（nlog（n））< = O（log（n！）<= O（nlog（n））' –

這是真的，但是當我看大O符號的正式定義時，看起來第一個不平等就是所有要表明的'log（n！）= O（n log（n））'無論如何，這是一個很好的簡單解釋，它提醒了我一些細節;並確認當前維基百科「樹排序」條目不太準確。 – rapt

O(log(n!)) = O(nlog(n))。

https://en.wikipedia.org/wiki/Stirling%27s_approximation

（答案必須是30個字符）。

來源

2016-08-02 04:07:10 wookie919

你不需要斯特林是什麼？簡單的對數規則和O定義。但我想知道爲什麼在這種情況下指定複雜度爲O（log n！）是不常見的。通常人們使用O符號來表示「這大致是操作次數」，雖然它不準確。換句話說，通常使用O（log n！）的算法可能比O（n log n）中的一個更好。 – rapt

@rapt我認爲你得到的是'log（n！）'可能比'n log（n）'更尖銳。但在世界上，如果大O，這是完全不是這樣的。 'O（log（n！））'確實等於'O（n log（n））'這裏證明了這一點：http://stackoverflow.com/questions/8118221/what-is-ologn-and-on-and -stirling-approximation我認爲'O（n log（n））'是首選的原因是因爲人們發現它更容易掌握。 – wookie919

是的。但正如我多次說過的那樣，大O表示法被非正式地用來顯示實際的時間複雜度，由於它只是時間複雜度的上限，所以它不是很準確。無論如何，這是一個很好的答案。謝謝。 – rapt

樹排序：時間複雜度

回答

相關問題