O(M + N)是什么意思？

Question

这是一个基本问题......但我认为O(M + N)与O(max(M,N))相同,因为当我们进入无穷大时,较大的项应该占主导地位？而且,这与O(min(M,N))不同,是吗？我一直看到这种符号,尤其是 在讨论图算法时.例如,您经常看到:O(| V | + | E |)(例如,http://algs4.cs.princeton.edu/41undirected/).

Answer 1

是的,O(M + N)意味着与O(max(M,N))相同.这与O(min(M,N))不同.正如@Dr_Asik所说,O(M + N)在技术上是线性O(N)但是当M和N有意义时,能​​够说"线性在什么？"是很好的.想象一下,算法的行数和列数是线性的.我们可以定义N =行+ cols并说O(N)或者我们可以说O(M + N)其中M是行而N是列.