我需要一些關於大O的澄清

我有幾個問題，請耐心等待。我需要一些幫助來澄清大O和運行時間。據我瞭解，Big O是一種呈現算法正確運行時間的方法嗎？從閱讀中我一直在想如何計算一個算法的大O.到目前爲止，我已經想通了，這樣的事情爲O的大O（N^2）我需要一些關於大O的澄清

for(i = 0; i < N, i++) 
    for(j = 0; j < N; j++) 
     //code

但如果是這種情況發生什麼：

for(i = 0; i < N, i++) 
    for(j = 0; j < M; j++) 
     //code

其中N總不是等於M.

另外如果您將其中兩個加在一起，那麼大O又是什麼？

for(i = 0; i < N, i++) 
    for(j = 0; j < N; j++) 
     //code 
for(i = 0; i < N, i++) 
    for(j = 0; j < N; j++) 
     //code

大O等於N^2 + N^2 = 2N^2嗎？

來源

2012-05-28 Asking Questions

其中N總不是等於M.

然後，它是O(NM)，除非M取決於N，或反之亦然。如果他們是獨立的，那麼說它是O(N)和O(M)也是正確的。

大O等於N^2 + N^2 = 2N^2嗎？

O(2N^2)相當於O(N^2)。

來源

2012-05-28 19:42:30

第二個例子是O（N * M）。第三個仍然是O（N^2），因爲常數因子（2）不會改變BigO。重要的是，如果你加倍N，時間乘以4.如果你三倍N，時間乘以9.

來源

2012-05-28 19:43:46

基本上你是正確的。對於第二個它會O（N * M）。對於第三個，你也是對的，但它可以從O（N^2 + N^2）= O（2 * N^2）= O（N^2）中減少。

大哦表示法用於近似算法的運行時間。所以在這種情況下，倍增因子2幾乎不如功率係數那麼大，因此我們將其除掉。

來源

2012-05-28 19:44:50

對於前兩種情況，認識到在這種情況下Big-O只是兩個變量的函數。如果我告訴你f(x,y) = x + sin y你會說f（x）= f(x) + sin x？不，這是無稽之談。

確實是O(N*M)。如果您處於M是固定常量並且您對程序將如何執行N的情況感興趣，那麼它在N或O(N)中是線性的。但是有時候你會遇到N = M的情況，比如說你在處理一個正方形，你可以說這個函數是O(N^2)。但是對於某些konstant k或M=N沒有任何限制，如M=k，唯一準確的說法是O(N*M)。如果你告訴我這是二次方，那麼我會逆向工程，並期望N = M或某物，如果你告訴我它是線性的，我會期望它保持不變。

如果你想得到更多的理論知識，你可以注意到說O(something)永遠是廢話，直到你指定你正在工作的變量。f(N,M) = NM是O(N) w.r.t. N，O(NM) w.r.t N,M和O(N^2) w.r.t N where M=N。

如果你想得到更多的mathy ...這是維基百科或math.stackexchange.com :)

來源

2012-05-28 19:46:58 djechlin

我需要一些關於大O的澄清

回答

相關問題