為了聯盟
2019-2-10 11:31:26
Memoization即是dp，應該每個數都要計過一次，所以O(n)
O(log n)係要用matrix multiplication or formula derived from it
Ads
為了聯盟
2019-2-10 11:35:17
O(1)有條直接揾到nth fib嘅formula
青花瓷
2019-2-10 12:01:32
又要比人壓價
:^(
Code4Food
2019-2-10 12:19:36
No, my old post in hkgolden does not cover O(1) Fibonacci. I don’t think you can do O(1) without precomputation.
Code4Food
2019-2-10 12:21:21
Not really. you can do O(log n) time and O(1) space using matrix multiplication with memorizing anything.
Code4Food
2019-2-10 12:23:54
What is the time complexity for evaluating the close for of Fibonacci numbers? How long does it take to compute a^n for an arbitrary n?
:^(
Code4Food
2019-2-10 12:51:04
I meant without memorizing, sorry
為了聯盟
2019-2-10 13:20:25
屌😂
手一黏便緊(UTC+9
2019-2-10 13:21:11
U can if you consider math is a O(1) oracle, which is not a really bad consideration as pow is slow anyway
為了聯盟
2019-2-10 13:26:01
Math.pow我記得係O(1)
Code4Food
2019-2-10 13:26:42
You cannot consider maths to be O(1). Otherwise there is no point in studying multiplication algorithms for example. You can only treat basic arithmetic operations for small numbers to be O(1) like 64 bit. Multiplying two really big numbers is not O(1) for example.
Code4Food
2019-2-10 13:40:36
Even if you restrict the range to be 64 bit, pow() may not be O(1). If you compute pow() using a Taylor series approximation with fixed number of terms, you will run into an issue with floating point rounding error. If you use matrix multiplication with integers, the best you can do is THETA(log n) multiplications.
If you restrict your Fibonacci numbers in the range representable by 64-bit integers, you cannot even compute the 100th Fibonacci number without overflow. You might just precompute and use a look up table.