Я використовував бібліотеку часу і приурочував скільки часурекурсивний алгоритм вимагає обчислити числа фіб до 50. Наведіть це число, чи є формула, яку я можу використовувати, щоб визначити, скільки часу потенційно знадобиться для обчислення фіб (100)?
Часи для менших значень:
Fib(40): 0.316 sec
Fib(80): 2.3 years
Fib(100): ???
Відповіді:
1 для відповіді № 1Це дуже залежить від використовуваного алгоритму. Пряме обчислення займає постійний час. Рекурсивне обчислення без запам'ятовування експоненціальне, з основою фі. Додайте до цього запам'ятовування, і воно припадає на логарифмічний час.
Єдиний, який міг би відповідати вашим даним, - це експоненційний час. Займається базовою математикою ...
(2.3 years / 0.316 sec) ** (1.0/40)
gives us
base = 1.6181589...
Гей, дивись на це! Менше однієї частини на 10 ^ 4 більше, ніж фі!
Нехай t (n) - час для обчислення Fib (n). Ми можемо підтримати гіпотезу, що
t(n) = phi * t(n-1)
Therefore,
t(100) = phi^(100-80) * t(80)
Я вірю, що ви можете закінчити звідси.