std::map を std::string キーで使用する場合と int キーで使用する場合のコストはどちらですか? 質問する

漸近的パフォーマンスのアルゴリズムを分析するには、実行する必要がある操作と、それらが方程式に追加するコストを検討します。そのためには、まず実行される操作が何であるかを把握し、次にそのコストを評価する必要があります。

バランスのとれた二分木（マップはそれです）でキーを検索するには、O( log N )複雑な操作が必要です。これらの操作のそれぞれは、一致するキーを比較し、キーが一致しない場合は適切なポインタ（子）をたどることを意味します。つまり、全体的なコストは、log Nこれら2つの操作のコストに比例します。ポインタをたどる操作は一定時間でO(1)、キーの比較はキーに依存します。整数キーの場合、比較は高速ですO(1)。2つの文字列を比較するのは別の話で、関係する文字列のサイズに比例した時間がかかりますO(L)（ここでは、意図的Lに文字列の長さより一般的な の代わりに パラメータを使用しますN。

すべてのコストを合計すると、整数をキーとして使用して合計コストが となり、O( log N )*( O(1) + O(1) )これは と等しくなりますO( log N )。(は、表記法O(1)によって暗黙的に隠されている定数の中に隠されますO。

文字列をキーとして使用する場合、総コストは、O( log N )*( O(L) + O(1) )定数時間の操作がよりコストのかかる線形操作によって隠されO(L)、 に変換できるO( L * log N )場所です。つまり、文字列をキーとするマップ内の要素を検索するコストは、マップに格納されている要素の数の対数と、キーとして使用される文字列の平均長の積に比例します。

ビッグ O 表記法は、問題のサイズが大きくなったときにアルゴリズムがどのように動作するかを判断するための分析ツールとして使用するのが最も適していますが、その下には生のパフォーマンスにとって重要な多くの事実が隠されていることに注意してください。

最も単純な例として、キーを汎用文字列から 1000 文字の配列に変更すると、表記から省略された定数内にそのコストを隠すことができます。1000 文字の配列を比較することは、かなりの時間がかかる定数操作です。漸近表記法では、O( log N )整数の場合と同様に、これは単なる操作になります。

同じことが他の多くの隠れたコストでも起こります。たとえば、要素の作成コストは、問題のパラメータに依存しないため、通常は一定時間の操作と見なされます (各割り当てでメモリ ブロックを見つけるコストはデータ セットに依存せず、アルゴリズム分析の範囲外であるメモリの断片化に依存します。2 つのプロセスが同じメモリ ブロックを返そうとしないことを保証するために malloc 内でロックを取得するコストは、プロセッサの数、プロセス、およびそれらが実行するメモリ要求の量に依存するロックの競合に依存します。これもアルゴリズム分析の範囲外です)。big-O 表記法でコストを読み取るときは、それが実際に何を意味するかを意識する必要があります。