这种最坏情况分析是否正确？

下面是代码：这种最坏情况分析是否正确？

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 ）。

来源

2013-05-25 user2421270

听起来对我来说是正确的。做得好！ –

'x^2'是二次方程，它是在阶数'2'的'x'上的多项式。你可以说你的复杂性是'O（i * j）'和'j = O（i）'，因此你有'O（n^2）'......每当你有一个嵌套循环时，它通常是'O n^2）':) – Bill

请参阅CS上的[此依赖嵌套循环复杂性]（http://cs.stackexchange.com/questions/4590/big-o-nested-for-loop-with-dependence）问题。 – user2246674

确切地说：正如你所说，第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-25 23:17:54

您的直觉对于最终效率等级是正确的，但它可以更严格。首先，您通常会选择最昂贵的基本操作来计算您的分析。在这种情况下，它可能是最内层循环中的乘法，每次迭代都会执行一次。那么它被称为多少次？在最外层循环的第一次迭代中，内循环将迭代两次。在第二次外迭代时，它将是三次，并且类似地达到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-25 23:23:43 tsherif

复杂度等级* –

这种最坏情况分析是否正确？

回答

相关问题