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

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



int Fibonacci(int n)

{

    if (n <= 1)

        return n;

    else

        return Fibonacci(n - 1) + Fibonacci(n - 2);

}


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

599   11  

11 ответов:

вы моделируете функцию времени для вычисления Fib(n) как сумма времени для расчета Fib(n-1) плюс время для расчета Fib(n-2) плюс время, чтобы добавить их вместе (O(1)).

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) is равно Fib(n) x O(1). Следовательно, жесткой границей для этой функции является сама последовательность Фибоначчи (~θ(1.6n)). Вы можете узнать эту жесткую связь, используя функции генерации, как я уже упоминал выше.

304  
2012-09-13 23:23:30

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

на F(1) ответ 1 (первая часть условной).

на F(n) ответ F(n-1) + F(n-2).

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

an = = a(n-1) + a(n-2)

разделить по а(n-2):

a2 = = a + 1

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

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

107  
2017-10-04 12:02:20

есть очень хорошая дискуссия об этом конкретная проблема в 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-го числа Фибоначчи в Википедии, Если вы хотите получить больше информации.

27  
2008-12-11 23:21:14

Я согласен с 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) вызывается только часть этого.

если мы мысленно переместим все * ' S из 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)
24  
2014-04-16 00:38:56

вы можете развернуть его и иметь визуализацию 

     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)
11  
2017-08-10 18:39:12

он ограничен на нижнем конце 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)

плотная граница может быть уменьшена далее с помощью его закрытая форма если вам нравится.

8  
2008-12-11 23:03:08

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

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)).

8  
2014-02-28 03:21:33

ну, по мне это 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) ].

2  
2012-11-18 03:24:21

http://www.ics.uci.edu / ~eppstein/161/960109.html

Время (n) = 3F(n) - 2

1  
2010-04-28 23:33:32

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

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

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

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

0  
2017-10-01 01:21:52

это работает намного лучше:

unsigned int Fib(unsigned int n)
{
    // first Fibonaci number is Fib(0)
    // second one is Fib(1) and so on

    // unsigned int m;  // m + current_n = original_n
    unsigned int a = 1; // Fib(m)
    unsigned int b = 0; // Fib(m-1)
    unsigned int c = 0; // Fib(m-2)

    while (n--)
    {
        c = b;
        b = a;
        a = b+c;
    }

    return a;
}
-4  
2008-12-20 23:10:16

Comments

    Ничего не найдено.
Click here to cancel reply.