Сложность для реализации динамического массива стека

Question

В типичной реализации динамического массива мы удваиваем стек, когда нет места для нового элемента.В этом случае удвоение среднего времени для операции push равно O (n).

В чем сложность push, если вместо удвоения мы увеличили размер стека на (n + k)?

Мой подход заключается в следующем

Предполагая, что стек пуст, и k = 10, мы увеличиваем стек до 10 элементов.После 10 элементов мы получаем 20 элементов и т. Д.

Среднее время копирования элементов составляет 10 + 20 + 30 + ...

Таким образом, среднее время для толчка должно быть впорядок O (n)?

Является ли мой подход правильным?

Answer 1

Ваши вычисления неверны. Существует причина, по которой типичная реализация динамического массива удваивает его размер (или, в более общем случае, увеличивает его размер на x процентов).

Если вы увеличите размер с 1 до n = 2 ⁱ , общее количество копируемых элементов составит 1 + 2 + 4 + 8 + 16 + ... + 2 ⁱ . Если вы суммируете это, оно будет меньше 2 ^{i + 1} , поэтому общая сложность времени составляет O (n), а сложность амортизированного времени одной вставки равна O (1). Если n не является степенью двойки, вычисление будет немного более сложным, но результат будет таким же.

С другой стороны, если вы увеличите размер на k с 0 до n = i * k, общее количество копируемых вами элементов будет равно k + 2k + 3k + ... + ik. Если вы суммируете это, оно будет (ik + k) * (ik / k) / 2 = O (n ² ). А амортизируемая сложность одной вставки будет O (n).

Из-за этого ваше решение намного хуже, чем удвоение размера.

Answer 2

В зависимости от того, как вы увеличите объем хранилища, а k достаточно мало, для всех случаев это может быть O (1) или что-то еще.

Под «как», я имею в виду, в управляемых языках одинсоздаст новый массив размером n + k, а затем скопирует старый массив (размера n) в новый и, наконец, заменит ссылку старого массива на новый.Это будет: O (1) (создание массива, это предположение) + O (n) (копирование данных) + O (1) (изменение ссылки).Мы игнорируем выполнение сборщика мусора, потому что оно очень зависит от реализации.В неуправляемых языках можно использовать что-то похожее на realloc, чтобы старые элементы сохранялись без необходимости копировать, поскольку новое хранилище занимает ту же область памяти, только расширенную до количества требуемых элементов.В этом случае это O (1) для всех случаев.Обратите внимание, что иногда расширение хранилища до количества требуемых элементов невозможно из-за фрагментации памяти, поэтому вместо этого используется подход, подобный управляемым языкам (но неявно реализуемый реализацией realloc).В этом случае сложность та же, что и в управляемых языках: O (n).

Это ответ с практической точки зрения, я надеюсь, что вы можете найти ответ с аналитической точки зрения, используя ответ выше.Удачи.