大O分析.非负数组中的最大整数

Question

试图做大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];
}

谢谢

Answer 1

是的,假设元素是随机选择的,平均为O(n ²).在最坏的情况下,您将每个元素与每个其他元素进行比较.

该算法不是最优的.可以使用简单的O(n)算法在数组中找到最大元素:迭代数组一次,同时跟踪到目前为止看到的最大元素.