问题引发

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

>>> a=1
>>> i=a**9999999
>>> print(i)
1

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

遇到问题没人解答？小编创建了一个Python学习交流QQ群：895817687 寻找有志同道合的小伙伴，
互帮互助,群里还有不错的视频学习教程和PDF电子书！
>>> 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小很多，所以实际运行时间还是比较快的。