c++ - 插入多组的运行时间

Question

插入多集合的整体运行时间是多少，假设我要遍历十亿个元素并插入多集合，它保持有序的顺序。我最坏的情况下运行时间是多少？

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 的值会改变。