考虑以下在现代Intel或AMD x86_64硬件上的c代码，其中数据类型int具有32 bits:
// 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;
}
如果我们忽略递归步骤，除了ifs的分支之外，这段代码中最慢的操作将是+操作。该操作仍然可以由CPU在一个时钟周期内执行。因此，即使添加两个32 bit的整数在我们的硬件中基本上占用O(1)的时间，我们仍然应该将bigint操作称为O(n)，其中bigint是int与n-bits的组合。
说到这里，这个递归实现的两个数字相乘的base case终止于y == 0。函数调用自己(除了第一次可能切换x和y并改变一些符号的时候)最大为32 times，因为它调用自己时将y的参数设置为y >> 1。该操作将位向左移动一位，直到所有位都为0，对于32 bit int,y >> 32的最大值为0。
这是否意味着它是O(n log n)算法，用于将两个整数相乘(因为它也适用于bigints，具有相同的时间复杂度)。
为什么是O(n log n)?当调用此函数一次时，我们正在执行多个O(1)和O(n)计算。因为我们调用这个函数多达O(log n)次，所以我们将O(log n)与O(n)相乘得到O(n log n)。至少这是我的理解。
我不确定，因为所有通常的两个整数相乘的方法都需要O(n*n)步骤，只有极少数复杂的算法比这更快，请参阅:https://www.wikiwand.com/en/Multiplication_algorithm
无符号整数的简单版本:
// 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和x和y之间的混淆，这导致你错误地认为你正在做log(n)次的事情，当你实际上做了n次。所以要清楚
-
的复杂度时所关心的正常值n是您正在相乘的数字中的(最大)位数/位数。这是讨论算术运算 -
x和y是要相乘的值。所以每个字符最多有37个n位。
所以当你递归使用移位y >> 1时，你将y减半，而不是n。这只将y减少了一个位(将n减少了一个)，因此最终递归O(n)次，而不是O(log(n))
在理论乘法算法的分析中，通常将每个位运算视为一次运算，因此将res + res视为n运算，而不是1。因此，与其他理论乘法算法相比，你的算法确实是O(n log n)。
同样值得注意的是，硬件使用了第三种计数方法:计数的是晶体管，所以每一行"并行晶体管"是一个运算，所以我们在学校学习的朴素进位加法器是n行，也就是O(n)时间。巧妙的算法可以使加法的时间降低到O(log n)。