複雜性和二進制嘗試

Question

我有一個很大的問題，理解複雜性，尤其是與binary trees。

例如，我知道當我們遇到問題時，說問題的大小爲x=log2(sizeofarray)，但我不明白log2的來源？

Answer 1

這是日誌因爲樹的每個級別將您的問題分成兩部分。

例如，考慮這組數據：

{ 1, 2, 3, 4, 5, 6, 7, 8 } 

第一級可能是

{ 1, 2, 3, 4 }, { 5, 6, 7, 8 } 

第二級：

{ 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } 

第三級：

{ 1 }, { 2 }, { 3 }, { 4 }, { 5 }, { 6 }, { 7 }, { 8 } 

---

在這裏用8個值，登錄（8）= 3，並且有在樹3倍的水平。

---

也看到這些其他StackOverflow的問題更多：

• 「Why is the height of a balanced binary tree log(n)? (Proof)」 - 答案遵循類似的靜脈the answer是Amadan張貼在這個問題上。
• 「Search times for binary search tree」 - 包含一些漂亮的ASCII藝術，並檢查最佳/最差的情況。

Answer 2

讓我們以二分查找爲例。假設您有64個元素的排序列表，並且您正在搜索特定的元素。在每次迭代中，您將數據集減半。通過您的數據集有1元的時候，你已經減半它的6倍（算上箭頭，而不是數字）：

64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 

這樣做的原因是，64 = 2^6，其中2是基礎（你鴻溝數據集在每次迭代中分2部分），指數爲6（因爲您在6次迭代中達到底部）。還有另一種方式來寫這篇文章，因爲冪有其對數倒數：

64 = 2^6 
6 = log2 64 

所以我們可以看到，迭代次數與元素數量的基礎二對縮放。