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 是列。

Answer 2

线性时间记为 O(N)。由于 (M+N) 是一个线性函数，因此也应该简单地记为 O(N)。同样，将 O(1) 与 O(2)、O(10) 等进行比较是没有意义的，它们都是常数时间，都应该记为 O(1)。

Answer 3

我知道这是一个旧线程，但是当我现在正在研究这个时，我想我会为那些目前正在搜索类似问题的人添加两分钱。

我认为 O(n+m) 在表示为adjacency list的图的上下文中正是如此，并且由于以下原因不能更改：

1) O(n+m) = O(n) + O(m)，但 O(m) 的上限为 O(n^2)，因此 O(n+m) = O(n) + O( n^2) = O(n^2)。然而，这纯粹是关于 n 的，也就是说，它只考虑顶点并给出一个弱的上限（弱是因为它试图用顶点表示边）。这确实表明 O(n) 不等于 O(n+m)，因为与顶点相比，边的数量可能是二次的。

2) 说 O(n+m) 考虑了在实现一种算法时必须通过的所有元素，这种算法被简化为广度优先搜索(BFS) 之类的算法。由于它只考虑一次图中的所有元素，因此可以认为它是线性的，并且是一种更严格的分析，比用 n^2 限制边的上限。为了符号的缘故，可以写出类似 n = |V| 的东西。+ |E| 因此 BFS 的运行时间为 O(n)，并给读者一种线性的感觉，但通常，正如 OP 所提到的，它写为 O(n+m)，其中 n= |V| 和 m = |E|。

非常感谢，希望这对某人有所帮助。