Java实现俄罗斯农民乘法代码的时间与空间复杂度分析

核心实现代码 #

int num1 = Integer.parseInt(jTextField1.getText());
int num2 = Integer.parseInt(jTextField2.getText());

int res = 0;
// 当第二个数大于0时持续计算
while (num2 > 0)
{
    // 第二个数为奇数时，把当前第一个数累加到结果
    if ((num2 & 1) != 0)
        res = res + num1;

    // 第一个数乘2（左移1位），第二个数整除2（右移1位）
    num1 = num1 << 1;
    num2 = num2 >> 1;
}
jTextField3.setText(String.valueOf(res));

时间复杂度 #

• 循环的每一轮都会对num2做右移1位操作，相当于每次把num2的二进制表示长度减少1位，直到num2变为0终止循环。
• 循环内部的按位与判断、加法、移位操作全是常数时间就能完成的操作，耗时不会随输入数值变化。
• Java的int是固定32位的有符号整数，不管初始输入值多大，循环最多执行32次就会终止。从算法通用分析视角，时间复杂度为O(log n)（对数以2为底，对应输入数值的二进制位数）；针对固定长度的整型场景，也可以认为是常数时间复杂度，因为循环次数存在明确的固定上界。

空间复杂度 #

• 算法全程只额外申请了一个int类型的变量res存储计算结果，没有开辟随输入规模变化的额外内存空间。
• 前后的输入解析、UI组件取值赋值属于业务逻辑的固定开销，和算法本身的空间占用无关。
• 最终空间复杂度为O(1)，属于常数级空间占用。

内容的提问来源于stack exchange，提问作者xKD