計算乘方是有快速演算法的，並不是一個一個蠻力乘上去的。比如想算2^10000，計算機先算2^5000，再算一次平方，即兩個數的乘法。而為了計算2^5000，計算機會先算2^2500再算一次平方。這個演算法叫快速冪演算法，對於2^N的計算，如果認為每次乘法的時間複雜度是O(1)的話，那整體的時間複雜度只有O(logN)級別。
一般來說，為了實現快速冪演算法，首先把指數做二進位制表示，比如你要算A的23次方，可以把23分解為16+4+2+1。然後計算B=A^2，C=B^2=A^4，D=(C^2)^2=A^16。最終結果為ABCD相乘。
但這裡乘法的複雜度並不是O(1)，因為它是無限精度的，也就是所謂的大數乘法。大數乘法也有很多演算法，最樸素的，類似手算的方法，複雜度是O(N^2)，其他一些方法有分治法，複雜度O(N^1.58)，FFT方法，複雜度O(N logN loglogN)等。快速冪的O(logN)次大數乘法中，最複雜的只有最後一次，也就是2^5000的那次，前面的複雜度幾何級數衰減，所以整體複雜度也就是最後一次計算的複雜度。如果你用FFT方法的話，複雜度也就是比線性多了一點點，一般計算機上隨便算算就出來了。
CPU沒有全速執行是因為這個程式只用了1個核心在做計算，而你顯示的是總的使用率，所以大概會保持在四分之一的水平。
是否用到了移位操作涉及Python大數運算的具體設計，我不是很懂就不多講了。但原理上講也是很有可能的，如果用位元串儲存大數的話，那麼計算2^N只需要在陣列的第N位設定一個1，其餘設定為0即可，那麼轉換到十進位制是這段程式碼中最消耗計算量的部分。
計算乘方是有快速演算法的，並不是一個一個蠻力乘上去的。比如想算2^10000，計算機先算2^5000，再算一次平方，即兩個數的乘法。而為了計算2^5000，計算機會先算2^2500再算一次平方。這個演算法叫快速冪演算法，對於2^N的計算，如果認為每次乘法的時間複雜度是O(1)的話，那整體的時間複雜度只有O(logN)級別。
一般來說，為了實現快速冪演算法，首先把指數做二進位制表示，比如你要算A的23次方，可以把23分解為16+4+2+1。然後計算B=A^2，C=B^2=A^4，D=(C^2)^2=A^16。最終結果為ABCD相乘。
但這裡乘法的複雜度並不是O(1)，因為它是無限精度的，也就是所謂的大數乘法。大數乘法也有很多演算法，最樸素的，類似手算的方法，複雜度是O(N^2)，其他一些方法有分治法，複雜度O(N^1.58)，FFT方法，複雜度O(N logN loglogN)等。快速冪的O(logN)次大數乘法中，最複雜的只有最後一次，也就是2^5000的那次，前面的複雜度幾何級數衰減，所以整體複雜度也就是最後一次計算的複雜度。如果你用FFT方法的話，複雜度也就是比線性多了一點點，一般計算機上隨便算算就出來了。
CPU沒有全速執行是因為這個程式只用了1個核心在做計算，而你顯示的是總的使用率，所以大概會保持在四分之一的水平。
是否用到了移位操作涉及Python大數運算的具體設計，我不是很懂就不多講了。但原理上講也是很有可能的，如果用位元串儲存大數的話，那麼計算2^N只需要在陣列的第N位設定一個1，其餘設定為0即可，那麼轉換到十進位制是這段程式碼中最消耗計算量的部分。