> php教程 > php手册 > 본문

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

WBOY
풀어 주다: 2016-06-06 19:46:21
원래의
1259명이 탐색했습니다.

设计一个最优算法来查找一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;
  ?>

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 추천
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