時間複雜度，二進制（搜索）樹

假設我有一個完整的二叉樹達到一定深度d。遍歷（預遍歷）此樹的時間複雜度是多少。時間複雜度，二進制（搜索）樹

我很困惑，因爲我知道樹中節點的數量是2^d，所以時間複雜度是BigO(2^d)？因爲樹正在成倍增長。

但是，在互聯網上的研究，大家說的遍歷BigO(n)其中n爲元素的數量（這將是在這種情況下2^d），不BigO(2^d)，我缺少什麼？

謝謝

2012-10-23 dgamma3

n = 2^d。這裏沒有問題。 –

如果n = 2^d，那麼我可以說BigO（n）或BigO（2^d）。如果n是2^d？ – dgamma3

習慣上使用n。問題的大小用n表示，複雜度也是如此。 –

n被定義爲節點的數量。

2^d僅僅是節點的數量時在該深度處每一個可能的結滿

即

 o 
/ \ 
    o  o 
/\ 
o o

只有5個節點時，2^d爲8

完全二叉樹有充滿除了最後一排，所有的節點都被填充了向左的每個節點。您可以在維基百科上找到的定義

2012-10-23 23:52:24

我的問題是，如果它是一棵完整的樹，也就是說。全部已完成 – dgamma3

更新後的答案。 –

即使你可以表達的時間複雜度爲O（2^d），這幾乎沒用，因爲它不是東西，你可以用它來比較它的時間複雜度任何其他收藏品。

表達時間複雜度爲O（n）另一方面非常有用。它可以準確地告訴你在收集項目數量時如何反應，而不必確切知道集合是如何實現的，並且可以將其與其他集合的時間複雜性進行比較。

2012-10-23 23:56:51 Guffa

所以你說什麼，實際上我選擇哪一個並不重要。但是bigO（n）更直觀。 – dgamma3

不真的明白爲什麼O（2^d）是除非，這是因爲界限如此之高？ – dgamma3

@ dgamma3：這是非常沒用的，因爲你必須知道樹是如何實現的，否則它不會告訴你有關當你添加更多項目時收集如何反應。 – Guffa

回答