快速幂算法复杂度分析：乘法操作是否可按常数时间计算？

你完全可以将double乘法运算的耗时视作常数，最终该算法的时间复杂度就是O(log₂y)。

原因说明 #

• 你提到的乘法复杂度为O(n²)的结论，仅适用于任意精度的大数运算场景，比如自定义实现的大整数、高精度浮点数运算，这类场景下数值的存储位宽n会随着运算结果的量级增长而变大，乘法耗时和位宽直接相关。
• 你当前代码中使用的是Java原生double类型，属于固定长度的基础数据类型，总长度固定为64位，符合IEEE 754双精度浮点数标准，乘法运算直接由CPU硬件指令实现。题目已经明确输入不会引发溢出，所有运算过程中的中间值都在double的合法表示范围内，因此单次double乘法的耗时是固定的常数，和指数y的大小、中间结果的量级没有任何关联。
• 你的快速幂实现递归层数为⌊log₂y⌋ + 1，每一层的位运算、乘法、递归调用操作都是常数时间开销，因此整体时间复杂度就是O(log₂y)。

额外补充 #

你代码中使用无符号右移>>>处理指数的二分，对于题目中给定的正整数y来说是完全合法的，不需要额外处理负指数的边界情况。

内容的提问来源于stack exchange，提问作者super.t