Использование рекуррентных отношений для доказательства функции имеет экспоненциальное время выполнения?

Question

Вот простая программа C:

int f(int n) { 
    if(n==0 || n==1) { 
    return n; 
    } else { 
    return 2 * f(n - 1) + 3 * f(n - 2); 
    } 
} 

Эта программа имеет экспоненциальную сложность времени. Вы можете увидеть это в этой схеме вызовов функций для f(5):

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

Рекуррентное соотношение я придумал это

Т (п) = Т (п-1) + T (N-2) + с

расширяющейся дает

Т (п) = 2T (п - 2) + Т (п - 3) + 2c

Однако я не знаю, как решить Thi Далее. Как я могу решить эту рекуррентную связь?

Answer 1

Для начала, ваше повторение нуждается в некотором базовом случае, так как в противном случае он не определен, когда вы нажмете 0. Для простоты допустим, что

T (0) = а

T (1) = а + Ь

Т (п + 2) = Т (п) + Т (п + 1) + с

Давайте начнем расширение из нескольких первых членов этого рецидива:

• Т (0) = а
• Т (1) = а + Ь
• T (2) = 2а + B + C
• T (3) = 3a + 2b + 2c
• Т (4) = 5 + 3b + 4c
• Т (5) = 8 + 5b + 7с
• Т (6) = 13a + 8b + 12с
• Т (7) = 21a + 13b + 20c

Здесь очень интересный образец. Давайте посмотрим индивидуально на коэффициенты коэффициентов a, b и c. Коэффициенты Термины следовать образцу

1, 1, 2, 3, 5, 8, 13, 21, ...

Это ряд Фибоначчи, смещение на один шаг , Коэффициенты b терминов равны

0, 1, 1, 2, 3, 5, 8, 13, ...

Который именно Серия Фибоначчи. Наконец, давайте посмотрим на условиях C:

0, 0, 1, 2, 4, 7, 12, 20, ...

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

а: 1, 1, 2, 3, 5, 8, 13, 21, ...

б: 0, 0, 1, 2, 4, 7, 12, 20, ...

Обратите внимание, что условия б, все члены с а один вычитании! Другими словами, это серия Фибоначчи, сдвинутая на один шаг, но с 1 вычитанием из каждого члена.

На основании этих наблюдений, мы можем предположить, что справедливо следующее:

Т (п) = ар _{п + 1} + Bf _п + с (Р _{п + 1} - 1)

Теперь мы можем попытаться доказать это индукцией.В наших базовых случаях:

T (0) = а = 1а + 0b + 0C = 1а + 0b + (1 - 1) с = Af + Bf + C (F - 1)

Т (1) = а + Ь = 1а + 1b + 0c = 1a + 1b + (1 - 1) с = ар + Bf + с (Р - 1)

Для нашего шага индукции, предположим, что для некоторого натурального числа п, что

Т (п) = ар _{п + 1} + Bf _п + с (Р _{п + 1} - 1)

и что

Т (п + 1) = ар _{п + 2} + Bf _{п + 1} + с (Рп + 2 - 1)

Тогда мы имеем, что

Т (п + 2) = Т (п) + Т (п + 1) + с

= AF _{п + 1} + Bf _п + с (Р _{п + 1} - 1) + АФ _{п + 2} + Bf _{п + 1} + с (Р _{п + 2} - 1) + с

= A (F _{N + 1} + F _{п + 2}) + В (F _п + Ж _{п + 1}) + с (Р _{п + 1} + Ж _{п + 2} - 2 + 1)

= AF _{п + 3} + Bf _{п + 2} + с (Р _{п + 3} - 1)

Это завершает индукцию, поэтому наша формула должна быть правильной!

Как это соотносится с эффективностью? Ну, Binet's formula говорит нам, что F _п = Θ (φ ^п), где φ является golden ratio (около 1,61).Это означает, что

Т (п) = ар _{п + 1} + Bf _п + с (Р _{п + 1} - 1) = а Θ (φ ^п) + Ь Θ (φ ^п) + с Θ (φ ^п) = Θ ((а + B + C) φ ^п)

Так до тех пор, а + B + C ≠ 0, среда выполнения является Θ (φ ^п), который является экспоненциальной.

Надеюсь, это поможет!