algorithm - 乘法算法的渐近复杂度是否仅依赖于两个操作数中较大的一个？

Question

我正在上一门算法课，当我被要求分析有乘法或除法的代码的运行时时，我反复遇到麻烦。如何找到将 n 位数字与 m 位数字相乘的 big-theta(其中 n>m)？和两个n位数字相乘一样吗？

例如，现在我正在尝试分析以下代码行:

return n*count/100

其中 count 最多为 100。它的渐近复杂度与 n*n/100 有什么不同吗？还是 n*n/n？

Answer 1

您可以随时在这里查看Computational complexity of mathematical operations .

n*count/100 的复杂度是 O(length(n))，因为 100 是一个常数，而 length(count) 最多为 3。

一般n和m位长度的两个数相乘，需要O(nm)，除法所需的时间相同。在这里，我假设我们正在谈论长除法。有许多复杂的算法可以克服这种复杂性。

为了让事情更清楚，我将提供一个例子。假设你有三个数字:

• A - n 位长度
• B - m 位长度
• C - p 位数长度

计算以下公式的复杂度:

A * B/C

先相乘。 A * B 的复杂度是 O(nm) 结果我们有数字 D，它是 n+ m 位长度。现在考虑 D/C，这里的复杂度是 O((n+m)p)，其中整体复杂度是两个 O(nm + (n +m)p) = O(m(n+p) + np).

先除法。所以，我们除法B/C，复杂度是O(mp)，我们有m个数字E。现在我们计算A * E，这里的复杂度是O(nm)。同样，总体复杂度为 O(mp + nm) = O(m(n+p))。

从分析可以看出，先划分是有好处的。当然，在现实生活中，您也会考虑数值稳定性。