На собеседованиях по С++ задают много вопросов про контейнеры STL. И самый безобидный из них, как думал, std::vector. Но вот и по нему попался интересный вопрос.

Представим, что стратегия управления внутренним буфером контейнера std::vector (в реальности, она иная) такова: изначально размер буфера равен нулю, и он будет увеличивается вдвое каждый раз, когда в нем уже нет места под следующий элемент.

Вопрос: оценить вычислительную сложность последвательного добавления в контейнер k элементов (как уже говорилось, начальная длина контейнера нулевая). Элементы добавляются в конец.

Как я полагаю, в среднем ожидается, что отвечать стоит практически сразу.

На всякий случай: мой ответ будет завтра.

А сейчас мини эксперимент с реальным std::vector (компилятор, и сообразно STL — Sun C++ 5.9 SunOS_sparc) для выяснения реальной стратегии роста буфера в векторе:

#include <vector>
#include <iostream>
#include <iomanip>
#include <cstdlib>

int main() {
  int last = -1;
  std::vector<int> a;
  std::cout << std::setw(12) << "Capacity" << " " 
            << std::setw(12) << "Size"
            << std::setw(12) << "Ratio" << std::endl
            << std::setw(12) << std::setfill('-') << "-" << " " 
            << std::setw(12) << "-" << " "
            << std::setw(12) << "-" << std::endl;

  std::cout << std::setfill(' ') << std::fixed;
  while (1) {
    if (a.capacity() != last) {
      last = a.capacity();
      std::cout << std::setw(12) << a.capacity() << " "
                << std::setw(12) << a.size() << " "
                << std::setw(12) << std::setprecision(6)
                << (float)a.capacity() / a.size() << std::endl;
    }
    a.push_back(std::rand());
  }
  return 0;
}

А вот и результат:

    Capacity         Size       Ratio
------------ ------------ ------------
           0            0          NaN
          32            1    32.000000
          64           33     1.939394
         103           65     1.584615
         166          104     1.596154
         268          167     1.604790
         433          269     1.609665
         700          434     1.612903
        1132          701     1.614836
        1831         1133     1.616064
        2962         1832     1.616812
        4792         2963     1.617280
        7753         4793     1.617567
       12544         7754     1.617746
       20296        12545     1.617856
       32838        20297     1.617875
       53131        32839     1.617924
       85965        53132     1.617952
      139091        85966     1.617977
      225049       139092     1.617987
      364129       225050     1.617992
      589160       364130     1.617994
      953260       589161     1.617996
     1542374       953261     1.617998
     2495561      1542375     1.617999
     4037817      2495562     1.617999
     6533187      4037818     1.617999
    10570696      6533188     1.618000
    17103386     10570697     1.618000
    27673278     17103387     1.618000
    44775363     27673279     1.618000
    72446537     44775364     1.618000
   117218496     72446538     1.618000
   189659526    117218497     1.618000
   306869113    189659527     1.618000

Выходит, что для моей STL - это какой-то магический коэффициент 1.618.

Update: В комментариях подсказали хорошую ссылку на тему стратегии управления размером вектора.

Update 2: Лично мой ответ на тему вычислительной сложности последовательного добавления элементов в вектор, если вектор будет удваивать размер буфера при переполнении.

Так как мы добавляем k элементов, то это как минимум O(k). А так как по условию вектор удваивает буфер каждый раз, когда нет места, то произойдет log2(k) раз (так как по условию элементы поступают последовательно).

Получаем в этоге: O(k*log2(k)).

Update 3: В комментариях меня поправили: O(k + log2(k)) или просто O(k).