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 回実行します。

2 番目のループは、j= 1 からまで実行されiます。n * (n - 1) / 2 回実行されるため、

O(n^2)。

3 番目のループは if 文の後ろにあります。したがって、最良のシナリオでは実行されず、最悪のシナリオでは常に実行されます。3 番目のループは、2 番目のループの実行ごとに n 回実行されます。

したがって、O(n^3) は最悪のケースです (毎回 true と評価される場合)。

n が 11 だとしましょう。

最初のループは 10 回実行されます。

2 番目のループは (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) 回、つまり 10 * 9 / 2 = 45 回実行されます。

二次関数が最大であるため、これは 1/2 * 10^2 - 5 -> O(n^2) です。

if が常に true と評価される場合、最も内側のループが実行されます。

45 & 10 回 = 450 = 1/2 * 10^3 - 50 -> O(n^3)、3 乗係数が最大。

于 2013-09-23T08:39:13.330 に答える
2

この種の質問に対して、あなたができる最善のことは、表を描くことです. いくつかの数を考えて
みましょう。最悪のシナリオのために、が常に満たされていると仮定しましょう。nif

  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秒を得るでしょう：

(1日)array[j+1]いつの間にj==i==n-1

(2回目)array[k]いつk==n.

で別のものを取得しArrayIndexOutOfBoundsExceptionます。array.length < narray[j]

于 2013-09-26T09:41:14.497 に答える