如何計算std::vector的push_back方法插入一個對象的平均時間（要寫出計算式）？

01-15

如題，面試時候遇到的一個問題。

假設現在 capacity() == size() == N ，那麼

後 1/2 N 個元素拷貝了1次，是 push_back() 直接拷貝的。

前 1/2 N 個元素在上次擴容的時候多拷貝了 1 次，

前 1/4 N 個元素在上上次擴容的時候又多拷貝了 1 次，以此類推。

所以平均每個元素拷貝了 1 + 1/2 + 1/4 + ... = 2 次，這是下限。

如果這時再 push_back()，又會擴容 size = N+1 = capacity/2 + 1，這次擴容會拷貝 N 個元素，那麼平均每個元素拷貝了 2+1 = 3 次，這是上限。

這是演算法導論分攤分析那一章的習題。

先列演算法

function push_back( E el ) if (capacity == 0) // initialize allocate vector of length 1 else if (capacity == size) //reallocation allocate vector of length 2 * size copy everything from old vector free old vector

add el to vector // insert end

然後列算式每個push_back的時間是a(push_back)

a(push_back) = t(insert) + 2 * delta(size) - delta(capacity)

//註：delta(size)是(插之後的size)-(插之前的size)

//delta(capacity)一個道理

然後算a到底是多少，分兩種情況：

1是直接插，插完就跑

2是插不進去，需要更大的vector

if push_back doesn"t cause reallocation t (insert) = 1 delta(size) = 1 delta(capacity) =0 a(push_back) = 3 if push_back cause reallocation t(insert)= n // n-1個copy + 1個insert delta (size) = 1 delta(capacity) = (n-1) a(push_back)= n + 2*1 - (n - 1) = 3

最後我們發現a(push_back) = 3

a(push_back) = 3 = O(1)

面試官問你2*delta(size) - delta(capacity)是怎麼來的。你就告訴他是difference in potential function。以他這個智商很難跟他解釋清楚…

//最好別這麼說，你自己先把potential function搞明白再去面試才好

這個算的是push_back的amortized time跟average差不多一個意思。都是把total分攤到個體上的。stack overflow上有討論amortized和average的區別的。average在push_back這個operation上沒什麼意義

http://stackoverflow.com/questions/7333376/difference-between-average-case-and-amortized-analysis

需要這麼幾個參數：vector的初始空間a，總共插入個數b，vector空間增長策略為f(x)。

比如b&<=a那就是b

f(a)&

以此類推。

求出的是拷貝次數，算時間的話還需要知道拷貝一次花的時間。另外這裡還省略了vector申請空間花費的時間。

vector增長不一定是翻倍。

不過這個等式再長，因為f(x)和a都是確定的，已知的，所以a,f(a),f(f(a))…都是常數。

因此對變數b求導就得到了1，即時間複雜度O(1)。

這樣計算應該是沒問題的，有錯請指出。

這喚作「攤還分析」。可參見算導第十七章。

push_back每次擴容需要O(n)的時間複雜度，而如果最終的數據規模是N的話，累計需要lgN次擴容，每次在不需要擴容的情況下進行插入則需要O(1)的複雜度。

平均開銷就是把進行N次插入需要的總開銷加起來，平攤到每一次插入上。

水平有限，爪機碼字，不知道對不對

假設該機器上vector默認分配的初始空間是N，N大於等於1，並假設其擴容的策略為每次倍增。假設非擴容情況發生時所耗時間為t1，擴容發生時所耗時間為t2，即認為不論擴容多少倍，每次擴容時所耗費的時間都是一樣的為t2。

為簡化計算，假設最終插入的元素個數恰好是N的倍數

插入第1至第N個元素總時間：t2 + t1*(N-1)

此後再插入時會擴容為2N

插入第N+1至第2N個元素總時間 t2 + t1*(N-1)

此後再插入時會擴容為4N

插入第2N+1至第4N個元素總時間t2 + t1*(2N-1)

依次類推

他們每個元素平均所花時間為

(t2 + t1*(N-1) + t2 + t1*(N-1) + t2 + t1*(2N-1) + …) /

(N + N + 2N + …)

假設最終剛好發生了k次擴容，且最後容器剛好被填滿

則上式可化為

(k+1)t2 + t1*(N - (k + 1) + N(1 - 2^k) / (1 - 2)) /

(N + N(1 - 2^k) / (1 - 2))

令k趨於無窮大，求得上式極限為t1

即平均插入每個元素的開銷就是t1，完全沒有了擴容的開銷。

假設內存空間是這樣變化的 for 不斷push_back：

element_size = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ... memory_size = 2 2 2 4 4 8 8 8 8 16 16 16 16 16 ...

顯然當內存空間兩倍擴充時需要進行複製。

設 push_back n次，在n次中，要擴充多少次呢？顯然的，以2為底，[log(n-1)]。// 我湊的，未必完全正確（逃

於是，總時間是插入n個元素的時間加上擴充時複製的時間，即：T = n + sum{ 2^(i - 1) for i from 2 to [log(n-1)] }。// 具體的結果不想查書了咳……

所以平均時間t = T / n ≈ O(1)，即push_back的平均時間為O(1)。

既然是平均時間，可假設push_back() N個元素

C++標準並沒有規定如何管理內存，只有介面和性能的規定，而具體實現上大多都是採用每次申請量倍增的方式（需要大神增補），對N個元素來講需要分配內存logN次

複製或移動原有元素需要： $2^{0} imesleft(frac{N}{2^{0} } - frac{N}{2^{1} } ight) + 2^{1} imes left( frac{N}{2^{1} } - frac{N}{2^{2} } ight) + 2^{2} imes left( frac{N}{2^{2}} - frac{N}{2^{3}} ight) + ... + 2^{logN} imes 1 = Oleft( N ight)$

即： $sum_{i= 0}^{logN}{2^{i} imes left( frac{N}{2^{i} } - frac{N}{2^{i+1} } ight) }$

每次分配和插入均可在常數時間內完成

所以：平均插入一個元素需要（O(logN) + O(N)）/ N = O(1)

也就是常數時間

std vector 的push_back 分為兩種情況，第一種容量大於已使用容量，速度大約就是在指定內存創建一個對象的速度，第二種容量不夠了，要重新分配內存，就要新分配一塊更大的內存，然後把原來的東西都copy過去，然後再push_back，具體的平均耗時要看內部實現的內存分配演算法。

--------------------------

還要考慮原來對象析構函數調用的時間

至於具體算式，就是高中數學了╮(￣▽￣"")╭

用Amortized Analysis，三種方法：Aggregate Analysis，Accounting Method，Potential Method。基本思想都是考慮一個average cost： $C(n)=frac{1}{n}*( ext{worst-case total cost of a sequence of n operations})$

CLRS都有講，再補充一個OCW 6.046J的handout，後面就有講分別用三種方法做resizable table amortized analysis。https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec11.pdf