抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

斐波那契数列

题目 一:求斐波那契数列的第n项。
写一个函数, 输入n, 求斐波那契 (Fibonacci) 数列的第n项。 斐波那契数列的定义如下:

解法一:递归 O(2^N)

public static long fibonacci(int n){
if (n<=0){
return 0;
}
if (n==1){
return 1;
}
return fibonacci(n-1)+fibonacci(n-2);
}

这个很好理解,看上去也很清晰,直接套公式即可,但是效率上存在大量重复劳动。见图:

在这棵树中有很多节点是重复的, 而且重复的节点数会随着n的增大而急剧增加, 这意味着计算晕会随着n的增大而急剧增大。

解法二:使用循环 O(n)

public static long fibonacci(int n) {
int[] result = {0, 1};
if (n > 0 && n < 2) {
return result[n];
}
long pre = 0;
long next = 1;
long cur = 0;
for (int i = 2; i <= n; i++) {
cur = pre + next;

pre = next;
next = cur;
}
return cur;
}

这个代码看起来也很容易理解,这个版本相比较递归版本的优化在于:

把已经得到的数列中间项保存起来,在下次需要计算的时候我们先杳找一下,如果前面已经计算过就不用再重复计算了。

解法三:时间复杂度为 O(logn) 该解法涉及到数学知识:

代码如下:

int[][] matrix=new int[2][2];

private int[][] muliMatrix(int[][] m1, int[][] m2){
int[][] res0=new int[2][2];
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
res0[i][j]=0;
for(int k=0; k<2; k++){
res0[i][j] += m1[i][k]*m2[k][j];
}
}
}
return res0;
}

private int[][] matrixPower(int[][] mat, int p){
int[][] tmp=mat;
int[][] res1=new int[2][2];
for(int i=0; i<2; i++){
res1[i][i]=1;
}
res1[0][1]=0;
res1[1][0]=0;
for( ; p != 0; p >>= 1){
if((p&1)!=0){
res1 = muliMatrix(res1,tmp);
}
tmp = muliMatrix(tmp,tmp);
}
return res1;
}

private int fibonacci(int n) {
if(n<1) {
return 0;
}
if(n==1 || n==2) {
return 1;
}
int[][] base = {{1,1},{1,0}};

int[][] res= matrixPower(base, n-2);

int result= res[0][0] + res[1][0];
return result;
}

其实我也还没搞明白,后面再回过头来看看。这里推荐一个辅助文章:点我跳转CSDN


0条评论

发表评论