Py算fib二分递归解的时间复杂度是？

Question

我写的

def recursive_function_cache(func):
     cache = dict()
  
     def wrapper(*args, **kwargs):
         parameters = (tuple.__repr__(args), dict.__repr__(kwargs))
         if parameters not in cache:
             cache.update({parameters : func(*args, **kwargs)})
         return cache.__getitem__(parameters)  #返回缓存的函数值
  
     return wrapper
  
def Fibonacci_sequence_06 (n: int) -> int:  #参数n是表示求第n项Fibonacci数
     assert isinstance(n, int), 'n is an error of non-integer type.'
     @recursive_function_cache
     #@profile
     def Calculate_Fibonacci_sequence (n: int) -> int:
         '返回单项的二分递归解法'
         if n>=3:
             if (n & 1) == 0:  #当n为偶数项
                 one_half_fib_n = Calculate_Fibonacci_sequence(n >> 1)
                 one_half_fib_n_minus_one = Calculate_Fibonacci_sequence((n >> 1) - 1)
                 return ((one_half_fib_n_minus_one << 1) + one_half_fib_n) * one_half_fib_n
             else:  #当n为奇数项
                 return Calculate_Fibonacci_sequence(n >> 1) ** 2 + Calculate_Fibonacci_sequence((n >> 1) + 1) ** 2
         elif n in (1, 2):
             return 1
         elif n==0:
             return 0
  
     if n>=0:
         return Calculate_Fibonacci_sequence(n)
     else:
         return None
  
Fibonacci_sequence_06(10000000)

算第1千万项用了3秒，耗时是矩阵法的100倍
我看时间复杂度是log(n)的。查看是递归调用了59次
可怎么大数时候跟矩阵法实测时间差那么多
什么地方隐藏着高复杂度

Answer 1

时间复杂度确实是log(n)
慢是因为 Python内置的大数运算太慢了
具体见 https://www.jianshu.com/p/9d1...