java - 使用 'fib(N) = [Phi^N – phi^N]/Sqrt[5]' 公式计算 Fibonacci 项的时间复杂度是多少？

标签 java algorithm math time-complexity fibonacci

<分区>

Fibonacci 的正常递归是 Fib(N)= Fib(N-1)+Fib(n-2)，其时间复杂度为 2^N。为了降低时间复杂度，我们有以下公式:

Fib(N) = [Phi^N – phi^N]/Sqrt[5] Source

其中 Phi= (1 + Sqrt[5])/2 和 phi = (1-Sqrt[5])/2; 或 phi=Phi-1 Source

我的java代码如下:

import java.util.*;
import java.lang.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println(fib(50)+"");
    }
    
    static long fib(int N){
        final double sqrtFive=Math.sqrt(5);
        double Phi=(sqrtFive+1)/2;
        double phi=Phi-1;
        double fibN=(Math.pow(Phi,N)-Math.pow(phi,N))/sqrtFive;
        return (long) fibN;
    }
}

我的代码的时间复杂度是多少？

O(1)? because modern computer are superfast in computation so Math.pow(base,power) will be almost constant for any power.

O(logn+logn) means O(logn)? because I'm doing Math.pow(Phi,N)-Math.pow(phi,N) and Math.pow() function takes logN time.

我很困惑，请帮帮我。

最佳答案

时间复杂度是根据迭代次数计算的。这种计算斐波那契的方法实际上是 O(1)，因为所有事情都是在 1 次迭代中完成的，没有进行任何递归或循环。

编辑: 如果您只调用此 fibonacci 方法几次，则 pow() 操作的运行时间无关紧要。但是，调用方法越多，您也必须考虑 pow() 的运行时间。但就大 O 表示法而言，我会说这是 O(1)

关于java - 使用 'fib(N) = [Phi^N – phi^N]/Sqrt[5]' 公式计算 Fibonacci 项的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/71900017/