0
我有一個散列表，它由1000個元素和100個桶組成，每個桶最多有100個條目。假設一個存儲桶有100個條目（即該存儲桶列表中有100個條目）。現在，如果我所搜索的項目是存儲桶列表中的第100個，那麼大O符號的時間複雜度是多少。 O（100）或O（n）？還是其他什麼？鏈式散列表中的時間複雜度是多少
A
回答
0
大O符號的一點是，你不「假設一個桶有100個條目」，你讓它的條目數爲n，並得到一個表達式爲n。
對於列表中的n條目，時間複雜度將爲O(n)，忽略您使用的任何散列函數。
請注意，這是最糟糕的情況（最後一項），平均而言，搜索運行在O(1)。
0
您的問題並不重要，因爲big-O表示法表示效率如何隨元素數量變化而變化，例如，元素的數量增加了超過1000，並且你沒有告訴我們這種行爲。
例如，對於大O符號效率發現，特定元素可能是：
如果一桶元素在將永遠不會有超過100個元素結束，然後O（1）
如果元素停留在那個桶中的位置100處，那麼即使在它之後追加了更多的項目，那麼假設搜索將從桶的開始處開始，那麼它仍然是O（1）
如果在該桶留在N/10元件的數量，那麼它的，如果元件保持在該桶的端部，但元件的數量在其中總是立方根O（N）
如果元素停留在該桶的末尾並且其中元素的數量總是大約爲3 * sqrt（N），則O（平方（立方根（N）））
sqrt（N））
正如你所看到的，O是將搜索時間與總數的元素，但是您沒有給出足夠的數據點來描述曲線。
相關問題
- 1. 密碼散列函數的時間複雜度是多少？
- 2. Collection.toArray（）的時間複雜度是多少？
- 3. 將地圖轉化爲鏈接列表的時間複雜度是多少
- 4. 獲取散列表中密鑰列表的時間複雜度？
- 5. 散列表和陣列列表的時間複雜度
- 6. 單鏈表中的時間複雜度
- 7. R列表中名稱查找的時間複雜度是多少？
- 8. 從Python中列表彈出元素的時間複雜度是多少？
- 9. 減少時間複雜度
- 10. 我的代碼中的時間複雜度是多少
- 11. Java中TreeSet的lower（）/ higher（）的時間複雜度是多少？
- 12. 確定給定散列槽的主機的運行時複雜度是多少？
- 13. 方案中'assoc'函數的時間複雜度是多少？
- 14. Python中collections.Counter（）的時間複雜度是多少？
- 15. Ruby中Array＃uniq方法的時間複雜度是多少？
- 16. TreeSet中有序操作的時間複雜度是多少？
- 17. Python中dict.keys（）的時間複雜度是多少？
- 18. Java中LinkedList.getLast（）的時間複雜度是多少？
- 19. clojure中count函數的時間複雜度是多少？
- 20. C++中std :: next_permutation（）函數的時間複雜度是多少？
- 21. java中lastIndexOf的時間複雜度是多少？
- 22. java中StringBuilder.append（）的時間複雜度是多少？
- 23. Python中zip（）的時間複雜度是多少？
- 24. java中HashMap.containsValue（）的時間複雜度是多少？
- 25. 分時排序算法的時間複雜度是多少？
- 26. 根據Big-O表示法，下列方法的時間複雜度是多少？
- 27. 這個排列算法的空間複雜度是多少？
- 28. 下面的遞歸函數的時間複雜度是多少
- 29. NavigableMap的floorEntry（）方法的時間複雜度是多少？
- 30. 下面的僞代碼的時間複雜度是多少？
我沒有得到你的數據結構 – deviantfan
它是哈希表，有100個桶，每個桶最多可以鏈接100個項目，以防碰撞。 – deepdive
因此，元素的最大數量在100到10000之間，取決於值？那麼......如果我們測量有多少元素需要搜索：O（1），因爲搜索100（獨立於散列表中的總數）是恆定的。順便說一句。 O（1）== O（100） – deviantfan