-4

このアルゴリズムの複雑さを知りたいです。私の場合、良い、中、最悪の両方がO（n ^ 2）です

public char getModa(char[] a){
   int ii[] =new int[a.length];
   char[] t= new char[a.length];

   for(int i=0;i<a.length;i++){
    for(int j=0;j<a.length;j++){
       if(a[j]==a[i]){ 
          ii[i]++;
          t[i]=a[j];
       }
     }
   }
   int cc=0;
   for(int i=0;i<ii.length;i++){
     if(ii[i]>ii[cc]) cc=i;
   }
   return a[cc];
 }
4

4 に答える 4

5

すべてのケース (最良/平均/最悪) の複雑さはO(n^2)であり、ボトルネックは での 2 回の繰り返し(i,j)ですrange([0,a.length),[0,a.length))。

最後のループがボトルネックの側に「ネスト」されていないため、実際にそうであり、そうではO(n^2)ない理由を明確にするために、3つのループの複雑さは基本的に ですが、これが答えです。O(n^3)O(n^2+n)O(n^2+n) = O(n^2)

実際、同じ長さの配列の場合、バリエーションはまったくありません。入力が正確に何であるかに関係なく、アルゴリズムの反復回数は同じです。

于 2013-01-23T12:41:56.997 に答える
1

あなたのコンプレックスはO(N^2)

Hash TableO(N)を使用すると、同様の問題が複雑に解決される場合があります。

于 2013-01-23T12:56:31.943 に答える
1

ネストされた for ループ内のコードは (a.length)^2 回実行され、最後の for ループ内のコードは ii.length = a.length 回実行されます。したがって、合計で (a.length)^2 + a.length 反復があり、O(a.length^2) になります。

反復の量 (および複雑さ) は、a の値ではなく、a のサイズのみに依存します。そのため、最良のシナリオでも最悪のシナリオでも同じです。

于 2013-01-23T12:45:06.647 に答える
0

for ループは、配列の長さに直接依存しますa。

だからO(n*n)、すべての場合で。

最後の for ループはプログラムの複雑さに影響しません.O(n*n)

于 2013-01-23T12:44:41.007 に答える