大O計算

int maxValue = m[0][0];   
for (int i = 0; i < N; i++) 
{    
    for (int j = 0; j < N; j++) 
    {     
     if (m[i][j] >maxValue)   
     {     
      maxValue = m[i][j];  
     }      
    }     
}     

cout<<maxValue<<endl;   

int sum = 0;     
for (int i = 0; i < N; i++)  
{     
    for (int j = 0; j < N; j++)  
    {     
     sum = sum + m[i][j];    
    }     
} 

cout<< sum <<endl;

對於上述代碼我得到O（N 2），作爲執行時間增長他們方式我得到它是由：大O計算

MAX [O（1），O（N 2）， O（1），O（1），O（n2），O（1）]

O（n2）都用於循環。這個計算是否正確？

如果我改變了代碼：

int maxValue = m[0][0]; 
int sum = 0; 
for (int i = 0; i < N; i++)   
{      
    for (int j = 0; j < N; j++)   
    {      
    if (m[i][j] > maxValue)  
     {     
     maxValue = m[i][j];  
     }    
     sum += m[i][j]; 
    }     
} 

cout<<maxValue<<endl; 
cout<< sum <<endl;

不過大O是O（n2）的對不對？那麼這是否意味着Big O只是根據輸入數據大小如何增長時間的指示？而不是如何寫算法？

來源

2012-04-29 sYl3r

這感覺有點像一門功課的問題給我，但是......

大哦是關於算法，以及具體怎麼執行的步數（或使用的內存量）算法隨着輸入數據的增長而增長。

在你的情況下，你將N作爲輸入的大小，並且它很混亂，因爲你有一個二維數組NxN。所以真的，因爲你的算法只需要對這個數據進行一兩次遍歷，你可以把它稱爲O（n），在這種情況下，n是二維輸入的大小。

但是要回答你的問題的核心，你的第一個代碼會對數據進行兩次傳遞，而你的第二個代碼在一次傳遞中完成相同的工作。然而，Big-Oh的想法是它應該給你增長的訂單，這意味着獨立於特定計算機的運行速度。所以，可能是我的電腦比你的電腦快兩倍，所以我可以在運行第二個代碼的同時運行你的第一個代碼。所以我們想忽略這些差異，並說這兩種算法都會對數據進行固定次數的傳遞，所以就「增長順序」而言，一次傳遞，兩次傳遞，三次傳遞都沒有關係。這與一次傳球完全相同。

不考慮NxN輸入可能更容易想到這一點。考慮一下N個數字的列表，並說你想對它做點什麼，比如找到最大值，或者對列表進行排序。如果列表中有100個項目，則可以在100個步驟中找到最大值，如果您有1000個項目，則可以以1000個步驟完成。所以增長的順序是線性與輸入的大小：O（n）。另一方面，如果你想對它進行排序，你可以編寫一個算法，在每次找到下一個要插入的項目時對數據進行大致的遍歷，並且對於每個元素列表，所以這是n遍過你的長度爲n的列表，所以這就是O（n^2）。如果列表中有100個項目，則大概需要10^4個步驟，如果列表中有1000個項目大概需要10^6個步驟。所以這個想法是，這些數字與您的輸入大小相比增長速度非常快，所以即使我的計算機速度更快（例如，比您的模型好10年的模型），我也許能夠在即使列表2或10甚至100或1000倍也是最大的問題。但對於O（n^2）算法的排序問題，當我試圖列出長度爲100或1000倍的列表時，即使計算機比使用10或20年的計算機更好，我也無法擊敗您你的。這就是Big-Oh的想法，它將這些「相對不重要」的速度差異分解出來，並且能夠看到給定算法在給定輸入大小下的更一般/理論意義上的工作量。

當然，在現實生活中，一臺電腦比另一臺電腦快100倍會對您產生巨大影響。如果您試圖通過固定的最大輸入大小解決特定問題，並且您的代碼以1/10的速度運行，而您的老闆要求的速度更快，並且您的新計算機運行速度提高了10倍，則無需解決問題需要編寫更好的算法。但重要的是，如果你想處理更大（更大）的數據集，你不能等待更快的計算機。

來源

2012-04-29 09:31:03

是的，這是關於作業，我已經做到了這一點，並希望得到一些關於Big-O的更多見解（其實第二個代碼是由我完成的）。如果沒關係，你能否說有可能比可能的執行路徑的數量有更多的Macabe複雜性。因爲這個代碼正在發生。 – sYl3r 2012-04-29 12:08:41

是的，在這兩種情況下都是O（N^2）。當然O（）的時間複雜度取決於你如何編寫算法，但是上面的兩個版本都是O（N^2）。但是，請注意，實際上N^2是您的輸入數據的大小（它是一個N×N矩陣），所以這可以更好地表徵爲線性時間算法O（n），其中n是輸入的大小，即n = N x N.

來源

2012-04-29 09:09:01

big O表示法是基於輸入大小執行算法所花費的最大時間的上限。因此，基本上兩種算法的最大運行時間可能會略有不同，但符號相同big O表示法。

您需要了解的是，對於運行時間函數，基於輸入大小的線性函數將具有大的符號o（n），並且二次函數總是具有大的符號o（n^2）。

所以如果你的運行時間只是n，那就是一個線性通過，大o表示保持o（n），如果你的運行時間是6n + c，那就是6個線性通過和一個恆定時間c，它仍然是o （N）。

現在在上述情況下，第二個代碼更加優化，因爲跳轉到循環內存位置所需的次數更少。因此這會給予更好的執行力。但是這兩個代碼的運行時間仍然是o(n^2)。

來源

2012-04-29 09:12:39

回答

相關問題