Доказательство сложности времени по рекурсивному алгоритму Фибоначчи

Question

Я пытаюсь понять доказательство по индукции в моем учебнике по алгоритмам.Вот автор доказывает с помощью индукции, что T (n) всегда будет больше 2 ^ (n / 2) (это для вычисления n-го числа Фибоначчи с использованием рекурсивного алгоритма):

ЧтоЯ не понимаю, это самый последний шаг, где он манипулирует уравнением.Как он идет от:

> 2^(n-1)/2 + 2^(n-2)/2 +1

до

> 2^(n-2)/2 + 2^(n-2)/2 +1

Он просто случайным образом меняет 2^(n-1)/2 на 2^(n-2)/2.Это ошибка?

Спасибо.

Answer 1

Это преднамеренно, если вы посмотрите внимательно, это неравенство, и он использует его, завершите шаг индукции.

Обратите внимание на опечатку, она должна сказать: «Мы должны показать, что T (n)> 2 ^ (n/ 2) "а не <. </p>

Answer 2

Я считаю, что конкретный шаг исходит из предположения, что:

T(n-1) > T(n-2)

Следовательно, мы можем сформировать алгебраическое неравенство:

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2) + 1

Мы можем отбросить + 1 с правой стороны (потому что неравенство все еще будет сохраняться для всего, что вычтено со стороны МЕНЬШЕГО):

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2)

Отсюда подставим нашу T (m) = 2 ^ (m / 2) (для всего, что меньше n и> 2, которые оба n-1 и n-2 соответствуют):

2^(n-1)/2 + 2^(n-2)/2 + 1 > 2^(n-2)/2 + 2^(n-2)/2

Это дает вам этот конкретный шаг. Это сделано осознанно, как было сказано выше, на плакате, чтобы добраться до 2 ^ (n / 2).