algorithm - O(m+n) 和 O(mn) 之间的区别？

Question

我试图通过不同的方法找出算法的复杂性。在数学上，我遇到了一种 O(m+n) 和另一种 O(mn) 方法。但是我无法理解或说形象化这一点。我看着他们并没有那种“啊!原来是这样”的感觉!有人可以使用他们自己的示例或任何其他工具来解释这一点吗？

Answer 1

O(m+n) 示例:

for(int i = 0, i < m, i++)
    //code
for(int j = 0, j < n, j++)
    //code

m 代码迭代发生。然后发生 n 次代码迭代。

O(mn) 示例:

for(int i = 0, i < m, i++)
    for(int j = 0, j < n, j++)
        //code

对于 m 的每次迭代，我们都有 n 代码迭代。想象一下迭代一个非正方形二维数组。

m 和 n 不一定等于相同的值。如果它们确实 等于相同的值，则对于 O(m+n):

O(m+n) => O(m+m) => O(2m) => O(m)

我建议查看 this question/answer为了理解最后的转变。

对于O(mn):

O(mn) => O(mm) => O(m^2)