-1 
for (int i=0; i<N; i++)
 for (int j=i; j<N; j++)
  fun1(i,j);

上面是一个嵌套的 for 循环。第一个 for 循环从 0 到 N，第二个 for 循环从 i 到 N。上面代码的时间复杂度是多少？

编辑：fun1 是 o(1)

4

5 回答 5

5

O(n²*O(乐趣))。显然，答案取决于乐趣的复杂性。

编辑：由于 fun() = O(1)，复杂循环复杂度为 O(n²)

于 2012-06-12T16:36:19.363 回答
2

循环数如下 1+2+3+...+N 即 N * (N + 1)/2 = N^2/2 + N/2。因此，时间复杂度为 O(N^2/2 + N/2) = O(N^2)

于 2012-06-12T16:46:06.607 回答
1

因为fun1()是常数时间，所以循环的复杂度是 O(N^2)

于 2012-06-12T16:40:27.823 回答
1

外部 for 循环将运行内部 for 循环 N 次。

内部 for 循环将在外部循环的第一个循环中调用 fun1(i,j) N 次。然后在外部 for 循环的第二个循环中执行 (N-1) 次。然后 (N-2) 次，然后 (N-3) 次，依此类推，直到 fun1(i,j) 只运行一次时外部循环的第 N 个循环 (i = N-1)。因此，我们在内部循环的每次迭代中平均运行 fun1(i,j) 次 N/2 次。

因此假设 fun1(i,j) 的复杂度为 O(fun1(i,j))，我们得到的总复杂度为 O(n * (n/2) * O(fun1(i,j))) = O( n^2/2 * O(fun1(i,j))) 但是由于我们可以忽略 N 的大值的数值常数来衡量复杂性，因此代码的复杂性顺序将为O(n^2 * O(fun1(我，j）））

由于 fun1(i,j) 是常数时间O(fun1(i,j)) = O(1)并且您的代码的复杂性将为O(n^2)

他可以在这个选择排序算法中看到一个类似的例子。请参阅选择排序算法。在这里，而不是你的 fun1(i,j) 一个简单的赋值行 'index_of_min = y;' 已使用，但这就像您的示例一样，可能会有所帮助。

于 2012-06-12T16:54:01.790 回答
0

内部循环的主体执行N + (N - 1) + (N - 2) + ... + 3 + 2 + 1次数

因此N + (N - 1) + (N - 2) + ... + 3 + 2 + 1 <= N * N循环体将运行次数增加O(n^2)

代码的总时间增长将取决于fun1 (). 如果fun1 ()时间增长，O(fun1)则fun1 ()执行O(N^2)次数将是：O(n^2 * O (fun1 ()))

编辑

正如您所编辑fun1 ()的O(1)那样，总复杂性是O(n^2 * O (fun1 ())) = O(n^2)

于 2012-06-12T16:36:42.433 回答