algorithm - 两个n位数字相加的运行时间分析

Question

我想看看两个数字相加的时间复杂度是多少。这里写成加法是 n 平方。 Algo Notes

第 4 页第二段。

现在，如果我采用 99 + 99，因为我将执行两个加法运算和两个进位运算 + 将上一个结果的进位添加到新结果并合并所有内容。

我不确定我怎么能说这是 n 平方。

这让我觉得我应该用二进制来表示数字，这将使 01100011 变成 8 位，这将导致 8 次加法加上 4 次进位加法。这看起来像 n 平方，但我不确定。

是否有不同的方式来看待这个问题？它怎么样？您可以对每个数字运行一个循环并添加位置，即 10*sum+100*sum 等，但我可以在一个 for 循环中很好地完成此操作。

Answer 1

你提到的句子说:

Addition isn’t free, either. Adding two n-digit numbers takes O(n) time, so the running time of the iterative algorithm is O(n ²).

我将您第一次阅读文本时可能错过的相关单词加粗了。

“迭代算法”指的是前几页中讨论的其他内容的算法，而不是将两个 n 位数字相加。