地圖提供 O(1) 查找。難道我們不能遍歷數(shù)組一次并構(gòu)建一個(gè)對(duì)應(yīng)于它的索引（數(shù)組的反面）的映射，當(dāng)我們想要搜索我們可以調(diào)用map[VALUE]的東西時(shí)它會(huì)返回索引。它可能不適用于數(shù)組中的大值，但假設(shè)a[i]<10^5我們不能這樣做而不是二進(jìn)制搜索嗎？然后，每個(gè)查詢將是 O(1)。PS：我的意思是無(wú)序地圖..
3 回答
千巷貓影
TA貢獻(xiàn)1829條經(jīng)驗(yàn) 獲得超7個(gè)贊
哈希表，如Python 字典，將給出每次查找的攤銷常數(shù)平均成本。
對(duì)于大型數(shù)據(jù)集，這可能會(huì)成為二分查找的一個(gè)有趣的替代方法。
由于以下原因，某些算法可能絕對(duì)需要二分查找：
當(dāng)查找值不在數(shù)據(jù)集中時(shí)，二分查找仍然可以以相同的O(logn)成本判斷出數(shù)據(jù)集中大于查找值的最小值和小于查找值的最大值。
對(duì)我來(lái)說(shuō)，重復(fù)問(wèn)題不是什么大問(wèn)題，因?yàn)槟梢栽跀?shù)組中存儲(chǔ) (value, frequency) 或 (value, [payload1, payload2, ...]) 的元組，因此仍然使用哈希表。
慕碼人8056858
TA貢獻(xiàn)1803條經(jīng)驗(yàn) 獲得超6個(gè)贊
以下是您可能要考慮的問(wèn)題 -
您不能在地圖中存儲(chǔ)具有相同值的多個(gè)元素
查找時(shí)間是
O(log(n))和不是O(1)地圖中發(fā)生的事情并不神奇，它讓我們可以在更短的時(shí)間內(nèi)訪問(wèn)它。有一個(gè)散列過(guò)程在后臺(tái)進(jìn)行，
unordered_map這O(1)也需要時(shí)間。所以，大 O 隱藏了一個(gè)很大的常數(shù)時(shí)間因素。標(biāo)準(zhǔn)map為您提供O(logn)查找，時(shí)間復(fù)雜度與數(shù)組中的二進(jìn)制搜索相同。
你得到的搜索的平均時(shí)間復(fù)雜度是差不多的。在 C++ 中使用標(biāo)準(zhǔn)映射的主要問(wèn)題是它無(wú)法保存具有相同值的多個(gè)元素。使用 map 可能獲得的一個(gè)優(yōu)勢(shì)是刪除和插入時(shí)間將是O(logn).
因此，如果您知道您將要處理的數(shù)據(jù)集沒(méi)有重復(fù)元素和/或?qū)?strong>頻繁添加/刪除元素，那么在這種情況下您肯定可以將 map 視為更好的選擇
慕容708150
TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超4個(gè)贊
由于確切的運(yùn)行時(shí)間將取決于密鑰的長(zhǎng)度和類型、它們的分布、它們的數(shù)量，因此建議為您的特定應(yīng)用程序進(jìn)行基準(zhǔn)測(cè)試。
添加回答
舉報(bào)
0/150
提交
取消