動態數組的時間複雜度和增長策略

Question

我在閱讀Herb Sutter的More Exceptional C++關於實現字符串時選擇的增長策略。他列出以下內容：

1）確切增長。在此策略中，新緩衝區的尺寸與當前操作所需的尺寸完全相同

優點：無浪費空間。

缺點：性能不佳。這種策略需要每個字符的O（N）分配和平均O（N）複製操作，但在最壞的情況下需要一個高的常數因子......

2）固定增量增長。新的緩衝區應該是比當前緩衝區大的固定量

優點：浪費的空間很小。緩衝區中未使用的空間量由增量大小限定，並且不隨字符串的長度而變化。

缺點：表現中等。該策略需要O（N）分配和每個字符的平均O（N）複製操作。也就是說，分配數量和給定字符被複制的平均次數都隨字符串的長度而線性變化。 但是，常量因子的控制權在String實施者手中。

注：字符由1個

問題1添加到字符串1：如何常數因子在兩個控制？我不知道這裏的草本點

問題2：固定增量如何定義爲O（N），將不會取決於固定大小的使用情況，如果說它的100個字符，在第一次調整大小後，接下來的99次插入是O（1），那麼爲什麼要考慮O（N）呢？

Answer 1

1. 字符串實施者就可以選擇˚F固定大小的增量有多大。所以他控制了2）中的常數因子，而不是1）。請注意，在1）中沒有控制常數因子的主張。

2. 每個字符的成本爲O（N/f）。我相信Herb的含義是f是由實現固定的，因此它本質上是一個大的符號（即它被丟棄）中的一個常數因子。然而，大的常數因子越小，因此性能越好（以更多的浪費空間爲代價）。因此，實施者在選擇f時必須權衡這兩個因素。