Сложность времени выполнения LAB и числа Фибоначчи (Java)

Question

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

1. Числа Фибоначчи и сложность

Числа Фибоначчи рекурсивно определяются следующим образом:
F (n) = n, для n <= 1 <br> F (n) = F (n-1) + F (n-2) для n> 1
Напишите следующие методы для вычисления F (n):
а) метод O (2n ^ n), основанный на рекурсивном определении
б) метод O (n), который использует цикл
в) метод O (1), который использует решение в закрытой форме - не стесняйтесь искать эту формулу в режиме онлайн.

Проверьте все три метода, используя n = 10; 20; 50; 100; 1000; 10000; 100 000 и 1 000 000. Если определенная комбинация алгоритма и ввода не возвращает ответ в течение разумного периода времени, обратите внимание на это в своем отчете (то есть не ждите, пока ваша программа завершится часами (или хуже)).

Answer 1

Ну, чтобы ответить на часть c, есть функция с постоянным временем, которая будет вычислять n-е число Фибоначчи. Вы можете найти формулу для этого здесь: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

Answer 2

Я предполагаю, что "Hw" означает домашнюю работу, поэтому я не боюсь кода.

a) O (2n) и O (n) - это одно и то же.Вы имеете в виду O (2 ^ n)?Это произойдет, если вы используете рекурсивный метод без кэширования результатов.

b) Это «очевидный» способ реализовать его, используя процедурную реализацию и запоминая последние два числа и используя их для вычисления следующегоодин.В псевдокоде это будет что-то вроде loop { a, b = b, a+b; }

c) Это не будет работать для всех n, если у вас нет бесконечной точности, а бесконечная точность не равна O (1).Например, когда я использую doubles, fib (73) получается 806515533049395, но на самом деле это 80651553304939 3 .Разница связана с ошибками округления при работе с числами с плавающей запятой.

А что касается решения O (n), если вы собираетесь вычислять до fib (1000000), тогда 64-разрядное целое число небудет достаточно близко, чтобы сохранить результат.Вам нужно будет использовать BigIntegers.Добавление двух BigIntegers не является операцией O (1), поэтому упомянутая выше производительность O (n) слишком оптимистична.