從一棵空樹開始，在大O符號中插入紅黑樹的複雜性是多少？

如果我有10種元素，從一個空的樹，什麼是在大O符號插入10個元素融入到紅色黑色的複雜性？從一棵空樹開始，在大O符號中插入紅黑樹的複雜性是多少？

它是否會超過O（log 10），因爲每次插入元素時，都必須搜索元素的適當位置，並在祖先節點和子節點之間執行一系列旋轉。因此，如果我有N個元素並將N次插入紅黑樹，是不是會使它成爲O（n log n）？

感謝您的任何幫助。

來源

2009-11-15 John

將單個元素插入RB樹的時間複雜度爲O(log n)，其中n是樹的當前大小。

將n元素插入空的RB樹的時間複雜度因此是O(n log n)。

將10元素插入空的RB樹的時間複雜度是恆定的，或O(1)。由於樹開始爲空，並且由於插入的元素數量是固定的，因此這裏沒有可變元素。

來源

2009-11-15 03:41:20 yfeldblum

你從來不會使用大O以恆定的（除1），因爲O（10）指完全一樣的O（1）或O（128291），所以按照規定，您總是用O（1）！

那麼，讓我們來看看什麼是將K個到初始爲空的RB-樹大O。第一次插入是一個恆定的時間，所以稱它爲O（1）;並在有X個項目時插入X + 1是O（log（X））（即使你必須向下旋轉每一步，仍然與log（X）成正比，所以O（log（X）），因爲「層」或「層」的數量只與X以對數方式增長 - 因爲K層的RB樹有許多節點，它們的增長爲2到K次方）。

所以我們希望X的log（X）從2到N（加上一個costant）的總和，恰好等於N的階乘對數。對於Stirling's approx，大約是N log（N） - N，以大O的形式再次歸結爲N log（N）。

來源

2009-11-15 03:44:57

謝謝，你解釋這真的很好。 – John

@約翰，所以如果你喜歡它，爲什麼不接受它（使用複選標記下方的數字大「upvotes數」的問題左上方） - 這是基本的禮儀SO，並會幫助您開始在SO聲譽梯（是的，你通過接受獲得代表！）。 –

@AlexMartelli我相信你有一個小的錯字：插入時，有X項是'O（logX）'而不是'O（X）'。很好回答btw，+1。 –

什麼@Justice和@Alex實際上是在一個O(f(N))複雜性度量談論限制行爲（例如運行時間，比較次數，無論什麼），因爲N趨於無窮大。

他們說，如果你代替N個特定的值時，O術語不再有意義。

還有一點，他們沒有做。那就是你不能用O(...)表示法中的陳述來告訴你N小時會發生什麼。根據定義，「大O」符號不會告訴你在這種情況下會發生什麼。

這不只是迂腐。例如，成本函數F(N) = 1,000,000 * N + N**2是O(N**2)，但第一項支配對於N小於1000的值。如果你在這種情況下嘗試使用O(N**2)度量作爲估計量，你將得到完全錯誤的答案。

來源

2009-11-15 04:21:46

從一棵空樹開始，在大O符號中插入紅黑樹的複雜性是多少？

回答

相關問題