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次可怎么大数时候跟矩阵法实测时间差那么多什么地方隐藏着高复杂度