我能够使用Binet公式(即封闭解公式)来计算斐波那契数，在恒定时间内计算任何通常可计算的斐波那契数(除非结果变大)。这是我的代码:
对于非递归的fibonnaci实现:
gr = (1 + 5**0.5) / 2
def gfib(n):
return int(((gr**n - (1-gr)**n) / 5**0.5))
我知道a ^ n表示指数级的运行时复杂度，但是当代码在python中运行时情况并非如此，因为这会立即计算第n个斐波那契数。我已经进行了一些有关如何在python中实现指数的研究(也许是通过平方来求幂？)，以给出我得到的恒定时间解决方案，但尚未找到明确的答案。有任何想法吗？
最佳答案
float.__pow__()方法使用C的libm，它充分利用了对二进制浮点算术的硬件支持。后者使用对数表示数字。对数表示使得仅需一个乘法就可以实现指数运算。
执行摘要:浮点数是在硬件中实现的，由于对数的魔力，它几乎以恒定的速度运行。
关于python - 如何在Python中实现幂运算？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12377632/