0
我已閱讀維基百科，因爲訪問HAST表只是簡單地通過數組索引像hast_table[index]，所以它應該是O(1)，爲什麼的容貌表的時間最壞的情況下複雜度是O（n）。什麼是最壞的情況？爲什麼的容貌表的時間複雜度最壞情況下爲O（n）
A
回答
1
容量1的哈希表（使用側鏈）退化爲鏈表，導致查找需要在表的單個桶中進行線性搜索。
https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_linked_lists
相關問題
- 1. 最佳情況和最壞情況下的時間複雜度
- 2. 最壞情況下的時間複雜
- 3. 最壞的情況會是什麼時間複雜度？
- 4. 爲什麼代碼O（log n）的時間複雜度？
- 5. 最壞情況下的時間複雜度
- 6. 最壞情況下運行時間爲O，Ω爲最佳情況，但爲什麼有時在最壞情況下使用Ω？
- 7. 以下代碼的時間複雜度如何爲O（n）？
- 8. 爲什麼定義爲O（n^3）的矩陣乘法的時間複雜度？
- 9. 算法的最壞情況複雜度
- 10. 時間複雜度：O（logN）或O（N）？
- 11. 給定函數的最壞情況時間複雜度是什麼？
- 12. 快速帶O的最壞的情況下（N log n）的
- 13. 時間複雜度 - 計算算法的最壞情況
- 14. 散列的最壞情況時間複雜度（插入）
- 15. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 16. 爲什麼合併排序最差情況運行時間O（n log n）？
- 17. 爲什麼下面的代碼只有空間複雜度O（N）？
- 18. 爲什麼單詞O（n）的句子的逆時間複雜度？
- 19. 查找數組中缺失的數字，時間複雜度爲O（N），空間複雜度爲O（1）
- 20. 爲什麼python的list.append（）方法O（1）的時間複雜度？
- 21. 如何確定的時間複雜度爲O（M + N）或O（Math.max（M，N））
- 22. 爲什麼插入排序的最佳情況是O（n）＆not O（n^2）？
- 23. 爲什麼C++ STL映射容器O（log（n））的複雜性？
- 24. 時間複雜度 - O（n^2）到O（n log n）搜索
- 25. 計算算法的最壞情況下運行時間複雜度
- 26. 爲什麼我的底部複雜度不是O（n^3）
- 27. O（3^n）指數時間複雜度
- 28. 最壞情況下的搜索次數爲零的散列複雜度
- 29. 排序在最壞情況下O（n * log（n））
- 30. 爲什麼堆排序的空間複雜度爲O（1）？
最壞情況：所有元件被散列到同一個桶中。最糟糕的情況一般是由於內存有限（或者有無限的內存：非完美的哈希）。但是，由於分析可能更加複雜，請採取我的評論， [杜鵑哈希]（https://en.wikipedia.org/wiki/Cuckoo_hashing）+ [dearmortization]（https://en.wikipedia.org/wiki/Amortized_analysis）策略。 – sascha
https://www.youtube.com/watch?v=h2d9b_nEzoA – Alexander