Python之眼

问题引发

网友计算1的9999999次方，不到1s就得出答案。那python是如何处理的？

>>> a=1

>>> i=a**9999999

>>> print(i)

1

而计算2的2222222次方，python却算了将近半分钟(骁龙845平台)，

>>> a=2

>>> i=a**2222222

>>> print(i)

略去，太长

相信对于python还不太熟悉的朋友会感到很奇怪，为什么内部处理上时间差距这么大，python究竟是如何运作的呢？

问题解答

求解形如a^n的值，可以使用快速幂算法，只需要O(logn)次乘法运算。每次乘法运算的时间是与数的位数的平方成正比。

计算1^n无需考虑乘法运算的时间，所以总共只需要O(logn)的时间，几乎不需要时间。

而计算2^n需要考虑乘法运算的时间，数的位数是O(n)级别的，所以总共需要O(n^2logn)的时间。不过实际每次乘法的时候数的位数要比n小很多，所以实际运行时间还是比较快的。

ITPub博客

Python计算 1的9999999次方，不到1s就得出答案！是如何处理的？