a**********0
发帖数: 422 | 1 请问怎么做？ 我看了一篇小文 会做了 觉得挺有意思的 |
a**********0
发帖数: 422 | 2 更正 说错了 仍然不是constant time
【在 a**********0 的大作中提到】
: 请问怎么做？ 我看了一篇小文 会做了 觉得挺有意思的
|
b*******r
发帖数: 361 | |
d**********x
发帖数: 4083 | 4 impossible. best running time is O(logn).
【在 a**********0 的大作中提到】
: 请问怎么做？ 我看了一篇小文 会做了 觉得挺有意思的
|
s*********o
发帖数: 14 | 5 there is a formula to calculate nth element, is that what you mean? |
d**********x
发帖数: 4083 | 6 put aside these math tricks...
we can actually make a lookup table... because Fn is same order as 2^n, so..
..
【在 a**********0 的大作中提到】
: 请问怎么做？ 我看了一篇小文 会做了 觉得挺有意思的
|
e***l
发帖数: 710 | |
d**********x
发帖数: 4083 | 8 well. the idea is, formula with irrational number is not accurate when you
calculate it in computer. (which is not that true. for F1-F30, it is
accurate enough)
and, with the 'n' parameter in the formula, it still needs O(logN) time to
evaluate.
I think OP was talking about the matrix solution in fact.
【在 e***l 的大作中提到】
: 这么多人不知道有通项公式?
|
a**********0
发帖数: 422 | 9
【在 s*********o 的大作中提到】
: there is a formula to calculate nth element, is that what you mean?
|
a**********0
发帖数: 422 | 10 对 可以使用类似公式的东西 可以用矩阵的SVD乘方的方法计算
但问题是需要计算常数的乘方 所以不算constant time
【在 s*********o 的大作中提到】
: there is a formula to calculate nth element, is that what you mean?
|
s***e
发帖数: 403 | 11 Fibonacci在特定条件下可以O(1)计算。通过模板元编程进行编译期计算即可。 |
i******t
发帖数: 22541 | |
