0

Please help me finding the complexity of following code:

public static int method(int[] array, int n) {
     for (i = 1; i < n; i++)
         for (j = 1; j <= i; j++)
            if (array[j] < array[j+1])
               for (k = 1; k <= n; k++)
                    array[k] = array[k] * 2;
}

I need to know how BIG-O is calculated in best and worst case taking this code as an example

4

3 回答 3

2

最好的情况是 O(n^2) 最坏的情况是 O(n^3)。

无论如何，外部 2 个循环都会执行。

第一个循环运行i= 1 到 n。它执行 n 次。

第二个循环向上j= 1 到i. 它执行 n * (n - 1) / 2 次，这使得它

O(n^2)。

第三个循环在 if 语句后面。因此，在最好的情况下，它永远不会执行，而在最坏的情况下，它总是会执行。对于第二个循环的每次执行，第三个循环执行 n 次。

所以 O(n^3) 是最坏的情况（如果每次都评估为真）。

假设 n 是 11；

第一个循环执行 10 次。

第二个循环执行 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) 次，即 10 * 9 / 2 = 45 次。

这是 1/2 * 10^2 - 5 -> O(n^2) 因为二次函数是最大的。

如果 if 总是计算为真，最里面的循环执行：

45 & 10 次 = 450 = 1/2 * 10^3 - 50 -> O(n^3)，三次因子最大。

于 2013-09-23T08:39:13.330 回答
2

对于这类问题，你能做的最好的事情就是画一张桌子。
假设n某个数字，并且由于最坏的情况，我们假设if始终满足：

  i  |  j  |  k
-----+-----+-----
  1  |  1  |  1
  1  |  1  |  2
  1  |  1  | ...
  1  |  1  |  n
  2  |  1  |  1
  2  |  1  |  2 
  2  |  1  | ...
  2  |  2  |  n
  2  |  2  |  1
  2  |  2  |  2
  2  |  2  | ...
  2  |  2  |  n
 ..  | ..  |  ..

如果你继续这样做，你会得到一个关于“内部循环执行多少次取决于n”的直觉，你会得到它是 O(n 3 ) - 我强烈建议你在表格中填写更多的值为了更好地理解什么是复杂性。

对于最好的情况，你会假设相反（if永远不会满足），所以你会得到一个简单的嵌套循环，它将是 O(n 2 )。

于 2013-09-23T08:41:54.073 回答
0

O(n^2) 最佳情况：对于反向排序的数组；和

O(n^3) 最坏情况：对于排序数组。

一些附加说明：

java中的数组是零索引的。将计数器初始化为 1 通常是不好的做法，您应该将它们初始化为 0；否则你可能会无意中跳过array[0]。

如果array.length == n有，您将获得 2ArrayIndexOutOfBoundsException秒：

(1st) 在array[j+1]什么时候j==i==n-1

(2) 在array[k]什么时候k==n。

ArrayIndexOutOfBoundsException如果有的话，array.length < n你会得到另一个array[j]。

于 2013-09-26T09:41:14.497 回答