Амортизированный анализ динамического стека

Question

Ниже приведен фрагмент текста, касающийся амортизированного анализа динамического стека.

Если мы реализуем стек как динамический массив.Предположим, что вставка в массив стоит 1, а извлечение элемента из массива - 1, а стоимость изменения размера массива - это число перемещенных элементов.(Скажем, что все другие операции, такие как увеличение или уменьшение "top", бесплатны).Если мы решим удвоить размер массива при изменении размера.Теперь в любой последовательности «n» операций общая стоимость изменения размера составляет 1 + 2 + 4 + 8 + ... + (2 ^ i) (то есть от 2 до степени i) для некоторых 2 ^ i

MyВопрос в том, как автор пришел к выводу, что сумма не более 2n -1.Просьба помочь с примером или доказательством.

Спасибо!

Answer 1

Вы пытаетесь найти сумму:

1 + 2 + 4 + ... + 2^i

Мы можем видеть, что это то же самое, что и:

2^0 + 2^1 + ... + 2^i

Давайте обозначим эту сумму как S(i).Глядя на первые несколько значений, вы можете увидеть шаблон:

S(0) = 2^0       = 1         = 1
S(1) = 2^0 + 2^1 = 1 + 2     = 3
S(2) = ...       = 1 + 2 + 4 = 7
S(3) = ...       = ...       = 15
S(4) = ...       = ...       = 31

Мы можем видеть, что все они кажутся на единицу меньше, чем степени 2. Точнее: S(i) кажется равно 2^(i+1) - 1.Мы можем доказать это по индукции:

Базовый случай:

S(0) = 2^(0+1) - 1

Мы можем легко увидеть, что приведенное выше утверждение верно.

Индуктивный шаг:

Мы знаем, что:

S(i) = S(i-1) + 2^(i)

, что очевидно из определения суммы.Кроме того, если S(i-1) = 2^(i) - 1, то:

S(i) = (2^(i) - 1) + 2^(i)
       = 2*(2^(i)) - 1
       = 2^(i+1) - 1

и, следовательно, мы доказали, что для всех целых чисел i >= 0, что S(i) = 2^(i+1) - 1

Теперь, возвращаясь к вашему первоначальному вопросу, мыданы, что 2^i < n.Тогда мы имеем:

S(i) = 2^(i+1) - 1
     = 2*(2^i) - 1
     < 2*n - 1

и, следовательно, мы доказали, что S (i) <2 * n + 1. </p>

Answer 2

это сумма геометрической прогрессии :

SUM(q^k for k = 0 to n) = (q ^n+1 -1)/ (q-1)

тогда в вашем случае у вас есть:

SUM(2^k for k = 0 to i) = 2^(i+1) - 1 

Тогда с 2 ^ i

2^(i+1) < 2n 

и

SUM(2^k for k = 0 to i) = 2^(i+1) - 1 < 2n - 1