现代x86 CPU上C语言递归整数乘法的O(n log n)复杂度验证

完整版本代码（支持正负整数） #

// calc x times y for any two integers values of x and y (where the result can be stored by the int datatype)
int fastMult(int x, int y) {
    /*
     * Assuming the following operators take O(n) or O(1) time:
     * ==, <, >, &&, ||, &, |, >>, -, +, ?: 
     */

    // x*0 == 0*y == 0
    if (y == 0 || x == 0) return 0;

    // (-x)(-y) == xn and (-x)y == x(-y)
    if (x < 0) return fastMult(-x, -y);

    int isNegative = y < 0; // x cannot be negative here

    // y*x is faster than x*y for bigger absolute y than x
    if (isNegative && x < -y || x < y) return fastMult(y, x);
    if (isNegative) y = -y; // handle y in a simpler way

    int res = fastMult(x, y >> 1); // called at max lb(y) times aka sizeof(y) times
    res = res + res; // one addition
    if (y & 1) res = x + res; // possible second addition

    // if y was negative, then the answer is negative
    return isNegative ? -res : res;
}

无符号简化版本代码 #

// x * y for unsigned integers of x and y
int fastMult(int x, int y) {
    if (y == 0) return 0;

    int res = fastMult(x, y >> 1);
    res <<= 1; // O(1) or O(n), doesnt matter since O(n) is below this line and 2 times O(n) is still O(n)
    if (y & 1) res += x; // O(n)

    return res;
}

时间复杂度分析结论 #

这个算法本质是二进制分解乘法（俄罗斯农民乘法），你的时间复杂度推导是正确的，具体分析如下：

前提与推导 #

• 对于n位大整数，加法操作的时间复杂度为O(n)，其余比较、移位等操作的时间开销远低于加法，可忽略
• 递归次数为O(log n)：每次递归将乘数右移1位，相当于位数减半，直到乘数变为0，总递归次数为二进制位数的对数级别
• 每次递归最多执行2次大整数加法（res + res和可选的x + res），单次递归的时间开销为O(n)

综上，总时间复杂度为O(n log n)。

与常规O(n²)乘法的区别 #

常规竖式乘法需要将乘数的每一位与被乘数相乘，再逐位累加，总操作数为O(n²)；而二进制分解乘法通过递归拆分乘数，将加法的执行次数从O(n)降到了O(log n)，因此效率更高，确实属于比常规乘法更优的算法类型。

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