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

https://stackoverflow.com/questions/360748

21-08-2019
|

Вопрос

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

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

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

Решение

Вы моделируете функцию времени для вычисления 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(2ⁿ).Затем вы можете доказать свою гипотезу методом индукции.

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

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

T(n) = T(n-1) + T(n-2) + O(1) который равен

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

Однако, как отмечено в комментарии, это не самая жесткая граница.Интересным фактом об этой функции является то, что 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.6ⁿ)).Вы можете выяснить эту жесткую границу, используя генерирующие функции, как я упоминал выше.

Другие советы

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

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

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

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

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

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

a² == a + 1

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

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

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

Я согласен с пгауром и рикербхом, рекурсивная сложность фибоначчи равна 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)

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

     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)

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

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

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

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

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

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

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

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

time(n) = 3F(n) - 2

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

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

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

и именно поэтому стоимость растет в геометрической прогрессии.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow