当我们说时间复杂度是O（M + N）时，这意味着什么？

是不是等于说当我们说时间复杂度是O（M + N）时，这意味着什么？

O(max(M,N))?

我学习的时间复杂度和这种类型的复杂性的出现时间和再次graphs.I不完全明白他们的意思

O(M+N),

其中M =边数 N =顶点数。

来源

2013-06-23 Aravind

不要问这个问题，请尝试使用定义来证明它是真实的。如果你不能这样做，请尝试证明它是错误的。如果一切都失败了，你可以在这里或另一个论坛上发布你的尝试（计算机科学堆栈交换或数学堆栈交换也许？）。但我认为，如果你只是看看Big-Oh的定义，你会发现它确实很快（当然，在你对严格定义有一些基本的了解之后）。 – rliu

此外，他们倾向于说'O（M + N）'的原因是因为它是一个更紧密的界限，也更清晰。它通常意味着“我们处理线性时间的边和顶点”，而'O（M）'会给你一个印象，即算法可能完全忽略顶点。它也有帮助，因为图算法实现经常在性能上有很大差异。如果你的图很稀疏（例如'| M |'很小），那么你可能不会在意在时间复杂度中存在'O（M^2 * ...）'因素（即你更喜欢'O M^2 * logN）'vs'O（M * N）'尽管前者渐近地变慢）。 – rliu

是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)相同。

来源

2013-06-23 11:01:38 dasblinkenlight

不失一般性？我会说你在谈论一个上限。如果图很稀疏会怎么样？ – TheEmeritus

@TheEmeritus无所谓：两个数字“M”和“N”中的一个会更大，另一个会更小，或者它们会相等。如果您最初标记为“N”的那个恰好较大，您可以将其重新标记为“M”。 – dasblinkenlight

@TheEmeritus为了跟上dasblinkenlight的回复，他指的是：http://en.wikipedia.org/wiki/Without_loss_of_generality。这意味着证据在其他情况下基本上仍然是相同的（通常是因为您可以像我们在这里看到的那样重命名变量）。我实际上并不喜欢这个证明，因为它并不真正涉及Big-Oh的定义，并且取决于Big-Oh的传递性，当它不是真的需要时（即它对我感觉迂回）。但是对于偶然的目的，我认为这已经足够清楚 – rliu

假设你有N顶点，边的数量可以变化（N^2之间0到，如果它是一个有向图，并0和(N^2)/2之间，以其他方式）。这就是为什么当给出答案时，你也有N和M。当然，你可以说O(M+N) = O(max(M,N))，但随便的说法是O(M+N)。

来源

2013-06-23 11:00:08 TheEmeritus

当我们说时间复杂度是O（M + N）时，这意味着什么？

回答

相关问题