地圖提供 O(1) 查找。難道我們不能遍歷數組一次并構建一個對應于它的索引（數組的反面）的映射，當我們想要搜索我們可以調用map[VALUE]的東西時它會返回索引。它可能不適用于數組中的大值，但假設a[i]<10^5我們不能這樣做而不是二進制搜索嗎？然后，每個查詢將是 O(1)。PS：我的意思是無序地圖..
3 回答
慕碼人8056858
TA貢獻1803條經驗 獲得超6個贊
以下是您可能要考慮的問題 -
您不能在地圖中存儲具有相同值的多個元素
查找時間是
O(log(n))和不是O(1)地圖中發生的事情并不神奇，它讓我們可以在更短的時間內訪問它。有一個散列過程在后臺進行，
unordered_map這O(1)也需要時間。所以，大 O 隱藏了一個很大的常數時間因素。標準map為您提供O(logn)查找，時間復雜度與數組中的二進制搜索相同。
你得到的搜索的平均時間復雜度是差不多的。在 C++ 中使用標準映射的主要問題是它無法保存具有相同值的多個元素。使用 map 可能獲得的一個優勢是刪除和插入時間將是O(logn).
因此，如果您知道您將要處理的數據集沒有重復元素和/或將頻繁添加/刪除元素，那么在這種情況下您肯定可以將 map 視為更好的選擇
添加回答
舉報
0/150
提交
取消