當我們說時間複雜度是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）時，這意味着什麼？

回答

相關問題