Я понимаю нотацию Big-O, но не знаю, как рассчитать ее для многих функций. В частности, я пытался выяснить вычислительную сложность наивной версии последовательности Фибоначчи:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Какова вычислительная сложность последовательности Фибоначчи и как она рассчитывается?
time-complexity
big-o
complexity-theory
fibonacci
Джульетта
источник
источник
Ответы:
Вы моделируете функцию времени для вычисления
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
)
База:
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
n
)
Однако, как отмечается в комментарии, это не жесткая граница. Интересный факт об этой функции заключается в том, что 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
n
)
источник
Просто спросите себя, сколько заявлений нужно выполнить для
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
, иначе известный как золотое сечение .Так что это требует экспоненциального времени.
источник
Я согласен с 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?
Давайте рассмотрим реальный случай, например F (6)
Мы видим, что 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.
Теперь с точки зрения сложности:
источник
Там очень хорошее обсуждение этой конкретной проблемы в MIT . На странице 5 они подчеркивают, что, если вы предполагаете, что сложение занимает одну вычислительную единицу, время, необходимое для вычисления Fib (N), очень тесно связано с результатом Fib (N).
В результате вы можете сразу перейти к очень близкому приближению ряда Фибоначчи:
и скажем поэтому, что наихудшая производительность наивного алгоритма
PS: в Википедии обсуждается выражение в закрытой форме числа N числа Фибоначчи, если вам нужна дополнительная информация.
источник
Вы можете расширить его и иметь визуализацию
источник
<
в конце есть менее чем характер ? Как ты получилT(n-1) + T(n-1)
?T(n-1) > T(n-2)
Так что я могу изменитьT(n-2)
и поставитьT(n-1)
. Я получу только более высокую оценку, которая все еще действительна дляT(n-1) + T(n-2)
На нижнем конце он ограничен
2^(n/2)
на верхнем конце 2 ^ n (как отмечено в других комментариях). И интересным фактом этой рекурсивной реализации является то, что она имеет жесткую асимптотическую границу самого Fib (n). Эти факты можно обобщить:Тесная граница может быть уменьшена далее, используя ее закрытую форму, если хотите.
источник
Контрольные ответы хороши, но мне всегда приходится делать несколько итераций вручную, чтобы действительно убедить себя. Поэтому я нарисовал небольшое дерево вызовов на своей доске и начал считать узлы. Я разделил свои отсчеты на все узлы, конечные узлы и внутренние узлы. Вот что я получил:
Что сразу бросается в глаза, так это количество конечных узлов
fib(n)
. То, что потребовалось еще несколько итераций, чтобы заметить, - то, что число внутренних узлов естьfib(n) - 1
. Поэтому общее количество узлов равно2 * fib(n) - 1
.Поскольку вы отбрасываете коэффициенты при классификации вычислительной сложности, окончательный ответ -
θ(fib(n))
.источник
1
к одному аккумуляторуFib(n)
, но интересно, что это все еще точноθ(Fib(n))
.0
, хотя: базовые случаи рекурсии есть0
и1
, потому что они делаютFib(n-1) + Fib(n-2)
. Так что, вероятно, ответ3 * Fib(n) - 2
из этого только для ссылки является более точным для общего числа узлов, а не2 * Fib(n) - 1
.Временная сложность рекурсивного алгоритма может быть лучше оценена путем построения дерева рекурсии. В этом случае отношение рекуррентности для построения дерева рекурсии будет иметь вид T (n) = T (n-1) + T (n-2) + O (1), отметив, что каждый шаг занимает O (1), что означает постоянное время, так как он выполняет только одно сравнение, чтобы проверить значение n в случае, если дерево block.Recursion будет выглядеть
Здесь, скажем, каждый уровень выше дерева обозначается i, следовательно,
допустим, при определенном значении i дерево заканчивается, этот случай будет, когда ni = 1, следовательно, i = n-1, что означает, что высота дерева равна n-1. Теперь давайте посмотрим, сколько работы проделано для каждого из n слоев дерева. Обратите внимание, что каждый шаг занимает O (1) время, как указано в отношении повторяемости.
поскольку i = n-1 - высота дерева, работа на каждом уровне будет
Следовательно, общая проделанная работа будет суммой проделанной работы на каждом уровне, следовательно, она будет 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)
. Итак, здесь, когда мы записываем сложность времени, встречающуюся на каждой глубине дерева, сумма суммирования выглядит так:это порядок
2^n [ O(2^n) ]
.источник
Наивная рекурсивная версия Фибоначчи имеет экспоненциальный характер из-за повторения в вычислениях:
В корне вы вычисляете:
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))
Это всего лишь нижняя граница, которую для целей вашего анализа должно быть достаточно, но функция реального времени является фактором постоянной по той же формуле Фибоначчи, и, как известно, закрытая форма экспоненциально равна золотому сечению.
Кроме того, вы можете найти оптимизированные версии Фибоначчи с помощью динамического программирования, например:
Это оптимизировано и делает только n шагов, но также экспоненциально.
Функции стоимости определяются от входного размера до количества шагов для решения проблемы. Когда вы видите динамическую версию Фибоначчи ( n шагов для вычисления таблицы) или самый простой алгоритм, чтобы узнать, является ли число простым ( sqrt (n), чтобы проанализировать действительные делители числа). Вы можете подумать, что эти алгоритмы являются O (n) или O (sqrt (n)), но это просто неверно по следующей причине: входными данными для вашего алгоритма является число: n , используя двоичную нотацию, входной размер для целое число n равно log2 (n), а затем делает изменение переменной
позвольте узнать количество шагов в зависимости от размера ввода
тогда стоимость вашего алгоритма в зависимости от размера ввода равна:
и именно поэтому стоимость является экспоненциальной.
источник
Это легко рассчитать путем построения диаграмм вызовов функций. Просто добавьте вызовы функций для каждого значения n и посмотрите, как растет число.
Большой O - это O (Z ^ n), где Z - золотое сечение или около 1,62.
Числа Леонардо и числа Фибоначчи приближаются к этому соотношению, поскольку мы увеличиваем n.
В отличие от других вопросов большого О, входные данные не изменчивы, и алгоритм и реализация алгоритма четко определены.
Там нет необходимости в кучу сложной математики. Просто изобразите вызовы функций ниже и подгоните функцию к числам.
Или, если вы знакомы с золотым сечением, вы узнаете его как таковой.
Этот ответ является более правильным, чем принятый ответ, который утверждает, что он приблизится к f (n) = 2 ^ n. Это никогда не будет. Это приблизится к f (n) = golden_ratio ^ n.
источник
http://www.ics.uci.edu/~eppstein/161/960109.html
время (n) = 3F (n) - 2
источник