Изменение размера динамического массива с размером чисел Фибоначчи

Question

У нас есть динамический массив с размером чисел Фибоначчи.Предположим, что F (k) - это текущий размер массива (F (k) - это k-е число рядов Фибоначчи).У нас есть два правила: 1) Если после вставки элемента в массив количество элементов массива равно F (k-1), мы создаем новый массив размером F (k + 1) и копируем предыдущие элементыв новый массив.2) Если после удаления элемента из массива количество элементов массива равно F (k-3), мы создаем новый массив размером F (k-1) и копируем предыдущие элементы в новый массив.

Сначала массив пуст и имеет размер 2. Мы хотим показать, что для каждой последовательности действий (вставка или удаление) каждое действие имеет амортизированную временную сложность O (1).

Для решения этой проблемы я понимаю, что между двумя действиями по увеличению массива выполняются как минимум действия F (k-1) -F (k-2), а копирование элементов занимает время O (F (k-1)),Кроме того, между двумя действиями по сокращению массива выполняются как минимум действия F (k-2) + F (k-3), а копирование элементов занимает время O (F (k-3)).Можете ли вы помочь мне решить эту проблему?

Answer 1

Амортизированный анализ суммируется каждый раз при копировании, который равен T(n) = F(1) + F(2) + ... + F(k), если мы предположим n = F(k).Мы знаем, что T(n) = F(k+2) -1 1.

Как T(n) = F(k+2) - 1 = F(k+1) + F(k) - 1 = 2F(k) + F(k-1) - 1= 2*n + F(k-1) - 1< 3n - 1, следовательно, амотизированная стоимость равна T(n)/n < 3, а в амортизированном смысле это означает T(n) = Theta(1).