Вычислительная сложность последовательности Фибоначчи

Question

Я понимаю нотацию Big-O, но не знаю, как рассчитать ее для многих функций. В частности, я пытался выяснить вычислительную сложность наивной версии последовательности Фибоначчи:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Какова вычислительная сложность последовательности Фибоначчи и как она рассчитывается?

Answer 1

Вы моделируете функцию времени для вычисления Fib(n) как сумму времени для расчета Fib(n-1) плюс время для вычисления Fib(n-2) плюс время для их сложения (O(1)). При этом предполагается, что повторные оценки одного и того же Fib(n) занимают одно и то же время, т. Е. Не используется запоминание.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Вы решаете это рекуррентное отношение (например, с помощью генерирующих функций), и в итоге получите ответ.

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

База: n = 1 очевидна

Предположим, T(n-1) = O(2n-1), , следовательно,

T(n) = T(n-1) + T(n-2) + O(1) , что равно

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

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

f(n) = f(n-1) + f(n-2).

Листья дерева рекурсии всегда возвращают 1. Значение Fib(n) - это сумма всех значений, возвращаемых листьями в дереве рекурсии, которая равна количеству листьев. Поскольку для вычисления каждого листа потребуется O (1), T(n) равно Fib(n) x O(1). Следовательно, жесткой границей для этой функции является сама последовательность Фибоначчи (~ θ(1.6n)). Вы можете узнать эту жесткую границу, используя генерирующие функции, как я упоминал выше.

Answer 2

Просто спросите себя, сколько операторов нужно выполнить, чтобы завершить F(n).

Для F(1) ответ: 1 (первая часть условного выражения).

Для F(n) ответ: F(n-1) + F(n-2).

Так какая функция удовлетворяет этим правилам? Попробуйте ⁿ (a> 1):

a ⁿ == a ^(n-1) + a ^(n-2)

Разделить на ^(n-2) :

a ² == a + 1

Решите для a, и вы получите (1+sqrt(5))/2 = 1.6180339887, иначе известный как золотое сечение .

Так что требуется экспоненциальное время.

Answer 3

Я согласен с pgaur и rickerbh, сложность рекурсивного Фибоначчи - O (2 ^ n).

Я пришел к такому же выводу довольно упрощенно, но я верю, что все еще верны рассуждения.

Во-первых, нужно выяснить, сколько раз вызывается рекурсивная функция Фибоначчи (F () с этого момента) при вычислении N-го числа Фибоначчи. Если он вызывается один раз на число в последовательности от 0 до n, то у нас есть O (n), если он вызывается n раз для каждого номера, то мы получаем O (n * n) или O (n ^ 2), и т. д.

Таким образом, когда F () вызывается для числа n, число обращений к F () для данного числа от 0 до n-1 увеличивается с приближением к 0.

В качестве первого впечатления мне кажется, что если мы представим это визуально, то для заданного числа вызывается отрисовка единицы измерения за один раз, когда F () получает мокрую форму пирамиды (то есть, если мы центрировать единицы по горизонтали). Примерно так:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Теперь вопрос в том, насколько быстро увеличивается основание этой пирамиды с ростом n?

