피보나치 분석 -이 솔루션은 log (n) 또는 (m (n) * log n) 시간 복잡도입니까?

Question

저는 최근에 인터뷰를 위해 공부했으며 피보나치 시퀀스 질문의 컴퓨팅에 대해 생각해 냈습니다. Wikipedia Rosetta 페이지에서이 솔루션을 발견했습니다. 그들은 O (log (n)) 시간에 그것을 계산한다고 주장한다. 그러나 그것은 O (m (n) * log n)가되지 않을 것입니다. 여기서 m (n)은 두 자리 숫자 n을 곱한 시간입니다. 나는 그것이 O (log n) 산술 연산이라고 이해하지만, 또한 O (log n) 시간이라고 생각하지 않는다. 이 가정에서 맞습니까, 아니면 완전히 혼란입니까? 누군가 나를 위해 이것을 분명히 할 수 있습니까?

public class fibonacci { 

public static long fib(long n) { 
    if (n <= 0) 
    return 0; 

    long i = (int) (n - 1); 
    long a = 1, b = 0, c = 0, d = 1, tmp1,tmp2; 

    while (i > 0) { 
    if (i % 2 != 0) { 
      tmp1 = d * b + c * a; 
     tmp2 = d * (b + a) + c * b; 
     a = tmp1; 
     b = tmp2; 
    } 

     tmp1 = (long) (Math.pow(c, 2) + Math.pow(d, 2)); 
     tmp2 = d * (2 * c + d); 

     c = tmp1; 
     d = tmp2; 

     i = i/2; 
    } 
    return a + b; 
} 
} 

Answer 1

먼저 짝수 및 홀수 번호의 치료 누락 else가 :

여기에 코드입니다. 둘째, (과잉과 같이) 수를 제곱하기 위해 힘 함수를 사용하는 것은 바람직하지 않습니다.

하지만 큰 정수에 대해 가변 숫자 라이브러리를 사용하면 합계가 정확합니다. 그러면 다중 숫자 곱셈의 비용이 본질적으로 지정된 형식의 런타임에 영향을줍니다.