如何計算一段代碼中每行的運行時間

我對Big O符號有點熟悉，但是我遇到了Big O符號的解釋，我無法完全理解。如何計算一段代碼中每行的運行時間

int foo(int n) { 
    int p = 1;  -------------->c1  x 1 
    int i = 1;   ------------->c1  x 1 
    while (i < n) {  ------------>c2  x n 
    int j = 1; ------------------->c1  x (n - 1) 
     while (j < i) { ----------->c2  x ((1/2)n^2 - (3/2)n + 2) 
     p = p * j; -------------->(c1 + c3) x ((1/2)n^2 - (3/2)n + 1) 
     j = j + 1; -------------->(c1 + c4) x ((1/2)n^2 - (3/2)n + 1) 
     } 
    i = i + 1; ------------------->(c1 + c4) x (n - 1) 
    } 
    return p; ---------------------->c5  x 1   
}

（C1 + 1/2 * C2 + 1/2 * C3 + 1/2 * 1 -C 4）N^2 +（-c1 - 1/2 * C2 - 3/2 * C3 - 1/2 * c4）n +（2 * c1 + 2 * c2 + c3 + c5）

我知道這個算法會變成n^2，因爲嵌套循環以及常量和低階項的減少在結果方程中。然而，我不明白的是，例如（（1/2）n^2 - （3/2）n + 1）導出了「x」的右值。任何對此的見解都將得到最多的讚賞，我真的需要了解大O符號的核心概念。謝謝。

Check here for animated explanation

來源

2012-04-12 Romaine Carter

有周期的n-1個迭代而（ⅰ< N）

腸子週期將被執行0，1，2，3，... N-2倍 - 這是等差級數，其總和是（n-2）（n-1）/ 2 =（1/2）n^2 - （3/2）n + 1

來源

2012-04-12 15:10:34 MBo

爲什麼第二個while循環執行x（（1/2）n^2 - （3/2）n + 2）及其語句執行x（（1/2）n^2 - （3/2）n + 1）。 – 2012-04-12 15:31:34

第二個循環被執行（.. + 1）次，但是它的條件（while（j MBo 2012-04-12 16:46:20

外環進行n-1倍：

sum(1, i=1;n-1) = n-1.

內環針對每個i進行i-1次，總共：

sum(i-1, i=1;n-1) 
= sum(i, i=1;n-1) - sum(1, i=1;n-1) 
= (n-1)*((n-1)+1)/2 - (n-1) 
= (n-1)*n/2 - n+1 
= (1/2)n^2-(3/2)n+1

使用公知的歐拉公式數字的總和從1到n：sum(i, i=1;n) = n*(n+1)/2

來源

2012-04-12 15:04:53 Attila

如何計算一段代碼中每行的運行時間

回答

相關問題