2
A
回答
9
不，絕對不是。鏈表無法快速找到某個項目 - 這是O（n）。
在散列表中搜索只有O（1）如果你有足夠好的散列碼。如果全部您的密鑰具有相同的哈希碼，則無論您使用哪種編址方案，都是O（n）。
+1
這是最有名望的點，我見過：O – Shivam 2013-02-19 19:24:17
+2
富有變得更豐富。 – 2013-02-19 19:25:35
+1
@SotiriosDelimanolis：不是從這個答案我不 - 至少不會，除非它被接受。 – 2013-02-19 19:26:50
5
除非在其他結構中保留對鏈接列表中的節點的引用，否則無法訪問O（1）中鏈接列表中的元素。這是因爲鏈表保持對列表頭部的引用，並且必須遍歷每個下一個元素以找到所請求的元素，這出現在O（n）中。
0
不，您不能在O（1）複雜度內的鏈接列表中進行搜索。
哈希表創建具有相同哈希值的元素的結構鏈或鏈接列表。
如果哈希值是均勻分佈的（好的哈希值），那麼哈希表將具有O（1）複雜度來搜索元素。哈希表具有存儲桶可以從哈希值訪問每個存儲桶，然後每個存儲桶包含具有相同哈希值的元素的鏈接列表。
相關問題
- 1. 在O（1）時間搜索可能嗎？
- 2. 實際上是鏈接列表添加O（N）或O（1）？
- 3. Haskell：與O（1）追加和O（1）索引的Datastruture？
- 4. 窮舉搜索Big-O
- 5. 如何刪除哈希表中的O（1）雙鏈接鏈接？
- 6. C兩個鏈表搜索
- 7. 搜索鏈接列表
- 8. 單鏈接列表搜索
- 9. 搜索有序鏈表上
- 10. C鏈表搜索功能
- 11. 搜索鏈接列表
- 12. 搜索併發鏈表
- 13. 哈希如何有一個o（1）的搜索時間？
- 14. 對象文字搜索的深度比O（1）慢嗎？
- 15. 算法分析 - 在碰撞列表中O（1）中的哈希搜索
- 16. Apple Mach-O鏈接器警告 - 框架搜索路徑？
- 17. 如何在O（n）時間內對雙鏈表進行二進制搜索？
- 18. 哈希表O（1）攤銷或O（1）平均攤銷？
- 19. Solr搜索：SEVERE：java.lang.ArrayIndexOutOfBoundsException：-1
- 20. 如何更改我的鏈接列表插入功能從O（N）到O（1）
- 21. 在多（1-n）關係表上搜索
- 22. Excel - 搜索表1使用表2中的列表
- 23. 鏈接到實際搜索頁面的搜索表單
- 24. Big O - O（N^2）or O（N^2 + 1）？
- 25. 圖形搜索O（log（N）（N + M）
- 26. O（n）中的2鍵搜索算法
- 27. O（log n）中的二叉搜索樹？
- 28. 二進制搜索W/O庫方法
- 29. 在O（log（t）* h）中搜索B-tree
- 30. C程序搜索FILE I/O
把所有的元素放在一個哈希集？ – assylias 2013-02-19 19:16:56
asslias，你是對的，但是將元素添加到哈希集合是O（n）:) – 2013-02-19 19:19:45
@ilanberci是的，但是你只需要爲多個查找操作一次。 – Eric 2013-02-19 19:20:14