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.

我很困惑，请帮帮我。