рекуррентное уравнение из алгоритма Фибоначчи

Я хочу найти рекуррентное уравнение для вычисления временной сложности 

    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

И вообще, как можно найти базовый случай для алгоритма ?

1 3
algorithm equation recurrence

1 ответ:

Для сложности базовый случай в этом примере обычно не имеет значения. Лично я бы, наверное, поставил 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. Это был бы полезный способ проанализировать время, если бы (например) добавление было сделано пользовательской функцией, производительность которой выходит за рамки вашего анализа.

3