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）是什麼意思？

回答

相關問題