PHP Common Algorithms and Time Complexity_PHP Tutorial-PHP Tutorial-php.cn

PHP Common Algorithms and Time Complexity_PHP Tutorial

WBOY

Release： 2016-07-21 15:01:50

Original

902 people have browsed it

Arranged in increasing order of magnitude, common time complexities are: constant order O(1), logarithmic order O(log2n), linear order O(n), linear logarithmic order O(nlog2n), square order O(n2), Cubic order O(n3)

Copy code The code is as follows:

//Binary search 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));
//Traverse the tree O(log2n)
function bianli($p){
$a = array();
foreach (glob($p.'/*') as $f){
if(is_dir($f)) {
               $a = array_merge($a,bianli($f));                                                                                                          ;
}
//Factorial O(log2n)
function jc($n){
if($n<=1){
return 1;
}else{
        return $n*jc($n-1);
    }                                                                                                                                                 > $c = count($a);
if($c <= 1){return $a;}
$l = $r = array();
for ($i=1 ;$i<$c;$i++){
                                                                                        else{
🎜> Return array_merge($l,array($a[0]),$r);
}
//Insertion sort 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] = $t;
}
return $a;
}
//Selection sort O(N*N)
function xuanze($a ){
$c = count($a);
for($i=0;$i<$c;$i++){
for ($j=$i+1;$j< $c;$j++){
                                                                                                                                                                                                                                                 = $a[$i];
                                                                                         ; Bubble sort 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];                                                  🎜>                                                                                                                                                                                                                                                                         Return $a;

/**
 * Permutation and combination 
 * Use the binary method to select combinations. For example, when choosing 3 from 5, only 3 bits are 1, so the available combinations are 10 types such as 01101 11100 00111 10011 01110. Combination
 *
 * @param Array to be arranged $arr
 * @param Minimum number $min_size
 * @return New array combination that meets the conditions 
*/
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);