当我们说时间复杂度为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,所以O(M+N)是一样的O(2*M),这又一样O(M).