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

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

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

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

11.12.2008 20:20:25
См. Раздел формы матрицы здесь: en.wikipedia.org/wiki/Fibonacci_number . Делая эту матрицу ^ n (умным способом), вы можете вычислить Fib (n) в O (lg n). Хитрость заключается в выполнении функции власти. На iTunesU очень хорошая лекция об этой конкретной проблеме и о том, как ее решить в O (LG N). Курс интро к алгоритмам из MIT лекции 3 (его Absolutley бесплатно , чтобы проверить это, если вы заинтересованы)
Aly 11.02.2011 16:50:33
Ни один из приведенных выше комментариев не затрагивает вопрос, касающийся сложности вычислений наивной версии (в размещенном коде), а не о более умных версиях, таких как матричная форма или нерекурсивные вычисления.
Josh Milthorpe 2.05.2018 05:21:07
Очень красивое видео здесь , который говорит о как нижняя граница сложности (2 ^ п / 2) и верхняя граница сложности (2 ^ п) рекурсивной реализации.
RBT 29.01.2019 00:08:49
Дополнительный вопрос: должна ли наивная реализация ряда Фибоначчи быть итеративной или рекурсивной ?
RBT 29.01.2019 00:12:36
12 ОТВЕТОВ
РЕШЕНИЕ

Вы моделируете функцию времени для вычисления 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)

371
30.01.2019 08:48:59
Также доказательство по индукции. Ницца. +1
Andrew Rollings 11.12.2008 20:38:34
Хотя граница не жесткая.
Captain Segfault 11.12.2008 21:15:20
@ Капитан Сегфо: Да. Я уточнил ответ. Вы получите жесткую границу, используя метод GF, как я написал выше.
Mehrdad Afshari 11.12.2008 21:36:09
Я принимаю ваше StackOverflowException в качестве шутки. Экспоненциальное время довольно легко ощутимо при достаточно малых значениях n.
David Rodríguez - dribeas 11.12.2008 23:08:44
«В качестве альтернативы вы можете нарисовать дерево рекурсии, которое будет иметь глубину n и интуитивно понять, что эта функция асимптотически O (2n)». - Это совершенно неверно. Сложность времени O (golden_ratio ^ n). Это никогда не приближается к O (2 ^ n). Если бы вы могли дотянуться до бесконечности, это приблизилось бы к O (golden_ratio ^ n). Вот что такое асимптота, расстояние между двумя линиями должно приближаться к 0.
bob 20.12.2019 22:32:21

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

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

Ибо F(n)ответ есть F(n-1) + F(n-2).

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

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

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

a 2 == a + 1

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

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

130
4.10.2017 09:02:20
Доказательство по индукции. Ницца. +1
Andrew Rollings 11.12.2008 20:37:58
30 голосов за неправильный ответ? :-) Из этого следует, что 1 = F (1) = (1 + sqrt (5)) / 2? А как насчет другого решения (1-sqrt (5)) / 2?
Carsten S 24.08.2013 22:11:33
Нет, 1 не равно 1 + 1. Функция, которая удовлетворяет этим правилам, упоминается в вопросе.
molbdnilo 14.08.2014 12:46:55
Ответ не неправильный. Это верно бессимптомно. Другое решение отрицательно, поэтому не имеет физического смысла.
Da Teng 10.04.2016 00:35:50
Может кто-нибудь объяснить, как ^ n == a ^ (n-1) + a ^ (n-2) удовлетворяют этим правилам? Как именно это устраивает, пожалуйста, будьте конкретны.
frank 3.08.2016 20:22:06

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

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

10
11.12.2008 21:03:08

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

31
11.12.2008 21:21:14
Спасибо за ссылку на курс. Очень хорошее наблюдение тоже
SwimBikeRun 15.08.2018 01:19:18
-1
28.04.2010 20:33:32
Также было бы хорошо, если бы вы могли объяснить свой ответ, а не только опубликовать ссылку.
Magnilex 11.01.2015 08:36:08
Объяснения не предоставлены
Kunal B. 31.07.2016 01:07:48

Ну, по моему мнению, так 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
18.11.2012 01:24:21

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

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

10
28.02.2014 01:21:33
(Нет, я не рисовал полное дерево вызовов в 10 глубин на своей доске. Только 5 глубин.);)
benkc 28.02.2014 01:23:04
Хорошо, мне было интересно, сколько дополнительных рекурсивных дополнений сделал Fib. Это не просто добавление времени 1к одному аккумулятору Fib(n), но интересно, что это все еще точно θ(Fib(n)).
Peter Cordes 1.03.2018 18:49:12
Обратите внимание, что некоторые (большинство) рекурсивных реализаций тратят время на добавление 0, хотя: базовые случаи рекурсии есть 0и 1, потому что они делают Fib(n-1) + Fib(n-2). Так что, вероятно, ответ3 * Fib(n) - 2 из этого только для ссылки является более точным для общего числа узлов, а не 2 * Fib(n) - 1.
Peter Cordes 1.03.2018 18:52:46
Я не могу получить те же результаты на листовых узлах. Начиная с 0: F (0) -> 1 лист (сам); F (1) -> 1 лист (сам); F (2) -> 2 листа (F (1) и F (0)); F (3) -> 3 листа; F (5) -> 8 листьев; и т. д.
alexlomba87 1.04.2020 12:11: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) является лишь частью этого.

Если мы мысленно переместим все * из строк 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)
32
15.04.2014 21:38:56
F (3) вызывается только 3 раза, а не 4 раза. Вторая пирамида неверна.
Avik 22.02.2016 10:08:51
F (3) = 3, F (2) = 5, F (1) = 8, F (0) = 5. Я бы это исправил, но не думаю, что смогу отредактировать этот ответ.
Dukeling 13.06.2017 19:20:06

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

     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)
16
10.08.2017 15:39:12
Я понимаю первую строчку. Но почему <в конце есть менее чем характер ? Как ты попал T(n-1) + T(n-1)?
Quazi Irfan 4.10.2017 07:40:02
@QuaziIrfan: D это стрела. -> [(не менее). Извините за путаницу в отношении последней строки. Для первой строки, хорошо ... T(n-1) > T(n-2)Так что я могу изменить T(n-2)и поставить T(n-1). Я получу только более высокую оценку, которая все еще действительна дляT(n-1) + T(n-2)
Tony Tannous 4.10.2017 07:42:30

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

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

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

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

1
30.09.2017 22:21:52

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

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 дерево заканчивается, этот случай будет, когда ni = 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).

8
29.11.2018 06:35:19

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

Большой O - это O (Z ^ n), где Z - золотое сечение или около 1,62.

Числа Леонардо и числа Фибоначчи приближаются к этому соотношению, поскольку мы увеличиваем n.

В отличие от других вопросов Big O, входные данные не изменчивы, и алгоритм и реализация алгоритма четко определены.

Там нет необходимости в кучу сложной математики. Просто составьте схему вызовов функций ниже и подгоните функцию к числам.

Или, если вы знакомы с золотым сечением, вы узнаете его как таковой.

Этот ответ является более правильным, чем принятый ответ, который утверждает, что он приблизится к f (n) = 2 ^ n. Это никогда не будет. Это приблизится к f (n) = golden_ratio ^ n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)
1
20.12.2019 23:04:55
Можете ли вы предоставить какой-либо источник для этого утверждения о золотом сечении?
Nico Haase 11.01.2020 15:46:00