如果刪除的平均情況是lg(n),這很有意義,因爲您必須執行percDown值才能保持堆的完整性,爲什麼插入和封裝堆不同?是不是相對於輸入(n)進行比較的數量除以2?爲什麼在二進制堆O(1)中插入的平均情況?
回答
這是一個有趣的命題。我試圖做一個基本的計算。請確認一下,並提出計算是否有問題。它基本上是一個有一些假設的機械計算。
假設:
- 目前已經有
2^k-1
元素的完全二叉樹k
水平。 - 我們增加
2^k
更多元素使樹具有k+1
的等級。 - 元素均勻隨機地獲得位於一個水平從
[1..k]
(3)表示的是,在舊樹中的每個元件基本上由一個新的元件代替。因此向上滲透的數量將爲:
k + 2 * (k-1) + 4 * (k - 2) + ... + 2^(k-1) * 1
= k + 2 * k + 4 * k + ... + 2^(k-1) * k - (2 + 2 * 2^2 + 3 * 2^3 + ... + (k - 1) * 2^(k-1))
= k * (2 + 4 + ... + 2^(k-1)) - (k * 2^k - 2 * (2^k - 1)) ......(a)
= k * (2^k - 1) - k * 2^k + 2 ^(k+1) - 2
= k * 2^k - k - k * 2^k + 2^(k+1) - 2
= 2^(k+1) - (k + 2)
(a)計算爲here。
因此,我們有2^k
元素使用(2^(k+1) - (k+1) - 1)
步驟過濾。因此,每個元素的平均成本是O((2^(k+1) - (k+1) - 1)/2^k) = O(2 - (k+2)/2^k)
,即O(1)
。
因此,我們可以假設插入成本不變。
注:如果我們假設一個元素將得到的概率0.5
替代,我們可以認爲因素成以上的計算,我認爲這這將導致分工越來越接近1
。
我還沒有完全想到這一點,但它似乎並沒有考慮到插入2^k個新元素時,樹上的元素可能會被替換幾次。 – Henry
這就意味着新元素有很多值都是舊值的最大值之一嗎?這是否是一種常見的平均情況? – user1952500
我假設每個節點最終都被替換了。所以實際上底層節點在上面的計算中更經常被替換。 – user1952500
爲什麼它不適合插入和percUping堆一樣嗎?
當您刪除head(h)時,將它與堆中的最後一個元素交換,即最長的子樹中的最低元素(l)。將l放入更高級別的堆的概率被認爲足夠低以至於可以被忽略,因爲它已經是其子樹的最低元素。
存在特殊情況。例如,包含N個相等整數的堆將在O(1)中進行頭提取。但這不是一般情況。
我只是想知道當開始學習二進制堆時完全一樣的東西。我在C中編寫了一個實現,當我計算不同的操作時,這個現象讓我感到困惑。在給出一些想法之後,我的直覺是,正如其他人所提到的那樣,當移除一個元素時,它在堆中的位置被最後一個元素替代,即屬於底部的元素,因此將被保證必須沉入底部。在我的測試中,我只嘗試移除堆的頂層元素,因此這些移除總是導致遍歷整個堆的高度(log n)。
另一方面插入,將新元素放在底部,並讓它浮起來。這是我的想法,因爲堆中的大多數元素都集中在較低的層次上,所以新節點可能只有一兩個跳轉到達正確的位置。即使節點的值是整個堆的平均值,通常也不需要一直跳到堆的垂直中間層(實際上,看起來像包含2^x個元素的堆的底層,實際上包含整個堆的一半以上節點)。不知道這是否合理,但它對我有用:)。
現在,如果通過去除我們談論消除任何給定的元素,而不僅僅是最上面的一個,我不明白爲什麼平均情況應該不會有O(1)太,從那以後,我們應該是最有可能去除底部附近的東西...
- 1. 爲什麼插入排序的最佳情況是O(n)&not O(n^2)?
- 2. 插入元素二進制最小堆
- 3. 在TSQL什麼呢表名(1)平均
- 4. 哈希表O(1)攤銷或O(1)平均攤銷?
- 5. 爲什麼不能在沒有二進制文件的情況下顯示非符號堆棧跟蹤?
- 6. 爲什麼堆排序的空間複雜度爲O(1)?
- 7. 插入點的二進制搜索 - 爲什麼插入點錯誤?
- 8. 爲什麼O(N日誌N)構建二進制搜索樹?
- 9. 平均數計算最壞的情況下,最好的情況下和平均情況下的複雜性
- 10. 爲什麼1/1/1900被插入到SQL中?它在某些情況下是NULL的替代方法嗎?
- 11. 爲什麼不能我輸入下面的情況下,輸入十進制值
- 12. 爲什麼在這種情況下1 = 1不成立?
- 13. 爲什麼在二進制補碼(-1 >> 1)== -1而不是0?
- 14. 爲什麼deleteMin的堆取O(logn)?
- 15. 爲什麼-127 >> 1的二進制表示是11000000?
- 16. 線性搜索的平均情況
- 17. 查找二進制樹O(1)中的位數
- 18. MATLAB:在方形二進制矩陣中查找「平均」索引
- 19. 什麼是Trie數據結構的最佳/最差/平均情況大O運行時間?
- 20. 爲什麼printf自動將%x%o%d轉換爲十六進制十六進制和十二進制
- 21. 插入到二進制
- 22. 比較插入操作的二進制堆
- 23. RemoveMin在二進制堆Java
- 24. C++二進制堆
- 25. 二進制文件I/O
- 26. 這個erlang二進制文件爲什麼會失敗binary_to_term/1?
- 27. 爲什麼二進制Keras CNN總是預測1?
- 28. 爲什麼在將二進制數據從PHP插入MySQL時使用bin2hex?
- 29. Python中的二進制I/O
- 30. C中優雅的二進制I/O?
你能詳細說明一下嗎?我以前沒有聽說過這個說法。當你說「平均情況」時,你的意思是「隨機輸入的平均值?」 – templatetypedef