0

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

4

1 回答 1

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

于 2014-01-26T02:53:29.250 回答