常见算法总结

PHP 算法
 

算法是我们遇到复杂问题时，处理程序的利器。说到算法，我们先来理解算法复杂度，其实算法复杂度是一个概念，一定程度上反映一个算法的好坏程度。算法复杂度分为两个部分， 时间复杂度 和空间复杂度。时间复杂度反应算法执行的时间长短，空间复杂度反应是算法占用内存(或叫存储空间)的大小。 必须说一下，所谓的复杂度，不是一个具体的值，只是一个估值，在比较两种算法优劣时使用。

1、时间复杂度

时间复杂度就是是一个 函数 ，这个函数含有两个变量，一个算法的运行时间，一个算法要处理数据的数量。这里有一个关系：处理数据的数量越大，算法运行的次数和时间越长。假设处理数据的数量是n，算法运行的次数就是f(n)。这里的f()是一个函数，它的大小随着n增大而增大，数学上叫单调递增函数。

所以，在计算时间复杂度T(n)的时候，步骤如下： 1、先要拿出算法的基本单元。 2、根据相应的各语句确定它的执行次数f(n)。 3、找出T（n）的同数量级，将这个同数量等级赋值给f(n)。 4、因为T(n)/f(n)求极限可以得到一个常数C。（求极限值是高等数学内容，自行百度脑补一下），我们可以确定时间的复杂度T(n) = O(f(n));

总结：常用的时间复杂度所耗费的时间从小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

2、空间复杂度

空间复杂度是指算法在内存内所需要的存储空间的度量，一般是指除正常占用内存开销外的辅助存储单元规模。和时间复杂度类似，这样标记：S(n)=O(f(n))。n为问题规模，f(n)为语句关于n所占存储空间的函数；

3、PHP冒泡排序法

PHP

$arr = array();
for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
} 
 $t1 = microtime(true); 
//这是一个中间变量 
$temp=0; 
//我们要把数组，从小到大排序 
//外层循环 
$flag=false;//这个优化之后效率会很高，一般够用 
for($i=0;$i<count($arr)-1;$i++){ 
 for($j=0;$j<count($arr)-1-$i;$j++){ 
 //说明前面的数比后面的数大，就要交换 
 if($arr[$j]>$arr[$j+1]){ 
 $temp=$arr[$j]; 
 $arr[$j]=$arr[$j+1]; 
 $arr[$j+1]=$temp; 
 $flag=true; 
 } 
 } 
 if(!$flag){ 
 //已经是有序了 
 break; 
 } 
 $flag=false; 
} 
$t2 = microtime(true); 
echo $t2 -$t1;
 

算法部分代码平均运行时间(php 5.6): 11.246428012848 冒泡算法的平均时间复杂度为：O(n2)

4、PHP选择排序法

选择排序法思路： 每次选择一个相应的元素，然后将其放到指定的位置

PHP

//实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数 
$arr=array(); 
for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
} 
$t1 = microtime(true); 
//这是一个中间变量 
$temp=0; 
for($i=0;$i<count($arr)-1;$i++){ 
 //假设$i就是最小的数 是需要参与比较的元素
 $minVal=$arr[$i]; 
 //记录我认为的最小数的下标 
 $minIndex=$i; 
 for($j=$i+1;$j<count($arr);$j++){ 
 //说明我们认为的最小值，不是最小 
 if($minVal>$arr[$j]){ 
 $minVal=$arr[$j]; 
 $minIndex=$j; 
 } 
 } 
 //最后交换 
 $temp=$arr[$i]; 
 $arr[$i]=$arr[$minIndex]; 
 $arr[$minIndex]=$temp; 
} 
$t2 = microtime(true); 
echo $t2 -$t1; 
 

算法部分代码平均运行时间 6.1832849979401 快速排序法平均时间复杂度：O(n2)

5、插入排序法(小到大排序)

效率又比 选择排序法要高一些 插入排序法思路：将要排序的元素插入到已经 假定排序号的数组的指定位置

PHP

 $arr=array(); 
 for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
 } 
 $t1 = microtime(true); 
 //先默认下标为0的这个数已经是有序 
 for($i=1;$i<count($arr);$i++){ 
 //$insertVal是准备插入的数 
 $insertVal=$arr[$i]; 
 //准备先和谁下标为$inserIndex的比较 
 $inserIndex=$i-1; 
 //如果这个条件满足，说明我们还没有找到适当的位置 
 while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){ 
 //同时把数后移 
 $arr[$inserIndex+1] = $arr[$inserIndex]; 
 $inserIndex--; 
 } 
 //插入（这时就给$inserIndex找到适当的位置） 
 $arr[$inserIndex+1] = $insertVal; 
 } 
 $t2 = microtime(true); 
 echo $t2 -$t1; 
 

算法部分代码平均运行时间 2.6323339939117 插入法的平均时间复杂度：O(n2)

6、快速排序法

PHP

$arr=array(); 
for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
} 
$t1 = microtime(true); 
$a = quick_sort($arr);
$t2 = microtime(true); 
echo $t2 -$t1;
function quick_sort($arr) { 
 //先判断是否需要继续进行 
 $ length  = count($arr); 
 if($length <= 1) { 
 return $arr; 
 } 
 //如果没有返回，说明数组内的元素个数 多余1个，需要排序 
 //选择一个标尺 
 //选择第一个元素 
 $base_num = $arr[0]; 
 //遍历 除了标尺外的所有元素，按照大小关系放入两个数组内 
 //初始化两个数组 
 $left_array = array();//小于标尺的 
 $right_array = array();//大于标尺的 
 for($i=1; $i<$length; $i++) { 
 if($base_num > $arr[$i]) { 
 //放入左边数组 
 $left_array[] = $arr[$i]; 
 } else { 
 //放入右边 
 $right_array[] = $arr[$i]; 
 } 
 } 
 //再分别对 左边 和 右边的数组进行相同的排序处理方式 
 //递归调用这个函数,并记录结果 
 $left_array = quick_sort($left_array); 
 $right_array = quick_sort($right_array); 
 //合并左边 标尺 右边 
 return array_merge($left_array, array($base_num), $right_array); 
}
 

算法部分代码平均运行时间 0.055506944656372 快速排序法的平均时间复杂度：O(n*log2n)