algorithm - 当我们说时间复杂度为 O(M+N) 时，这是什么意思？

Question

是不是和说的一样

O(max(M,N))? 

我正在学习时间复杂度，这种类型的复杂性一次又一次地出现在图表中。我不完全理解它们的意思

O(M+N),

其中 M = 边数 N = 顶点数。

Answer 1

是O(M+N)一样的O(max(M,N))吗？

是的，它是一样的。不失一般性，可以这么说M >= N。因此，O(max(M,N))与 相同O(M)。同时，M < M+N < M+M, soO(M+N)与 相同O(2*M)，而 又与 相同O(M)。

Answer 2

假设您有N顶点，边的数量可能会有所不同（在0到之间N^2，如果它是有向图，在 和 之间0，(N^2)/2否则）。这就是为什么在给出答案时，你也有N和M。当然，你可以这么说O(M+N) = O(max(M,N))，但随意的说法是O(M+N)。