0

尝试进行大 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) 算法找到数组中的最大元素:迭代数组一次,同时跟踪迄今为止看到的最大元素。

于 2012-11-09T18:56:15.280 回答