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

331

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

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

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

Джульетта
источник
3
Смотрите раздел матричной формы здесь: en.wikipedia.org/wiki/Fibonacci_number . выполняя эту матрицу ^ n (умным способом), вы можете вычислить Fib (n) в O (lg n). Хитрость заключается в выполнении функции власти. Theres очень хорошая лекция на iTunesU об этой точной проблеме и как решить в O (LG N). Курс интро к алгоритмам из MIT лекции 3 (его Absolutley бесплатно , чтобы проверить это, если вы заинтересованы)
Aly
1
Ни один из приведенных выше комментариев не затрагивает вопрос, касающийся сложности вычислений наивной версии (в размещенном коде), а не о более умных версиях, таких как матричная форма или нерекурсивные вычисления.
Джош Милторп,
Очень красивое видео здесь , который говорит о как нижняя граница сложности (2 ^ п / 2) и верхняя граница сложности (2 ^ п) рекурсивной реализации.
RBT
1
Дополнительный вопрос: должна ли наивная реализация ряда Фибоначчи быть итеративной или рекурсивной ?
RBT

Ответы:

375

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

Mehrdad Afshari
источник
29
Также доказательство по индукции. Ницца. +1
Эндрю Роллингс
Хотя граница не жесткая.
Капитан Сегфо
@Captain Segfault: Да. Я уточнил ответ. Вы получили бы жесткую границу, используя метод GF, как я написал выше.
Мехрдад Афшари
Я принимаю ваше StackOverflowException в качестве шутки. Экспоненциальное время довольно легко ощутимо при достаточно малых значениях n.
Дэвид Родригес - dribeas
1
«В качестве альтернативы вы можете нарисовать дерево рекурсии, которое будет иметь глубину n и интуитивно понять, что эта функция асимптотически O (2n)». - Это совершенно неверно. Сложность времени O (golden_ratio ^ n). Это никогда не приближается к O (2 ^ n). Если бы вы могли дотянуться до бесконечности, это приблизилось бы к O (golden_ratio ^ n). Вот что такое асимптота, расстояние между двумя линиями должно приближаться к 0.
Боб
133

Просто спросите себя, сколько заявлений нужно выполнить для 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, иначе известный как золотое сечение .

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

Джейсон Коэн
источник
8
Доказательство по индукции. Ницца. +1
Эндрю Роллингс
2
30 голосов за неправильный ответ? :-) Из этого следует, что 1 = F (1) = (1 + sqrt (5)) / 2? А как насчет другого решения (1-sqrt (5)) / 2?
Карстен С.
1
Нет, 1 не равно 1 + 1. Функция, которая удовлетворяет этим правилам, упоминается в вопросе.
molbdnilo
6
Ответ не неправильный. Это верно бессимптомно. Другое решение отрицательно, поэтому не имеет физического смысла.
Да Тен
10
Может кто-нибудь объяснить, как ^ n == a ^ (n-1) + a ^ (n-2) удовлетворяют этим правилам? Как именно это устраивает, пожалуйста, будьте конкретны.
Фрэнк
33

Я согласен с 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)
JP
источник
3
F (3) вызывается только 3 раза, а не 4 раза. Вторая пирамида неверна.
Авик
2
F (3) = 3, F (2) = 5, F (1) = 8, F (0) = 5. Я бы это исправил, но не думаю, что смогу отредактировать этот ответ.
Бернхард Баркер
31

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

Боб Кросс
источник
Спасибо за ссылку на курс. Очень хорошее наблюдение тоже
SwimBikeRun
16

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

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

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

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

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

benkc
источник
(Нет, я не рисовал полное дерево вызовов в 10 глубин на своей доске. Просто 5 глубин.);)
benkc
Хорошо, мне было интересно, сколько дополнительных рекурсивных дополнений сделал Fib. Это не просто добавление времени 1к одному аккумулятору Fib(n), но интересно, что это все еще точно θ(Fib(n)).
Питер Кордес
Обратите внимание, что некоторые (большинство) рекурсивных реализаций тратят время на добавление 0, хотя: базовые случаи рекурсии есть 0и 1, потому что они делают Fib(n-1) + Fib(n-2). Так что, вероятно, ответ3 * Fib(n) - 2 из этого только для ссылки является более точным для общего числа узлов, а не 2 * Fib(n) - 1.
Питер Кордес
Я не могу получить те же результаты на листовых узлах. Начиная с 0: F (0) -> 1 лист (сам); F (1) -> 1 лист (сам); F (2) -> 2 листа (F (1) и F (0)); F (3) -> 3 листа; F (5) -> 8 листьев; и т. д.
alexlomba87
9

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

Нихил Кекан
источник
2

Ну, по моему мнению, так 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) ].

pgaur
источник
1

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

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

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

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

Miguel
источник
1

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

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

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

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

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

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

Этот ответ является более правильным, чем принятый ответ, который утверждает, что он приблизится к 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
Можете ли вы предоставить какой-либо источник для этого утверждения о золотом сечении?
Нико Хаасе
-1

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

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

nsh3
источник
4
Также было бы хорошо, если бы вы могли объяснить свой ответ, а не только опубликовать ссылку.
Magnilex
2
Объяснения не предоставлены
Кунал Б.