爪哇第n非比波纳契数
如何在o(logn)中找到第n个非斐波那契数
非斐波那契数为:4,6,7,9,10
下面的函数给出了给定n值的非斐波那契数
static int nonFibonacci(int n){
int a=1,b=2,c=3;
while(n>0){
a=b;
b=c;
c=a+b;
n-=(a-1);
}
n+=(a-1);
return (n+b);
}
它给出了正确的答案,但我想优化它,使用矩阵乘法可以在o(logn)中找到Fibonacci数。如何应用这个属性来找到第n个非Fibonacci数
# 1 楼答案
代码段中的算法不是
O(n)
,因为斐波那契级数呈指数增长。因此,您需要O(log n)
个步骤才能获得大于n的值。以下(以及非常简单的“基准测试”)似乎证实了您的代码已经具有了正确的复杂性:输出:
如您所见,即使对于n=2^62,执行时间也只有3421纳秒,这显然不是线性的。比率
executionTime/log(n)
在最后看起来相当稳定,大约为80,这使您的解决方案成为O(n)
我认为我们在开始时观察到的变化是由于斐波那契级数的第二项。的确如此。当n很小时,
psi^n
仍然会影响结果,但因为它小于1,当n很大时,它会变得非常小,这就是为什么它在末尾是对数的,而不是在开头