php 常用算法和时间复杂度
2015-01-24信息快讯网
本篇文章是对php中的常用算法以及时间复杂度进行了详细的分析介绍,需要的朋友参考下
按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3)//二分查找O(log2n) function erfen($a,$l,$h,$f){ if($l >$h){ return false;} $m = intval(($l+$h)/2); if ($a[$m] == $f){ return $m; }elseif ($f < $a[$m]){ return erfen($a, $l, $m-1, $f); }else{ return erfen($a, $m+1, $h, $f); } } $a = array(1,12,23,67,88,100); var_dump(erfen($a,0,5,1)); //遍历树O(log2n) function bianli($p){ $a = array(); foreach (glob($p.'/*') as $f){ if(is_dir($f)){ $a = array_merge($a,bianli($f)); }else{ $a[] = $f; } } return $a; } //阶乘O(log2n) function jc($n){ if($n<=1){ return 1; }else{ return $n*jc($n-1); } } //快速查找 O(n *log2(n)) function kuaisu($a){ $c = count($a); if($c <= 1){return $a;} $l = $r = array(); for ($i=1;$i<$c;$i++){ if($a[$i] < $a[0]){ $l[] = $a[$i]; }else{ $r[] = $a[$i]; } } $l = kuaisu($l); $r = kuaisu($r); return array_merge($l,array($a[0]),$r); } //插入排序 O(N*N) function charu($a){ $c = count($a); for($i=1;$i<$c;$i++){ $t = $a[$i]; for($j=$i;$j>0 && $a[$j-1]>$t;$j--){ $a[$j] = $a[$j-1]; } $a[$j] = $t; } return $a; } //选择排序O(N*N) function xuanze($a){ $c = count($a); for($i=0;$i<$c;$i++){ for ($j=$i+1;$j<$c;$j++){ if($a[$i]>$a[$j]){ $t = $a[$j]; $a[$j] = $a[$i]; $a[$i] = $t; } } } return $a; } //冒泡排序 O(N*N) function maopao($a){ $c = count($a); for($i=0;$i<$c;$i++){ for ($j=$c-1;$j>$i;$j--){ if($a[$j] < $a[$j-1]){ $t = $a[$j-1]; $a[$j-1] = $a[$j]; $a[$j] = $t; } } } return $a; }
/** * 排列组合 * 采用二进制方法进行组合的选择,如表示5选3时,只需有3位为1就可以了,所以可得到的组合是 01101 11100 00111 10011 01110等10种组合 * * @param 需要排列的数组 $arr * @param 最小个数 $min_size * @return 满足条件的新数组组合 */ function plzh($arr,$size=5) { $len = count($arr); $max = pow(2,$len); $min = pow(2,$size)-1; $r_arr = array(); for ($i=$min; $i<$max; $i++){ $count = 0; $t_arr = array(); for ($j=0; $j<$len; $j++){ $a = pow(2, $j); $t = $i&$a; if($t == $a){ $t_arr[] = $arr[$j]; $count++; } } if($count == $size){ $r_arr[] = $t_arr; } } return $r_arr; } $pl = pl(array(1,2,3,4,5,6,7),5); var_dump($pl);