php 常用算法和时间复杂度

 更新时间:2013年07月01日 15:30:52   作者:   我要评论
本篇文章是对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);

相关文章

  • 浅谈php扩展imagick

    浅谈php扩展imagick

    imagick是一个可以供PHP调用ImageMagick功能的PHP扩展。使用这个扩展可以使PHP具备和ImageMagick相同的功能。
    2014-06-06
  • 由php中字符offset特征造成的绕过漏洞详解

    由php中字符offset特征造成的绕过漏洞详解

    这篇文章主要给大家介绍了关于由php中字符offset特征造成的绕过漏洞的相关资料,文中不仅详细介绍了该漏洞的形成,更重要的是介绍了修复方式,对大家具有一定的参考学习价值,需要的朋友们下面来一起看看吧。
    2017-07-07
  • PHP程序员最常犯的11个MySQL错误小结

    PHP程序员最常犯的11个MySQL错误小结

    对于大多数web应用来说,金沙国际官网都是一个十分基础性的部分。如果你在使用PHP,那么你很可能也在使用MySQL—LAMP系列中举足轻重的一份子。
    2010-11-11
  • php实现保存submit内容之后禁止刷新

    php实现保存submit内容之后禁止刷新

    这篇文章主要介绍了php保存submit内容之后禁止刷新的具体实现,需要的朋友可以参考下
    2014-03-03
  • WordPress中用于获取及自定义头像图片的PHP脚本详解

    WordPress中用于获取及自定义头像图片的PHP脚本详解

    这篇文章主要介绍了WordPress中用于获取及自定义头像图片的PHP脚本编写方法,分别为get_avatar()和alt标签的使用,需要的朋友可以参考下
    2015-12-12
  • PHP 中文乱码解决办法总结分析

    PHP 中文乱码解决办法总结分析

    总之一句话,要解决PHP中文乱码最好最快的解决办法就是,页面申明的编码与金沙国际官网内部编码一致,如果页面申请的页码与金沙国际官网内部编码不一致时,就设定连接编码,mysql_query(”SET NAMES XXX”); XXX为连接编码.一定可以解决乱码的问题.
    2009-07-07
  • php版微信自定义回复功能示例

    php版微信自定义回复功能示例

    这篇文章主要介绍了php版微信自定义回复功能,结合完整实例形式分析了php版微信自定义回复功能的设置与代码实现技巧,需要的朋友可以参考下
    2016-12-12
  • PHP MemCached高级缓存配置图文教程

    PHP MemCached高级缓存配置图文教程

    memcache是一个高性能的分布式的内存对象缓存系统,它能够用来存储各种格式的数据,包括图像、视频、文件以及金沙国际官网检索的结果等。
    2010-08-08
  • PHP读取word文档的方法分析【基于COM组件】

    PHP读取word文档的方法分析【基于COM组件】

    这篇文章主要介绍了PHP读取word文档的方法,较为详细的分析了COM组件的开启、属性设置及基于COM组件打开并读取word文档的操作技巧,需要的朋友可以参考下
    2017-08-08
  • PHP简单实现定时监控nginx日志文件功能示例

    PHP简单实现定时监控nginx日志文件功能示例

    这篇文章主要介绍了PHP简单实现定时监控nginx日志文件功能,涉及php定时读取nginx服务器日志以及基于curl的数据传输相关操作技巧,需要的朋友可以参考下
    2018-06-06

最新评论