Необходимо добавить N элементов в начало пустого std::vector. Какая - Ответ на вопрос №1108883

Вопрос

Необходимо добавить N элементов в начало пустого std::vector. Какая будет асимптотическая сложность у данной операции?

• Добавление одного элемента в std::vector выполняется очень быстро, за постоянное время, то есть за О(1). Поскольку нужно добавить N элементов, то получаем асимптотическую сложность O(1*N), что равносильно O(N), то есть в результате имеем линейное время
• Добавление одного элемента в начало std::vector имеет сложность O(n), т.к. каждый раз придётся сдвигать все остальные элементы вправо. Следовательно, добавление N элементов в начало будет иметь сложность O(N^2), т.е. получаем квадратичное время
• std::vector является аналогом обычного массива, а значит память под него выделяется сразу и гарантировать добавление всех N элементов нельзя. Однако, пока есть свободная память, добавление элементов будет происходить за постоянное время, то есть сложность получаем О(1)

Ответ