Давайте рассмотрим реальный случай, например, F (6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

Мы видим, что F (0) вызывается 32 раза, что составляет 2 ^ 5, что для данного примера составляет 2 ^ (n-1).

Теперь мы хотим знать, сколько раз F (x) вызывается вообще, и мы можем видеть, что количество вызовов F (0) является лишь частью этого.

Если мы мысленно переместим все * из строк F (6) в F (2) в строку F (1), мы увидим, что строки F (1) и F (0) теперь равны по длине. Это означает, что общее время F () вызывается, когда n = 6 равно 2x32 = 64 = 2 ^ 6.

Теперь по сложности:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

Answer 4

Есть очень хорошее обсуждение этой конкретной проблемы на MIT . На странице 5 они подчеркивают, что, если вы предполагаете, что сложение занимает одну вычислительную единицу, время, необходимое для вычисления Fib (N), очень тесно связано с результатом Fib (N).

В результате вы можете сразу перейти к очень близкому приближению ряда Фибоначчи:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

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

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: В Википедии обсуждается выражение в закрытой форме N-го числа Фибоначчи , если вам нужна дополнительная информация.

Answer 5

Вы можете расширить его и получить визуализацию

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

Answer 6

Доказательные ответы хорошие, но мне всегда приходится делать несколько итераций вручную, чтобы действительно убедить себя. Поэтому я нарисовал небольшое дерево вызовов на своей доске и начал считать узлы. Я разделил свои отсчеты на все узлы, конечные узлы и внутренние узлы. Вот что я получил:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

Что сразу бросается в глаза, так это то, что число конечных узлов равно fib(n). Еще несколько итераций потребовалось, чтобы заметить, что число внутренних узлов равно fib(n) - 1. Поэтому общее количество узлов составляет 2 * fib(n) - 1.

Поскольку вы отбрасываете коэффициенты при классификации вычислительной сложности, окончательный ответ будет θ(fib(n)).

Answer 7

На нижнем конце он ограничен 2^(n/2), а на верхнем - 2 ^ n (как отмечено в других комментариях). Интересным фактом этой рекурсивной реализации является то, что она имеет жесткую асимптотическую границу самого Fib (n). Эти факты можно обобщить:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

Точную границу можно уменьшить, используя закрытую форму , если хотите.

Answer 8

Временная сложность рекурсивного алгоритма может быть лучше оценена путем рисования дерева рекурсии. В этом случае рекуррентное отношение для рисования дерева рекурсии будет T (n) = T (n-1) + T (n-2) + O (1) ) обратите внимание, что каждый шаг принимает O (1), что означает постоянное время, так как он делает только одно сравнение, чтобы проверить значение n в , если block.Recursion будет выглядеть как

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Здесь, скажем, каждый уровень выше дерева обозначается как я следовательно,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

Допустим, при определенном значении i, дерево заканчивается, этот случай будет, когда n-i = 1, следовательно, i = n-1, что означает, что высота дерева равна n-1. Теперь давайте посмотрим, сколько работы проделано для каждого из n слоев дерева. Обратите внимание, что каждый шаг занимает O (1) время, как указано в отношении повторяемости.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

, поскольку i = n-1 - высота дерева, выполняемая на каждом уровне, будет

i work
1 2^1
2 2^2
3 2^3..so on

Следовательно, общая проделанная работа будет суммой проделанной работы на каждом уровне, следовательно, она будет 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1), так как i = n -1. По геометрическим рядам эта сумма равна 2 ^ n, следовательно, общая сложность времени здесь составляет O (2 ^ n)

Answer 9

Ну, по-моему, это O(2^n), поскольку в этой функции только рекурсия занимает значительное время (разделяй и властвуй). Мы видим, что вышеуказанная функция будет продолжаться в дереве, пока листья не приблизятся, когда мы достигнем уровня F(n-(n-1)), т.е. F(1). Итак, здесь, когда мы записываем сложность времени, встречающуюся на каждой глубине дерева, сумма суммирования равна:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

это порядка 2^n [ O(2^n) ].

Answer 10

Наивная рекурсивная версия Фибоначчи имеет экспоненциальный характер из-за повторения в вычислениях:

В корне вы вычисляете:

F (n) зависит от F (n-1) и F (n-2)

F (n-1) снова зависит от F (n-2) и F (n-3)

F (n-2) снова зависит от F (n-3) и F (n-4)

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

T (n) = T (n-1) + T (n-2) + C, с постоянной C

T (n-1) = T (n-2) + T (n-3)> T (n-2), затем

T (n)> 2 * T (n-2)

...

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

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

Кроме того, вы можете найти оптимизированные версии Фибоначчи, использующие динамическое программирование, например:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

Это оптимизировано и делает только n шагов, но также экспоненциально.

Функции стоимости определяются от Входного размера до количества шагов для решения проблемы. Когда вы видите динамическую версию Фибоначчи ( n шагов для вычисления таблицы) или самый простой алгоритм, чтобы узнать, является ли число простым ( sqrt (n) для анализа действительных делителей число). Вы можете подумать, что эти алгоритмы: O (n) или O (sqrt (n)) , но это просто неверно по следующей причине: Входными данными для вашего алгоритма является число: n , используя двоичную запись, размер ввода для целого числа n равен log2 (n) , затем выполняется изменение переменной из

m = log2(n) // your real input size

позвольте узнать количество шагов в зависимости от размера ввода

m = log2(n)
2^m = 2^log2(n) = n

тогда стоимость вашего алгоритма как функция размера ввода равна:

T(m) = n steps = 2^m steps

и поэтому стоимость экспоненциальная.