如何計算算法的運行時間？

我在試圖弄清楚如何計算運行時間時看到了這段代碼。我知道這兩個for循環計算到n^2，但交換部分拋出我。我想了解交換部分是否對最壞情況下的運行時間有任何影響，這只是O(n^2)？如何計算算法的運行時間？

for(i = -1; i < N; i++) { 
    for(j = 0; j < N-1; j++) { 
     if a[j] > a[j + 1] { 
      swap(a[j], a[j + 1]) 
     } 
    } 
}

來源

2014-10-03 zerocool 18

取決於你計算的是什麼：比較或互換 - 他們的區別在於比較是恰好n^2很多，但掉期取決於你的輸入陣列（認爲這已經排序的數組 - > 0互換;也許你的任務是找到一個最佳/平均/最壞的情況下交換示例數組） – BeyelerStudios 2014-10-03 09:06:42

這是他給我們的所有代碼，沒有輸入數組。儘管他確實給了我們一些選擇。不，這不是家庭作業哈哈，這是我們在幻燈片中看到的，我被它困住了，想要弄明白，以防他在測試中給它。我認爲這是選擇2 1）* N + B + C， 2）A * N^2 + B * N + C， 3）A * N + B *日誌N + C， 4）A * N * log N + B * log N + C – 2014-10-03 09:27:06

不能爲您的老師說話，但正如我所說：交換次數取決於輸入數組。你不需要給予所述陣列，想象一下他們：有一個最好的和最壞的情況下，有許多對於一般情況下 - 互換的那些數量不同 – BeyelerStudios 2014-10-03 09:35:28

確定最壞的情況下，必須充分考慮最壞的情況下數據的設置，然後使用time命令來測量實時時間命令show你的程序的工作時間在流逝的時間而言，CPU時間（系統和用戶）

來源

2014-10-03 10:32:50

for(int i = 0; i < N-1; ++i) { 
    for(int j = 0; j < N-1; ++j) { 
     if a[j] > a[j + 1] { 
      swap(a[j], a[j + 1]); 
     } 
    } 
}

比較次數在（n-1）*（n-1）時是恆定的。交換次數取決於輸入數組。最壞的情況是反向排序的數組：{n，n-1，n-2，...，2，1}這產生n *（n-1）/ 2交換。

爲冒泡可以儘快停止作爲內環不產生交換：

for(int i = 0; i < N-1; ++i) { 
    bool hasSwap = false; 
    for(int j = 0; j < N-1; ++j) { 
     if a[j] > a[j + 1] { 
      swap(a[j], a[j + 1]); 
      hasSwap = true; 
     } 
    } 
    if(!hasSwap) 
     break; 
}

現在比較的數量也取決於所述輸入陣列上。

來源

2014-10-03 12:14:38 BeyelerStudios

最壞的情況計算複雜度爲O（n^2）如你所說，比較和交換，可以儘可能的總體複雜性而言的主項是O忽略（N^2），代碼可以

for(i = -1; i < N; i++) 
    for(j = 0; j < N-1; j++) 
    function...

你應該看看的大O簡化的規則：被重寫如下

若f（x）是幾個方面的總和，將具有最大增長費率保留，所有其他人省略。
若f（x）是幾個因素的產物，在任何常數（在不依賴於x的乘積項）被省略。

來源

2014-10-03 15:22:04

如何計算算法的運行時間？

回答

相關問題