哈希表O（1）攤銷或O（1）平均攤銷？

這個問題看起來有些迂腐，但我一直在努力深入研究Amortized分析，並且對於爲什麼插入一個哈希表是O（1）分期付款有點困惑（注意：我不是在談論表加倍，我明白）哈希表O（1）攤銷或O（1）平均攤銷？

使用此定義，「攤銷分析給出了在最差情況下每項操作的平均性能（隨時間變化）。」看起來N個插入散列表的最壞情況會導致每個操作的衝突。我相信當負載平衡保持較低時，通用散列保證以1/m的速率發生碰撞，但是在理論上每個插入點都可能碰撞嗎？

好像技術上平均攤銷分析哈希表的插入是O（1）。

編輯：您可以假設哈希表使用基本鏈接，將元素放置在相應鏈接列表的末尾。我的問題的真正含義是指對概率算法的攤銷分析。

編輯2：我發現this崗位上快速排序，「也有攤銷運行時間之間的微妙而重要的迪FF erence和預期運行時間快速排序隨機樞軸需要爲O（n log n）的預計運行時間，但它的。最壞情況下的運行時間在Θ（n^2）內，這意味着快速排序會花費（n^2）美元的可能性很小，但是隨着n增長，這種情況發生的概率接近零。我認爲這可能回答我的問題。

來源

2017-09-04 K.Enfield

有實現哈希表的方法很多，而實施的選擇有差別。例如，如果散列桶是（未排序的）鏈接列表，則假設您從不調整表的大小，那麼插入是* always * O（1）。 – psmears

不同的實現將以不同的方式處理衝突。例如，衝突可能會在未來備有現貨，也可以存儲在同一個地方，而是通過鏈接列表，或類似，但通過樹。上請註明碰撞是如何處理的，所以我們有一個固定的目標來分析的細節。 – TheGreatContini

理論上你可以在每次插入時都會碰到一個碰撞，但這意味着你有一個糟糕的表現散列函數，無法在鍵的「桶」中間隔出值。一個理論上完美的哈希函數總是會把一個新的值放到一個新的桶中，這樣每個鍵都會引用它自己的桶。（我假設一個鏈式哈希表，並將鏈字段稱爲「桶」，就像我被教過的那樣）。理論上最壞的情況下，函數會將所有密鑰粘貼到同一個桶中，導致長度爲N的桶中的一個鏈。

分期付款背後的想法是，如果給定了相當好的散列函數，則最終需要一個線性時間插入是因爲插入次數> O（1）的次數將大大減少插入簡單次數和O（1）的次數。這並不是說插入沒有任何計算（散列函數仍然需要計算，在某些特殊情況下，散列函數可能比查看列表更加沉重）。

這給我們帶來了在大O的一個重要概念，它是計算時間複雜度，當你需要看看最常執行的行動的想法一天結束。在這種情況下，插入的值不會與另一個散列衝突。

來源

2017-09-08 23:28:22

哈希表O（1）攤銷或O（1）平均攤銷？

回答

相關問題