Я хочу найти рекуррентное уравнение для вычисления временной сложности
int Fib(int n)
{
if (n <= 1)
return n;
else
return Fib(n - 1) + Fib(n - 2);
}
Я могу решить рекуррентное уравнение, но мне трудно найти уравнение и базовый случай.
Это правильное уравнение?
T(n)=T(n-1)+T(n-2)+1
а для базового случая?
T(0)=0
T(1)=0
Кроме того, как можно найти базовый вариант для алгоритма?
Для сложности базовый случай в этом примере обычно не имеет значения. Лично я бы, вероятно, установил T(0) = 1, T(1) = 1, исходя из того, что ничто не занимает нулевое время. Но просто посмотрите на свое рекуррентное отношение. Это сама последовательность в стиле Фибоначчи, она будет экспоненциальной (почти-) независимо от базовых случаев.
Общая проблема для базовых случаев заключается в том, что вам нужен конкретный ответ («сколько времени потребуется для вычисления Fib(0)?»), но фактические «единицы времени» в расчетах сложности обычно плохо определены. Чтобы быть точным, вы должны определить T(0) равным константе k_1 и T(1) равным константе k_2, и работать с ними. Если вам нужны числовые значения для констант, чтобы решить рекуррентное соотношение, то, вероятно, что-то пошло не так.
Точно так же вы можете установить отношение рекуррентности на T(n) = T(n-1) + T(n-2) + k_3.
Обратите внимание, что если «единицей времени» для вашего расчета сложности является «количество выполнений сложения», игнорируя другую логику, то ваши базовые случаи верны в 0. Это был бы полезный способ анализа времени, если (например) добавление было выполнено пользовательской функцией, производительность которой выходит за рамки вашего анализа.
