Вопрос:
Какова сложность для операций alloc (realloc)/new для кода ниже, для огромных значений N.
Насколько я понял push_back выделяет память:
size = cst * old_size;
cst = 2; // для gcc
Таким образом, у нас есть O (1) внутри цикла k и ~ O (N) внутри цикла i. В итоге я имею O (N), я прав?
std::vector<int> data; for (int i = 0; i < N; ++i) { for (int k = 0; k < 2 * N; ++k) data.push_back(k); for (int k = 0; k < N; ++k) data.pop_back(); } Лучший ответ:
Когда происходит перераспределение, он удваивает выделенный размер вектора, поэтому (для произвольно больших значений N) в данном примере это будет происходить постоянными * log_2 (N) раз.
Да, сложность вызова push_back амортизируется O (1), потому что перераспределение не займет больше времени, если вектор большой (лучше: время не зависит от размера), но перераспределение все равно будет происходить постоянным * log_2 (N) раз внутри цикла (где константа! = 0).
Наконец, сложность перераспределения в примере k-цикла составляет O (log2 (N)) и (отредактировано) для основного цикла, это O (log2 (N ^ 2)) = O (2 * log2 (N)) = O (log2 (N)).
Ответ №1
vector :: push_back – это не O (1), а амортизированный O (1), что требуется стандартом C++. См постоянное амортизированное время
Ответ №2
Как правило, если оставить в стороне код, который вызывает перераспределения, долгосрочное поведение push_back и последующие перераспределения больше похожи на O (log (N)), хотя стандарт C++ этого не требует.
