performance - 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 = rows + cols 并说 O(N) 或者我们可以说 O(M+N) 其中 M 是行，N 是列。