Временная сложность рекурсивной функции с тремя рекурсивными вызовами

Question

Какова будет временная сложность рекурсивной функции со следующим рекуррентным соотношением:

T(n) = T(n-1) + T(n-2) + T(n-3), T(0) = T(1) = 1 and T(2) = 2

Я знаю, что функция с двумя рекурсивными вызовами даст нам экспоненциальную временную сложность O (2 ^ n) , будет ли это означать, что функция с вышеуказанным рекуррентным соотношением будет иметь временную сложность O (3 ^ n) ?

Спасибо за помощь.

Answer 1

Если быть более точным, предположим, что у вас есть такая функция:

T(n) = T(n-1) + T(n-1) + T(n-1), T(0) = 1

Способ, которым это написано. Сложность по времени точно равна O (3 ^ n).

Ваша функциянемного лучше, чем эта функция, но все же сложность по времени та же O (3 ^ n)

Теперь, если мы переписаем мой предложенный код, например:

T(n) = 3 * T(n-1), T(0) = 1

Сложность просто O (n)!потому что результаты предыдущих вызовов повторно используются без повторного вызова.

Так что в вашей реализации, если у вас может быть буфер, чтобы не вызывать, а просто использовать ранее вызванные значения (некоторые языки фактически могут это поддерживать), то сложностьухудшится до O (n).