Пространственная сложность вектора push_back

Question

У меня есть код, который сначала создает вектор (вектор B).Затем мой код перебирает другой вектор (вектор A) в программе и добавляет этот индекс в конец вектора B.

Я думаю, что, поскольку мы переходим через n элементов, сложность времени будет хужеO (n ^ 2), поскольку нам может потребоваться создать совершенно новый массив, если вектор b становится слишком большим.среднее время O (n), поскольку откат обычно постоянен.

Теперь для сложности пространства, поскольку мы уже создаем пространство для хранения n элементов, это будет O (N).Однако, если наш вектор слишком велик, нам может понадобиться создать совершенно новый размер O (N).Таким образом, наше пространство будет O (2n), которое является просто O (n), или будет O (n + m) (m - размер нового массива).

Спасибо!

Answer 1

Относительно сложности времени:

Наихудший случай одиночного обратного хода является линейным (если только память не зарезервирована заранее, в этом случае наихудший случай постоянен, если размер не превышает зарезервированный размер),Средний регистр является постоянным.

И наихудший, и средний регистр N общего обратного хода являются линейными, независимо от того, зарезервирована ли память.

---

Таким образом, наше пространство будет равно O(2n), который является просто O (n) или будет O (n + m) (m является размером нового массива).

Это не имеет значения асимптотически.Новый размер является постоянным кратным (c) старого размера, поэтому O(n + m) -> O(n + (n * c)) -> O ((c + 1) * n) -> O(n).Таким образом, сложность одинакова в любом случае.