回覆列表
  • 1 # 使用者7063786766555

    按數量級遞增排列,常見的時間複雜度有:常數階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);

  • 中秋節和大豐收的關聯?
  • 麗格海棠一直放有水的托盤裡不會亂根嗎?