RED*_*AIR 5 c++ performance complexity-theory stl
我google了很长一段时间才找到一个比较,显示插入/推送擦除/弹出等所有STL-Containers的复杂性差异.我没有找到任何.我的所有STL书籍也没有.任何提示？
我当然知道一些经验法则.但是定义在哪里？
尝试用
http://www.sgi.com/tech/stl/complexity.html
http://www.sgi.com/tech/stl/table_of_contents.html
来自complexity.html：
从根本上说，很难为真实的计算机硬件而不是抽象的机器模型精确定义渐近算法复杂性的概念。因此，我们遵循以下准则：
- 为了使算法 A 的运行时间为 O(f(n))，必须有一个相应的算法 A'，该算法在具有任意长指针和 size_t 类型的机器上是正确的，使得 A 和 A' 执行本质上相同的操作序列在实际硬件上。（在简单的情况下，A 和 A' 将是相同的。在其他情况下，A 可能已通过地址有界的知识进行了简化。）对于足够大的大小 n 的输入，A' 必须最多花费 Cf(n) 时间，其中 C 是一个常数，与 n 和地址大小无关。（假定指针、size_t 和 ptrdiff_t 操作花费常数时间，与其大小无关。）
- 所有容器或迭代器复杂性规范均指摊余复杂性。单个操作可能需要比指定的时间更长的时间。但是，对同一容器或迭代器进行的任何足够长的操作序列最多将花费与指定操作成本的相应总和一样长的时间。
- 算法指定最坏情况或平均情况性能，并确定哪种情况。除非另有说明，平均值假设容器元素是从具有比容器大小更多可能值的有限类型中选择的，并且容器元素是独立均匀分布的。
- 操作 f 的复杂性规范假定 f 调用的操作最多需要指定的运行时间。但是，如果调用的操作不超过预期情况下指定的对数因子，则算法通常仍然适用。
如果操作比当前 STL 中函数 F 假设的操作更昂贵，那么 F 最多将按增加的成本成比例减慢。任何无法满足此属性的未来操作都将使其明确。
为了使其精确，假设 F 被指定为使用时间 f(m) 来输入大小为 m 的输入。F 使用操作 Gk，在输入大小 n 上指定运行时间 gk(n)。如果在每个 Gk 比预期慢至多一个因子 h(n) 的情况下使用 F，则 F 最多减慢一个因子 h(m)。这是成立的，因为当前的算法都没有将运算 Gk 应用于明显大于 m 的输入。