2

这是代码：

int Outcome = 0;  
for (int i = 0; i < N; i++)  
    for (int j = i+2; j = 0; j--)  
        Outcome += i*j;

以下是我的分析。由于第一行是一个赋值语句，所以这恰好需要一个时间单位，O(1)。第 2 行的细分为：1 + N + N = 2N + 2。在第 3 行中，由于循环的内容是单个操作，因此循环及其块执行 i+1 操作。这也是一个嵌套的 for 循环。最后，第 4 行恰好需要一个时间单位来执行。因此，这个代码的大哦符号 N 是 O(N 2 )。

4

2 回答 2

1

确切地说：正如您所说，第 4 行是 1 次操作。对于特定的i，您执行内部循环i+3时间。因此，您的操作总数为

sum(0 <= i <= N-1 : i+3) 
    = 3N + sum(0 <= i <= N-1 : i) 
    = 3N + N(N-1) / 2
    = N^2/2 + 5N/2
    = O(N^2)
于 2013-05-25T23:17:54.007 回答
0

您对最终效率等级的直觉是正确的，但可以更加严格。首先，您通常只选择最昂贵的基本操作来计算您的分析。在这种情况下，它可能是最内层循环中的乘法，每次迭代执行一次。那么它被调用了多少次？在最外层循环的第一次迭代中，内层循环将迭代两次。在第二次外部迭代中，它将是 3 次，并且类似地达到 N+2 （我假设内部循环条件是j >= 0）。所以这给我们留下了以下总结：

sum(2, 3, 4, 5, 6 ..., N+2)
= sum(1, 2, 3, 4 ..., N+2) - 1
= (N+2)(N+3)/2 - 1

它在 O(N²) 中（实际上，因为你有这个始终相同的特定结果，你可以说它在 ϴ(N²) 中）。

于 2013-05-25T23:23:43.073 回答