title: 计算机快速计算2^N是如何实现的？
desc: 看了大家的回答，感到十分羞愧。原来有这么强大的快速幂算法，而且打印输出耗费了很多时间。谢谢大家的回答！<br><br>-------------------------以下为原问题-------------------------<br><br><br>Python3.6，CPU仅为酷睿i5-6200U，主频2.3GHz。内存8GB。密集恐惧症慎点图片。。两秒是用手机的秒表记的<br> 估算了下，这个结果有48000位长。十进制 <br> 好奇的我又加了个0，2^10，000，000就慢多了，共用去了191秒。打开任务管理器后发现，而CPU并没有全速运行，但笔记本风扇一直呜呜呜的转着。<br> 最后，我注意到，结果中并没有出现“210，000，000
topic: Python
content: 计算乘方是有快速算法的，并不是一个一个蛮力乘上去的。比如想算2^10000，计算机先算2^5000，再算一次平方，即两个数的乘法。而为了计算2^5000，计算机会先算2^2500再算一次平方。这个算法叫快速幂算法，对于2^N的计算，如果认为每次乘法的时间复杂度是O1的话，那整体的时间复杂度只有OlogN级别。（详细一点的快速幂算法见评论） 但这里乘法的复杂度并不是O1，因为它是无限精度的，也就是所谓的大数乘法。大数乘法也有很多
answerer_tags: 讨厌实名