c# - 大O分析。非负数组中的最大整数

<分区>

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

谢谢

最佳答案

是的，平均来说是 O(n²)，假设元素是随机选择的。在最坏的情况下，您将每个元素与其他所有元素进行比较。

这个算法不是最优的。可以使用简单的 O(n) 算法找到数组中的最大元素:遍历数组一次，同时跟踪到目前为止看到的最大元素。

关于c# - 大O分析。非负数组中的最大整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13314177/