在使用 STL 的 C++ 中，这两个操作中的哪一个需要更少的 CPU 时间来对大的不同数字进行排序：
- 将元素推入一个集合
- 将元素存储在向量中并调用 sort() 函数？
问问题
102 次
1 回答
6
如果是一次性操作，我会使用 astd::vector后跟 a std::sort。
就涉及渐近复杂度而言，这两种解决方案应该是等价的：插入一个集合是 O(log(n))，而你对 N 个元素执行此操作，所以它是 O(N log(N))（证明）。
另一方面，插入向量（前提是你事先知道大小）是 O(N)，排序是 O(N log(N))，所以全局是 O(N log(N))。
但是：向量需要一次性分配（或者，如果您不知道最终大小，它应该在典型实现中达到 O(log(N)) 重新分配的最终大小）；另一方面，如果将集合实现为 RB 树，则需要为每个节点进行分配，这意味着您必须调用分配器 N 次 - 在 POD 容器中，分配器调用可能会是其中之一瓶颈。此外，树通常具有较少的缓存局部性并使用更多内存，因此所有这些开销可能会损害性能。
此外，big-O 表示法显示了函数时间依赖性，但隐藏了乘法常数；不要相信我的话，但我几乎可以肯定 N*set 插入最终会花费超过一次排序，因为每个元素都要进行所有额外的簿记（树插入通常需要一些努力恢复 RB 树属性）。
另一方面，如果你必须保持你的数据结构排序（随着新数据的到来），那么集合通常是正确的解决方案。
但是，与往常一样，当有疑问时。
于 2013-02-28T02:47:23.150 回答