Экспоненциальная оценка сложности для рекурсивных функций

[Mr Alexey]

Добрый вечер. Потребовалось определять сложность для рекурсивных функций следующего вида:
$ P(n) = \begin{cases} \operatorname{const},&\text{при $n < k$}\\ x_1 \cdot P(n-1)+ x_2 \cdot P(n-2)+...+x_k \cdot P(n-k),&\text{где $x_i$ - некоторые целочисленные коэффиициенты} \end{cases}$

В часности, есть такая функция:
$P(n) = \begin{cases} 1,&\text{при $n < 3$}\\ P(n-1)+2P(n-2)-P(n-3) \end{cases}$
Я попробывал определить сложность методом мат. индукции, предположив, что она экспоненциальна: $P(n) = k^n$
Индукционный переход имеет вид: $P(n+3) = k^3 \cdot k^n = k^2 \cdot k^n + 2 \cdot k \cdot k^n - k^n $
Из решения уравнения следует, что k ~ 1.8, т.е. оценка $P(n) = 1.8^n$

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

[ИСН]

Mr Alexey в сообщении #838527 писал(а):

обычно у экспонениальных оценок основание равно 2

Про числа Фибоначчи слышали когда-нибудь, например?

[nikvic]

Mr Alexey в сообщении #838527 писал(а):

Потребовалось определять сложность для рекурсивных функций следующего вида:

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

[Mr Alexey]

ИСН в сообщении #838569 писал(а):

Про числа Фибоначчи слышали когда-нибудь, например?

Теперь слышал, оценка $(\frac{1 + \sqrt 5}2)^n $, спасибо что обратили внимание.

nikvic в сообщении #838603 писал(а):

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

Действительно, имелась ввиду не сложность функции, а сложность алгоритма.

Еще один вопрос: для всех таких алгоритмов оценка будет экспоненциальной?

[svv]

В упор не вижу здесь ни одного алгоритма экспоненциальной сложности.

[nikvic]

Mr Alexey в сообщении #838657 писал(а):

для всех таких алгоритмов оценка будет экспоненциальной?

Гм, Вы оцениваете не сложность вычислений, а функцию.
Там, скорей всего, есть 2 варианта - периодичность и показательность.
Как у линейных дифур

А сколько нужно умножений?

[Mr Alexey]

nikvic в сообщении #838682 писал(а):

А сколько нужно умножений?

Не совсем понял, какие умножения?

[Xaositect]

Mr Alexey в сообщении #838527 писал(а):

обычно у экспонениальных оценок основание равно 2, а различаются только показатели.

Может быть, их просто так пишут? $a^n = 2^{n \log a}$.

[nikvic]

Mr Alexey в сообщении #838695 писал(а):

Не совсем понял, какие умножения?

Насколько я понимаю, для получения следующего члена нужно 3 умножения и 2 сложения
Итого - линейное количество операций....