c++ - 动态数组的时间复杂度和增长策略

Question

我正在阅读 Herb Sutter 的 More Exceptional C++ 中关于实现字符串时要选择的增长策略。他列出了以下内容:

1) 精确增长。在此策略中，新缓冲区的大小正好与当前操作所需的一样大

优点:不浪费空间。

缺点:性能较差。该策略需要 O(N) 次分配和每个字符的平均 O(N) 次复制操作，但在最坏的情况下具有高常数因子...

2) 固定增量增长。新缓冲区应该比当前缓冲区大固定数量

优点:空间浪费小。缓冲区中未使用的空间量受增量大小限制，不随字符串长度变化。

缺点:性能一般。该策略需要 O(N) 次分配和平均每个字符的 O(N) 次复制操作。也就是说，分配的次数和给定字符被复制的平均次数都随字符串的长度线性变化。但是，常数因子的控制权在 String 实现者手中。

注意:字符是1个1个加到字符串中

问题1:两者的常数因子如何控制？我不明白 Herb 的意思

问题 2:固定增量如何为 O(N)，不取决于使用的固定大小，如果说它的 100 个字符，在第一次调整大小后，下一个 99插入将是 O(1)，那么为什么要考虑 O(N)？

Answer 1

1. 字符串实现者可以选择固定大小增量 f 的大小。所以他可以控制 2) 中的常数因子，但不能控制 1) 中的常数因子。请注意，没有声称可以控制 1 中的常数因子)。

2. 每个字符的成本为 O(N/f)。我相信 Herb 的意思是 f 由实现固定，因此本质上是大 oh 表示法中的常数因子(即它被删除)。然而，f 越大，big-oh 常数因子越小，因此性能越好(以浪费更多空间为代价)。因此，实现者在选择 f 时必须权衡这两个因素。