Блог

Я изучаю структуры данных из «Основы структур данных на C» Сахни. В теме «Циклическая очередь с использованием динамического массива» автор упомянул ниже пункт,

Пусть емкость будет начальной емкостью циклической очереди, мы должны сначала увеличить размер массива с помощью realloc, это скопирует максимум элементов емкости в новый массив. Чтобы получить правильную конфигурацию циклической очереди, мы должны переместить элементы в правом сегменте (т.Е. Элементы A и B) в правый конец массива (см. диаграмму 3.7.d). Удвоение массива и сдвиг вправо вместе копируют не более 2 * элементов емкости -2.

Я понимаю, что удвоение массива копирует большинство элементов емкости. Но как удвоение массива и перемещение вправо копируют не более 2 * элементов емкости -2??

Давайте попробуем обосновать наихудший сценарий:

Для очереди с capacity = N N-1 elements в очереди присутствует максимум.

Итак, когда мы удваиваем размер очереди, нам нужно скопировать все эти N-1 элементы в новую очередь, и при максимуме может быть N-1 сдвигов (для элементов).

Итак, всего 2 * (N-1) = 2 * N — 2