Вычислительная сложность Последовательности Fibonacci

Используйте PDO и подготовленные запросы.

($conn - объект PDO)

$stmt = $conn->prepare("INSERT INTO tbl VALUES(:id, :name)");
$stmt->bindValue(':id', $id);
$stmt->bindValue(':name', $name);
$stmt->execute();
309
задан Tony Tannous 10 August 2017 в 05:43
поделиться

5 ответов

Вы моделируете функцию времени для вычисления Fib(n) как сумма времени для вычисления Fib(n-1) плюс время для вычисления Fib(n-2) плюс время для добавления их вместе (O(1)). Это предполагает, что повторенные оценки того же Fib(n) занимают то же время - т.е. никакой memoization не является использованием.

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) , который равен [1 133]

T(n) = O(2 <глоток> n-1 ) + O(2 <глоток> n-2 ) + O(1) = O(2 <глоток> n )

Однако, как отмечено в комментарии, это не связанное трудное. Интересный факт об этой функции - то, что T (n) асимптотически тот же как значение [1 123], так как оба определяются как [1 143]

f(n) = f(n-1) + f(n-2).

листы дерева рекурсии будут всегда возвращаться 1. Значение [1 125] является суммой всех значений, возвращенных листами в дереве рекурсии, которое равно количеству листов. Так как каждый лист возьмет O (1) для вычисления, T(n) равно [1 127]. Следовательно, трудной направляющейся в эту функцию является сама последовательность Fibonacci (~ θ(1.6 <глоток> n )). Можно узнать это трудное связанный при помощи производящих функций, как я упомянул выше.

349
ответ дан 11 revs, 2 users 95% 23 November 2019 в 01:14
поделиться

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

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

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

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

<глоток> n == <глоток> (n-1) + <глоток> (n-2)

Делятся через на <глоток> (n-2) :

<глоток> 2 == + 1

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

, Таким образом, это занимает время.

121
ответ дан Quazi Irfan 23 November 2019 в 01:14
поделиться

Существует очень хорошее обсуждение этого определенная проблема, законченная в MIT. На странице 5 они высказывают мнение, что, если Вы предполагаете, что дополнение берет одну вычислительную единицу, время, требуемое вычислить Выдумку (N), очень тесно связано с результатом Выдумки (N).

В результате можно пропустить непосредственно к очень близкому приближению ряда Fibonacci:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

и говорят, поэтому, что худшая производительность случая наивного алгоритма

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

пз: существует обсуждение закрытое выражение формы Энного Числа Фибоначчи закончено в Википедии, если Вы хотели бы больше информации.

29
ответ дан Bob Cross 23 November 2019 в 01:14
поделиться

Это ограничено на более низком уровне 2^(n/2) и на верхнем конце 2^n (как отмечено в других комментариях). И интересным фактом которого рекурсивная реализация состоит в том, что он имеет трудное асимптотическое, связанное Выдумки (n) самой. Эти факты могут быть получены в итоге:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

связанное трудное может быть уменьшено дальнейшее использование закрытая форма , если Вам нравится.

9
ответ дан Dave L. 23 November 2019 в 01:14
поделиться
0
ответ дан 23 November 2019 в 01:14
поделиться
Другие вопросы по тегам:

Похожие вопросы: