c++ - マルチセットへの挿入の実行時間

Question

マルチ セットへの挿入の全体的な実行時間はどのくらいですか。たとえば、10 億を超える要素をマルチ セットに挿入するとします。これにより、並べ替えられた順序が維持されます。最悪の場合の実行時間は?

Answer 1

http://www.sgi.com/tech/stl/MultipleAssociativeContainer.htmlによると、単一の要素を挿入する場合の挿入の複雑さは O(log n) です。長さ N のシーケンスを挿入する場合、O(N log n) です。

漸近的な複雑さではなく、本当に時間が必要な場合は、さまざまな値 (たとえば、1000、10,000) の時間を計り、そこから比例定数を計算できます。実際の方程式は t = A n log n + C になります。

しかし、もちろん、次に別のハードウェアで実行するときは、A と C の値が変わります。