O（M + N）是什么意思？

这是一个基本的问题......但我认为O（M + N）与O（max（M，N））是一样的，因为当我们走向无穷大时，更大的项应该占主导地位？另外，这与O（min（M，N））不同，是吗？我一直看到这个符号，尤其是。在讨论图算法时。例如，您经常会看到：O（| V | + | E |）（例如，http://algs4.cs.princeton.edu/41undirected/）。O（M + N）是什么意思？

来源

2012-08-13 Frank

是的，O（M + N）表示与O（max（M，N））相同的事物。这与O（min（M，N））不同。正如@Dr_Asik所说，O（M + N）在技术上是线性的O（N），但是当M和N有意义时，能够说“在什么时候是线性的”是很好的。想象一下，算法在行数和列数上是线性的。我们可以定义N =行+列，并说O（N）或者我们可以说O（M + N），其中M是行，N是列。

来源

2012-08-13 16:16:04

线性时间记为O（N）。由于（M + N）是一个线性函数，因此它应该简单地记为O（N）。同样，将O（1）与O（2），O（10）等进行比较也是没有意义的，它们都是不变的，并且都应该注意到O（1）。

来源

2012-08-13 16:01:12 Asik

那么，我在很多地方都会看到这个符号，包括很有信誉的人。看看：http://algs4.cs.princeton.edu/41undirected/ – Frank 2012-08-13 16:14:47

希望我的回答澄清了这一点。通过重新定义N = X + Y，您总是可以将O（X + Y）重写为O（N）。我们是否应该这样做，仅仅是因为它是“正确”的方式呢？我说“不”，但其他人可能会不同意。 – 2012-08-13 16:20:28

我明白它的意思是“线性”。这是一个很好的捷径，意思是“在主导术语”线性的“恕我直言”。 – Frank 2012-08-13 16:27:40

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

我认为，O（N + M），在表示为adjacency list的曲线图的情况下，正是并且不能被改变，原因如下：

1）O（N + M） O（n）+ O（n）= O（n）+ O（m），但O（m）的上界为O（n^2），所以O（n + m）= O N^2）。然而，这纯粹仅以n来表示，也就是说，它只考虑顶点并给出一个弱上限（因为它试图用顶点表示边）。这确实表明O（n）不等于O（n + m），因为与顶点相比，可以是二次量的边。 2）O（n + m）表示O（n + m）考虑了在实现算法时必须通过的所有元素，该算法被简化为Breadth First Search（BFS）。由于它将图中的所有元素都只考虑一次，因此可以认为它是线性的，并且是一个更严格的分析，即用n^2上边界边界。人们可以为了符号而写一些像n = | V |的东西+ | E |因此BFS运行是O（n）并且给读者一个线性感，但是一般来说，如OP所提到的，它被写为O（n + m），其中 n = | V |和m = | E |。

非常感谢，希望这有助于某人。

来源

2017-11-12 23:13:16 Pricej81

O（M + N）是什么意思？

回答

相关问题