最壞情況下運行時間大O

請問您能解釋一下如何才能得到這種算法的最壞情況。我正在閱讀我的教科書，並且遇到了類似這樣的算法，但仍不明白其背後的邏輯。最壞情況下運行時間大O

int t=0; 
for(int x=0;x<num.length;x++){ 
    for(int y=0;y<num.length;y++){ 
     for(int p=0;p<num.length;p++){ 
      for(int w=0;w<num.length;w++){ 
       if(num[p][w]>num[x][y]) 
       { 
        t=num[x][y]; 
        num[x][y]=num[p][w]; 
        num[p][w]=t; 
       } 
      } 
     } 
    } 
}

來源

2014-09-28 Plrr

這個邏輯非常簡單。讓我們從最內層循環開始：

此循環運行num.length次。假設爲n = num.length，其最大運行時複雜度爲big-O符號O(n)。

for(int w=0;w<num.length;w++){ 
    ... 
}

現在，當你把另一個用於循環周圍長度p，它將運行上面的for循環p倍。所以它是O(pn)。在你的情況下，p = num.length = n所以它應該是O(n*n) = O(n^2)。

在你的例子中有4個嵌套循環，所以答案是O(n^4)。

爲什麼我會忽略最內層循環的內容？由於執行的操作數量不變，請將該數字設爲c。大O符號使用的漸近分析如下：O(c) is equivalent to O(1)。這來自definition of big-O。

來源

2014-09-28 19:38:00 mostruash

怎麼樣，如果我有一個程序，而不只是一個特定的算法，「具體」在特定的「。假設我有一個程序運行（執行）不同的任務;例如，假設我有一個程序，生成然後按升序對它們進行排序，用戶被要求輸入任何數字，以使程序打印出一條消息，指定所選擇的數字是否在數組中。我必須分別評估每個語句？ – Plrr 2014-09-28 20:12:51

當每個算法不同時，如何使用不同的算法與其各自的Big O符號得出最壞情況運行時間（大O）的結論？就像程序有算法時一樣：O（n^2），O（1），O（n）....哪一個代表整個程序？ – Plrr 2014-09-28 20:17:41

@Plrr當你有多個大O.然後那個repres ent：最好情況，平均情況和最壞情況。在編程中，我們的目標是平均情況。但是，取決於您擁有的數據輸入。你可能會得到最好的情況，甚至是最壞的情況。在所有「發生最多」的情況下，都是平均情況。你處理這個很多。 – Juniar 2014-09-28 20:29:20

如果您正在比較元素爲; ==或<或>對一個列表或一個大小爲n的數組，然後最壞的情況是O（n）。

因此，一個for循環的代價是：O（n），但是你有4個for循環，每個循環的最壞情況O（n）。

總成本是：n * n * n * n =最壞情況O（n^4）。

來源

2014-09-28 20:20:12 Juniar

最壞情況下運行時間大O

回答

相關問題