Вычислительная сложность последовательности Фибоначчи
Я понимаю нотацию Big-O, но не знаю, как рассчитать ее для многих функций. В частности, я пытался выяснить вычислительную сложность наивной версии последовательности Фибоначчи:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Какова вычислительная сложность последовательности Фибоначчи и как она рассчитывается?
14 ответов
Вы моделируете функцию времени для расчета 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)). Вы можете узнать эту жесткую границу, используя генерирующие функции, как я уже упоминал выше.
Просто спросите себя, сколько заявлений нужно выполнить для 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, иначе известный как золотое сечение.
Так что это требует экспоненциального времени.
Я согласен с 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)
Там очень хорошее обсуждение этой конкретной проблемы в 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 числа Фибоначчи, если вам нужна дополнительная информация.
Вы можете расширить его и получить визуализацию
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)
Временная сложность рекурсивного алгоритма может быть лучше оценена путем построения дерева рекурсии. В этом случае отношение рекуррентности для построения дерева рекурсии будет иметь вид 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).
Доказательные ответы хороши, но мне всегда приходится делать несколько итераций вручную, чтобы действительно убедить себя. Поэтому я нарисовал небольшое дерево вызовов на своей доске и начал считать узлы. Я разделил свои отсчеты на все узлы, конечные узлы и внутренние узлы. Вот что я получил:
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)),
На нижнем конце он ограничен 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)
Тесная граница может быть уменьшена далее, используя ее закрытую форму, если хотите.
Наивная рекурсивная версия Фибоначчи имеет экспоненциальный дизайн из-за повторения в вычислениях:
В корне вы вычисляете:
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
и именно поэтому стоимость является экспоненциальной.
Это просто вычислить, построив диаграммы вызовов функций. Просто добавьте вызовы функций для каждого значения 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)
Ну, по мне, так это 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
время (n) = 3F(n) - 2
Отсутствие ответа подчеркивает, вероятно, самый быстрый и наиболее эффективный способ вычисления последовательности. Существует точное выражение в закрытой форме для последовательности Фибоначчи. Его можно найти с помощью производящих функций или с помощью линейной алгебры, как я сейчас сделаю.
Позволять
f_1 , f_2 , f_3 , ...
f_2 , f_3 , f_4 , ...
Обратите внимание, что следующий элемент
M = [0 1]
[1 1]
из-за
f_{n+1} = f_{n+1} and f_{n+2} = f_{n} + f_{n+1}
M диагонализируется над комплексными числами (на самом деле также диагонализируется над действительными числами, но обычно это не так). Есть два различных собственных вектора M, заданных формулой
1 1
x_1 x_2
где x_1 = (1+sqrt(5))/2 и x_2 = (1-sqrt(5))/2 — различные решения полиномиального уравнения
D = [x_1 0]
[0 x_2]
Чтобы найти f_n, найдите v_n и посмотрите на первую координату. Чтобы найти v_n, примените M n-1 раз к v_1. Но применить M n-1 раз легко, просто представьте, что это D. Тогда, используя линейность, можно найти
f_n = 1/sqrt(5)*(x_1^n-x_2^n)
Поскольку норма x_2 меньше 1, соответствующий член обращается в нуль, когда n стремится к бесконечности; поэтому получения наибольшего целого числа, меньшего, чем (x_1^n)/sqrt(5), достаточно, чтобы точно найти ответ. Используя трюк многократного возведения в квадрат, это можно сделать, используя только
Это работает намного лучше:
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;
}