Heim  >  Artikel  >  php教程  >  求一个数组中的最大值和最小值的算法改进 php 实现

求一个数组中的最大值和最小值的算法改进 php 实现

WBOY
WBOYOriginal
2016-06-06 19:46:211256Durchsuche

设计一个最优算法来查找一n个元素数组中的最大和最小。已知一种需要比较2n次的方法,请给一个更优的算法。情特别注意优化时间复杂度的常数。 主要思想:把数组两两一对分组,如果数组元素个数为奇数,就最后单独分一个,然后分别对每一组的两个数比较,把小

设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法,请给一个更优的算法。情特别注意优化时间复杂度的常数。

主要思想:把数组两两一对分组,如果数组元素个数为奇数,就最后单独分一个,然后分别对每一组的两个数比较,把小的放在左边,大的放在右边,这样遍历下来,总共比较的次数是 N/2 次;在前面分组的基础上,那么可以得到结论,最小值一定在每一组的左边部分找,最大值一定在数组的右边部分找,最大值和最小值的查找分别需要比较N/2 次和N/2 次;这样就可以找到最大值和最小值了,比较的次数为

      N/2 * 3 = (3N)/2 次


   //算法实现
   $data = array(1,2,3,2,6,5,8,5,7,9,3,2,1,59,45,34,60,10,90);
   $length =count($data);
   for($i=0 ; $i            if( isset($data[$i+1]) && $data[$i] > $data[$i+1]){
                   $temp_data = $data[$i];
                   $data[$i] = $data[$i+1];
                   $data[$i+1] = $temp_data;
          }

  }
  $min_data = $data[0];
  $max_data = $data[1];
  for($i=2;$i           if($min_data > $data[$i]) $min_data = $data[$i];
  }
  for($i=3;$i           if($max_data   }
 if($length%2!=0 && $max_data   echo $min_data,"\r\n" ,$max_data;
  ?>

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn