i****y
发帖数: 84 | 1 我写了个循环，请问这个是dp吗？
num[0]=1;
for(int n =0; n
if(num[n]==0)continue;
if(n+1
num[n+1]+=num[n];
if(n+2
num[n+2]+=num[n];
}
return num[num.length-1]; |
s***5
发帖数: 2136 | |
i****y
发帖数: 84 | 3 存量个数，互相存是不是更浪费时间，我要做两次加法，是不是很慢？
【在 s***5 的大作中提到】
: 存前两个数就行，不用整个数组。
|
g****o
发帖数: 547 | 4 不差加法这点时间
你要快 fibonacci number还有 o(lgn)的算法，你可以试试
【在 i****y 的大作中提到】
: 存量个数，互相存是不是更浪费时间，我要做两次加法，是不是很慢？
|
i****y
发帖数: 84 | 5 所以我这个是对的吗？看着很蹩脚。。
【在 g****o 的大作中提到】
: 不差加法这点时间
: 你要快 fibonacci number还有 o(lgn)的算法，你可以试试
|
s*w
发帖数: 729 | 6 第一次看人把 fibo 写成这样子
有啥好处？
【在 i****y 的大作中提到】
: 我写了个循环，请问这个是dp吗？
: num[0]=1;
: for(int n =0; n: if(num[n]==0)continue;
: if(n+1: num[n+1]+=num[n];
: if(n+2: num[n+2]+=num[n];
: }
: return num[num.length-1];
|
l******n
发帖数: 9344 | 7 不适有解析表达，o(1)吗？
【在 g****o 的大作中提到】
: 不差加法这点时间
: 你要快 fibonacci number还有 o(lgn)的算法，你可以试试
|
s*w
发帖数: 729 | 8 那个所谓的解析表达也是要算 raised to the power of n, 不是 O(1)
【在 l******n 的大作中提到】
: 不适有解析表达，o(1)吗？
|
g****o
发帖数: 547 | 9 你是说用double算么？那个没法保证精度
我说的是让你算fibonacci number第1e9项 mod 1e9+7的值
这个时候应该用矩阵算
【在 l******n 的大作中提到】
: 不适有解析表达，o(1)吗？
|
s***5
发帖数: 2136 | 10 求x^n也得是最少O(lg(n))。
【在 l******n 的大作中提到】
: 不适有解析表达，o(1)吗？
|
|
|
r*********n
发帖数: 4553 | 11 不行，因为你要考虑到表达式里面的irrational number，只能用floating number来近
似，然后还要求n此幂，各种over flow，最后还要cut off回整形，很难得到正确的答
案。
【在 l******n 的大作中提到】
: 不适有解析表达，o(1)吗？
|
g****o
发帖数: 547 | 12 我以前没仔细想过这个问题
不过看这里
http://stackoverflow.com/questions/13418180/time-complexity-of-
power(double,double) 是constant time 在x86下？
【在 s***5 的大作中提到】
: 求x^n也得是最少O(lg(n))。
|
h**6
发帖数: 4160 | 13 全都跑题了，我来说一下吧。
楼主没有给num数组赋初值，循环内第一行continue应该删除。 |
l*****t
发帖数: 2019 | 14 什么意思？
数学表达是不就是什么根号5还是黄金分割什么的。根本不用loop,一个expression搞定。
【在 s*w 的大作中提到】
: 那个所谓的解析表达也是要算 raised to the power of n, 不是 O(1)
|
g****o
发帖数: 547 | 15 需要计算什么根号5的n次方啊
问题在于这个运算的复杂度是o(lgn)还是o(1)
定。
【在 l*****t 的大作中提到】
: 什么意思？
: 数学表达是不就是什么根号5还是黄金分割什么的。根本不用loop,一个expression搞定。
|
