map - map.find（）時間計算量

Question

地図を持っている場合：

map myMap<string,vector<int>>

キーを見つけてから、ベクトルを反復処理して特定のintを見つけることは、最良、平均、および最悪の場合の時間計算量でしょうか。

map.find（）メソッドがO（log n）であることは知っていますが、ベクトル内でintを検索する必要があるという事実は、時間計算量を変更しますか？

ありがとう

Answer 1

これが C++ であると述べていただければ助かります。std::map は通常、バイナリ ツリーとして実装されるため、検索操作の O(log(n)) はそこから発生します。

O(log(n) + m) になります。ここで、n はマップのサイズ、m は (各) ベクトルのサイズです。ルックアップを 1 回だけ行ってから、キーに対応するベクトル全体を反復処理すると仮定しています。

log(n) はゆっくりと大きくなるため、ベクトルが非常に小さい場合を除き、log(n) は < m である必要があるため、アルゴリズムは O(m) である必要があります。