0

（在任何人说什么之前是的，这是家庭作业，但我已经把它上交并拿回来了，我只是想弄清楚明天的测试。）

问题是计算代码片段的执行时间和大 O。我可以计算出大 O 罚款，但我不知道如何确定执行时间。好的，基本上我不明白的是如何计算执行时间 

for(i=0; i < n; i++){
    SomeJavaStatment;
    for(j=0; j < 2 * n; J+= 2){ 
        SomeJavaStatment;
        SomeJavaStatment;
}
}

正确答案是 Big O(n^2) 我猜对了，但是我不知道执行时间是多少，正确答案是 4n^2+5n+2。

如果有人能解释我将如何得到这个答案，我将不胜感激。

4

2 回答 2

7

我不认为，应该以这种方式确定执行时间，但是：

 //assignment to i takes 1 operation    
 for(i=0; i < n; i++){ // i++ is executed n times, i < n is executed (n+1) times
    SomeJavaStatment; // n times

    //assignment to j takes 1 operation
    for(j=0; j < 2 * n; j+= 2){  // j+=2 is executed n*n times, j < 2*n is executed n*(n+1) times
        SomeJavaStatment; // n * n times
        SomeJavaStatment; // n * n times
    }
 }

总共给出 1 + n + (n+1) + n + n + (n*n) + (n+1)*n + (n*n) + (n*n) = 4 * n^2 + 5*n + 2:)

于 2012-04-03T21:29:58.943 回答
0

大 O 描述了函数的上限。您的函数不仅是大 O(n^2)，而且还具有严格的界限（对于任何给定的 值n，该函数具有完全相同的运行时）。您可以手动计算精确的紧密界限，也可以将其表示为总和，结果为4n^2+5n+2.

于 2012-04-03T21:34:09.597 回答