Какова временная сложность рекурсивного алгоритма, заданного рекуррентностью T (n) = 2T (n-1) + 1 - PullRequest
Новая
       8

Какова временная сложность рекурсивного алгоритма, заданного рекуррентностью T (n) = 2T (n-1) + 1

1 голос
/ 08 апреля 2020

Я совершенно новичок в этом, так что шаг за шагом очень помог бы, спасибо.

1 Ответ

2 голосов
/ 09 апреля 2020

Во-первых, вы можете начать с метода итерации , чтобы понять, как это происходит. 

T(n) = 2T(n-1) + 1 = 
     = 2*(2T(n-2) + 1) + 1 = 4T(n-2) + 3
     = 4(2T(n-3) + 1) + 3 = 8T(n-3) + 7
     = 8*(2T(n-4) + 1) + 7 = 16T(n-4) + 15
     = 16*(2T(n-5) + 1) + 15 = 32T(n-5) + 31

Теперь, когда мы понимаем поведение, мы можем сказать 

T(n) = 2^i * T(n-i) + (2^i - 1)

Теперь нам нужно использовать базовое предложение (о котором не идет речь) и извлечь для i=n. Например, если T(0) = 0: 

T(n) = 2^n * T(0) + (2^n - 1) = 2^n - 1

Это при O(2^n), при вычислении асимптотики c сложность.

Примечание: Метод итерации хорош и легко следовать - но это не формальное доказательство. Чтобы формально доказать сложность, вам понадобится другой инструмент, такой как индукция.

...