Нахождение нижней границы для алгоритма с использованием метода предположения / проверки

Question

Я пытаюсь выработать несколько предположений о сложности алгоритма, но каждый раз, когда я пытаюсь угадать, используя экспоненциальное время, мой метод угадывания / проверки кажется неудачным.Я уверен, что я делаю что-то нелепо неправильно, я просто не могу найти это сам.

Например, если у меня есть повторение T (n) = 2T (n-1) + T (n-2) + 1 , , где T (1) = 0 и T (2) = 1 .

Итерируя его несколько раз и подключая кюветы n = 3,4,5,6,7,8 ... мы можем наблюдать, что для любого значения n> = 8 T (n)>2 ^ n, поэтому 2 ^ n не является верхней границей.

Итак, зная эту информацию, я пытаюсь угадать, что T (n) = O (2 ^ n)

T (n) <= C (2 ^ n) </p>

2T (n-1) + T (n-2) +1 <= C (2 ^ n) </p>

2C (2 ^ (n-1)) + C (2 ^ (n-2)) + 1 <= c (2 ^ n) </p>

C (2 ^ n) -C (2 ^ n + 2 ^ (n-2)))> = 1

C (-2 ^ (n-2))> = 1

C> = 1 / (2 ^ (n-2)) |при n-> бесконечность выражение обращается в ноль

Не означает ли это, что мое предположение слишком велико?Однако я знаю, что это не так.Кто-нибудь может увидеть, где именно я убиваю теорию?Спасибо.

Answer 1

Я думаю, что ваша алгебра верна после ввода Итая, но ваше понимание c >= 1/(2^(n-2)) неверно.

Вы правы как n --> infinity, а затем 1/(2^(n-2)) --> 0.Тем не менее, это не означает, что c --> 0, предполагая, что ваша догадка слишком высока.Скорее это говорит о том, что c >= 0.Следовательно, c может быть любой положительной константой и подразумевает, что ваше предположение является точным.

Answer 2

Переход от 2T(n-1)+T(n-2)+1 <= C(2^n) к 2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n) неверен.
если T(n) <= C(2^n), то вы можете сделать вывод, что 2T(n-1)+T(n-2)+1 <= 2C(2^(n-1))+C(2^(n-2))+1, но не 2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n).

Обратите внимание, что 2C(2^(n-1))=C(2^n)должно быть, что 2C(2^(n-1))+C(2^(n-2))+1 >= c(2^n).