構建二叉樹的漸近複雜度

Question

構建大小爲n的平衡二叉樹的複雜性是什麼？

節點插入是O（log n）。

然而，當你走，累積時間爲

O（（日誌1）+（日誌2）+ ... +（日誌（N-1））+（log n）的）。

這個「加起來」是什麼？

它是o（n log（n）），小'o'，我不知道多小。

Answer 1

log(1) + log(2) + ... + log(n) = log(1*2*..*n) = log(n!)這是Theta(nlogn)

因此，從頭開始構建一個（平衡）樹具有與之結合的緊密漸近Theta(nlogn)

---

編輯：
我也想告訴你一個證明您無法使用任何算法構建比O(nlogn)更好的BST。基本上 - 這是因爲通過簡單地用「更好」算法構建樹，然後 - 在樹上進行順序遍歷並輸出元素，它將允許排序優於O(nlogn)。結果將是一個排序的數組。
複雜性按順序遍歷是O(n)，並且由於假設樹構建得更快，所以O(nlogn) - 我們得到的排序是Omega(nlogn)有問題的事實是矛盾的。