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

Question

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

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

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

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

Т (п) < = С (2^п)

2T (п-1) + T (n-2) +1 < = C (2^n)

2C (2^(n-1)) + C (2^(n-2)) + 1 < = c (2^п)

С (2^п) -С (2^п + 2^(п-2))> = 1

С (-2^(п-2))> = 1

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

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

Answer 1

Переход от 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).

Answer 2

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

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