用stl向量計算複雜度？

Question

我試圖計算一些算法的複雜性，但我不知道如何確定向量的操作的複雜性。例如，push_back（）的複雜性是什麼？

在C++參考我發現 「常數（攤銷時間，重新分配可發生）。 如果重新分配發生，重新分配是本身向上在整個大小爲線性」。

這是什麼意思？複雜度O（n）的操作是？ （n是矢量長度）。

謝謝。

Answer 1

複雜性爲向量是：

• 的push_back：O（1）。
  攤銷代表「圓整」，因爲這種複雜性取決於可能的重新分配。

你必須重新分配時，矢量的大小大於：

size_type capacity() const; 

返回：元素的總數的載體，而不需要 再分配舉行。
說明：重新分配會使所有引用 序列中的元素的引用，指針和迭代器全部爲 無效。確保在調用reserve（）之後發生的 插入期間不發生重新分配，直到插入的 時間使得向量的大小大於最近調用reserve（）時指定的大小 。