具有两个独立内循环的循环的大 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(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 最大{M, N} + T 最大{M, N})

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

= O(T max{M, N})

希望这可以帮助！