0

Big O分析を行おうとしています-このプログラムの平均的なケースは何ですか？O（n / 2（n / 2））= O（n ^ 2）？..

 /* Returns the largest integer in the array */
 int CompareToAll(int array[], int n)
 {

   int  i, j;
   bool isMax;/* Make sure that there is at least one element in the array.*/                        

   if (n <= 0) return -1;

   for (i = n-1; i > 0; i--) 
   {
      isMax = true;
      for (j = 0; j < n; j++) {

        /* See if any value is greater.*/
         if (array[j] > array[i]){
             isMax = false;  /* array[i] is not the largest value. */
             break;
          }
      } /* If isMax is true, no larger valueexists; array[i] is max. */

      if (isMax)
        break;
   }
   return array[i];
}

ありがとうございました

4

1 に答える 1

8

はい、要素がランダムに選択されていると仮定すると、平均してO（n 2 ）です。最悪の場合、すべての要素を他のすべての要素と比較します。

このアルゴリズムは最適ではありません。単純なO（n）アルゴリズムを使用して、配列内の最大要素を見つけることができます。これまでに見られた最大要素を追跡しながら、配列を1回繰り返します。

于 2012-11-09T18:56:15.280 に答える