证明或反驳:对一个 n 位整数进行平方比将两个 n 位整数相乘要快得多

Question

证明或反驳：对n位整数进行平方比乘法渐近快 两个 n 位整数。

Answer 1

如果 x 和 y 是两个 n 位数字，则 x+y 是 n+1 位数字。((x+y(^2 - x^2 - y^2(/2 是 xy。

因此，两个 n 位数的乘法最多与 1 次加法、三次平方、两次减法和除以 2 一样昂贵。

由于加法、减法和除以 2 是 Theta(n(，这表明平方不可能渐近更快。