language-agnostic - 具有两个独立内部循环的循环的大 O 复杂度

Question

我有一个函数，它依赖于三个变量T、N和M。循环如下：

for each t from 0 to T {
    for each n from 0 to N {
         process(n,t);
    }
    for each m from 0 to M {
         process(m,t);
    }
}

它的大 O 运行时复杂度是多少？我在想O(T*Max(n,m))，但这是标准吗？谢谢！

Answer 1

是的，这是正确的。和它一样O(T*(m+n))。这是“标准” - 很难说，但max似乎更经常使用。

Answer 2

分析这一点的一种方法是通过确定外部循环执行的次数并将其乘以循环体完成的工作量来查看循环的所有迭代中完成的工作总量。为此，我们将由内而外地工作。

从内部开始，请注意第一个循环运行 O(N) 次，并且在每次迭代中都做了一些工作（我假设它是 O(1) 工作，但如果不是这样，可以修改此分析）。因此，这个循环做了 O(N) 的工作。类似地，第二个循环确实 O(M) 工作。因此，循环体完成的工作总量为 O(M + N)。由于顶层循环运行 O(T) 次，每次迭代做 O(M + N) 工作，完成的工作总量为 O(T(M + N)) = O(TM + TN)。

您声称这等于 O(T max{M, N}) 也是正确的。一种查看方法如下：注意 N = O(max{M, N}) 和 M = O(max{M, N})，因此我们有

O(TM + TN)

= O(T max{M, N} + T max{M, N})

= O(2T 最大{M, N})

= O(T max{M, N})

希望这可以帮助！