为什么要研究算法,算法到底有什么用?
看这道题:
已知 a+b+c=1000 且a^2+b^2=c^2 求 a、b、c 有可能出现的组合。
一般我们看到这道题,就是for循环吧
这样写:
for($a=1;$a<=1000;$a++){ for($b=1;$b<=1000;$b++){ for($c=1;$c<=1000;$c++){ if($a+$b+$c===1000 && bcpow($a,2)+bcpow($b,2)==bcpow($c,2)){ printf("a b c %d,%d,%d \n",$a,$b,$c); } } } } //三层循环嵌套,谁知道这要运行多少次的计算 1000*1000*1000=? #结果: #a+b+c=1000,且a^2+b^2=c^2 问 a b c 可能的值是: #a b c 200,375,425 #a b c 375,200,425 #[Finished in 78.4s] #----------------------------------------------------- 那么有没有改良的程序: #设 a^2+b^2=c^2 #则 a、b、b至少等于1 ,因此 减去 3 #只需要循环到997 printf("\n\na+b+c=1000,且a^2+b^2=c^2 问 a b c 可能的值是:\n"); $sum=1000; for($a=1,$num=$sum-3;$a<=$num;$a++){ for($b=1;$b<$num-$a;$b++){ $c=$sum-$a-$b; if($a+$b+$c===1000 && bcpow($a,2)+bcpow($b,2)==bcpow($c,2)){ printf("a b c %d,%d,%d \n",$a,$b,$c); } } } #a+b+c=1000,且a^2+b^2=c^2 问 a b c 可能的值是: #a b c 200,375,425 #a b c 375,200,425 #[Finished in 1.6s]
这就是算法的魅力,就这么一个循环就能看出一个程序员水平的高低。
一个执行了 78.4s 一个1.6s 这差出多少倍?
先看一道数学题吧,
1+3+5+7+9+...+100 问得多少? 从1到100的奇数相加是多少
1+2+3+4+5+6+7+...100 得多少?从1到100相加之和是多少?
2+4+6+8+...100 得多少? 从1到100的偶数相加?
当我们看到这样的题之后,最先想到的是 写一个函数,循环从1到100 相加最后返回结果
这没有错误,符合程序的规则。
那来看看如何写这个函数:
function sum($start,$end){ $sum=0; for($i=$start,$i<=$end;$i++){ $sum+=$j; } return $sum; } echo sum(1,100); //5050
看到上面的函数和执行结果,我们写完了,那是不是最佳的方式方法呢?
显然不是,我们利用数学公式看看
(1+100)*100/2 如果使用这个公式,程序运行一遍,即可得到结果。既然有这样的算法,为什么要从1到100 循环呢?
//这是我们优化后的一种写法
function sum($start,$end){ return ($start+$end)*$end/2; }
这种写法,就得说说算法了。
算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,
算法代表着用系统的方法描述解决问题的策略机制。
也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。
其实编程限制了我们的想法,只要for循环就可以了。没有想起我们学习的数学公式。
为什么要使用算法呢?
就是为了一类问题,使用快速而优的方法得到想要的答案。
同样我们看看:我们看看1到100奇数加起来是多少
//需要执行50次 ceil(100/2) //如果遇到余数,总是向上进1 for ($j = 1, $num = 0, $sum = 0; $j <= 100; $j = $j + 2) { //printf("%s\n", $j); $num++; $sum += $j; } printf("1+3+5+7+9+....+100结果是:%s\n", $sum); // 这就是算法的精髓,根据题的规律,一次执行行到结果 function jiaddSum($start, $end) { $diff = 0; if ($start > 1) { $diff = floor($start / 2); } bcmod($end, 2) == 0 && $end--; $num = ceil($end / 2); return ($start + $end) * ($num - $diff) / 2; } echo "\n"; echo jiaddSum(1, 100);
总上所述,如果不研究算法,程序会使用for循环计算很多次,时间、内存都有所消耗。
如果使用使用我们的算法,那么就会快很多,
从1到100之间的奇数计算,使用for 循环 需要计算 50次
使用计算公式: 一次执行,通过几次数学公式 就能快速计算出结果。
通过这里,得到了些什么呢?
计算机部分编程与课本中的一些公式是息息相关的,可以借鉴数学公式、数学定论 得到结果。
计算机常见的几种算法:
冒泡排序
插入排序
选择排序
快速排序
二分查找
顺序查找
冒泡排序
/** * 冒泡排序 * @param [type] $arr [description] * @return [type] [description] */ function arrSort($arr) { for ($i = 1, $len = count($arr); $i < $len; $i++) { for ($j = 0; $j < $len - $i; $j++) { if ($arr[$j] > $arr[$j + 1]) { $temp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $temp; } } } return $arr; } //冒泡排序法的改良版 //如果这是一个有序的列表,那么放在这个方法执行中,会很快的返回 //时间复杂度 O(n) function arrSrot2($data){ $len=count($data); if($len<=1) return $data; $change=false; for($i=1;$i<$len;$i++){ for($j=0;$j<$len-$i;$j++){ //判断,如果前边的一个值 大于后边的值,则进行交换 if($data[$j]>$data[$j+1]){ $temp=$data[$j+1]; $data[$j+1]=$data[$j]; $data[$j]=$temp; $change=true; } } if($change==false) break; } return $data; }
例如数组:
$arr = array(10, 2, 36, 14, 25, 23, 85, 99, 45);
数组中共计9个数, 会执行多少次排序完毕?
先看看循环的轮数 for($i=1;$i<count($arr);$i++) 也就是8轮 公式: $len-1 =8 等同于 9-1
8轮循环完毕
再看里面的循环:
当 $i=1 ,=2,=3分别里面会循环几次
$i=1 ,$j从0 开始 循环到 9-$i =8 走了 8次
$i=2 ,$j从0 开始 循环到 9-$i =7 走了 7次
$i=3 ,$j从0 开始 循环到 9-$i =6 走了 6次
$i=4 ,$j从0 开始 循环到 9-$i =5 走了 5次
$i=5 ,$j从0 开始 循环到 9-$i =4 走了 4次
$i=6 ,$j从0 开始 循环到 9-$i =3 走了 3次
$i=7 ,$j从0 开始 循环到 9-$i =2 走了 2次
$i=8 ,$j从0 开始 循环到 9-$i =1 走了 1次
当等于9的时候,for不成立,退出。
因此 走了8轮。
则:8+7+6+5+4+3+2+1=36 使用数学公式计算 (8+1)*8/2=36
因此冒泡排序法最少排序=
冒泡排序法循环次数:$len*($len-1)/2
$len=数组的长度
$arr = array(10, 2, 36, 14, 25, 23, 85, 99, 45, 88, 33, 26, 57, 56, 72); 15个数 15*(15-1)/2=105
$arr = array(10, 2, 36); 3个数 3*(3-1)/2=3
$arr = array(10, 2, 36, 14, 25); 5个数 5*(5-1)/2=10
结论:就是把相邻的两个数值比较,把最大值向后移动。
轮数: for $i=1 从1开始
$j=0;$j<$len-$i;$j++
这是核心。
时间复杂度:
最坏时间复杂度:O(n2)
最优时间复杂度:O(n)
稳定程度:稳定
插入排序
操作的是前半部分
function insertSort($arr){ for($i=1;$i<count($arr);$i++){ $j=$i; //内层循环 起始 while($j>0 && $arr[$j]<$arr[$j-1]){ $temp=$arr[$j-1]; $arr[$j-1]=$arr[$j]; $arr[$j]=$temp; $j--; } } return $arr; } $result=insertSort($arr); print_r($result);
从后往前 去比较 ,比较过程中,如果前边一个值小于后天这个值,则跳出循环
while($j>0 && $arrr[$j]<$arr[$j-1]){
//只有j>0 且 $j < $j-1 才执行数据交换。
}
我们数据交换的时候,使用list() 这个方式进行交换,效率会怎么样????
时间复杂度:
最坏时间复杂度:O(n2)
最优时间复杂度:O(n)
稳定程度:稳定
选择排序
简单直观的排序算法, 从里面找最小的值,找到后,循环,替换
重点考虑后边顺序,
默认取出第一个值为最小值, 循环
$min=$i
再一次循环,这次循环比较特殊
function selectSort($data){ $len=count($data); for($i=0;$i<$len-1;$i++){ $min=$i; for($j=$i+1;$j<$len;$j++){ if($data[$min]>$data[$j]){ $min=$j; } } $temp=$data[$min]; $data[$min]=$data[$i]; $data[$i]=$temp; } return $data; } print_r($sresult);
时间复杂度:O(n2)
稳定程度:不稳定
希尔排序
function shell_sort($data){ $len=count($data); $gap=floor($len/2); while($gap>0){ for($i=$gap;$i<$len;$i++){ $j=$i; while($j>0 && $data[$j-$gap]>$data[$j]){ $temp=$data[$j]; $data[$j]=$data[$j-$gap]; $data[$j-$gap]=$temp; $j-=$gap; } } $gap=floor($gap/2); } return $data; } $arr = array(10, 2, 36, 14, 25, 23, 85, 99, 45); printf("希尔排序法:\n%s\n",var_export(shell_sort($arr),true));
结果展示:
希尔排序法: array ( 0 => 2, 1 => 10, 2 => 14, 3 => 23, 4 => 25, 5 => 36, 6 => 45, 7 => 85, 8 => 99, )
快速排序
/** * 快速排序法 * * @desc 注意事项:for 循环开始的$key 是1 * @param [type] $arr [description] * @return [type] [description] */ function quickSort($arr) { static $quickSortNum = 0; static $lun = 0; printf("\n\n\n-----------轮数:%d\n", ++$lun); if (count($arr) <= 1) { return $arr; } $firstVal = $arr[0]; $leftArr = []; $rightArr = []; for ($i = 1; $i < count($arr); $i++) { if ($arr[$i] < $firstVal) { $leftArr[] = $arr[$i]; } else { $rightArr[] = $arr[$i]; } printf("\nquickSort执行的次数:%d >>>>数组:%s", ++$quickSortNum, var_export($arr, true)); } $leftArr = quickSort($leftArr); $rightArr = quickSort($rightArr); return array_merge($leftArr, [$firstVal], $rightArr); }
19次就排序完毕
二分查找
function erfen($arr, $val, $min = 0, $big = null) { static $num = 0; is_null($big) && $big = count($arr); if ($big < $min) { return -1; //如果找不到数据就返回-1 } //$middle = intval(($min + $big) / 2); $middle=bcdiv(bcadd($min,$big),2); printf("查找%d位置的次数:%d\n", $val, ++$num); //echo $arr[$middle]; if ($arr[$middle] == $val) { return $middle; } else if ($arr[$middle] < $val) { return erfen($arr, $val, $middle + 1, $big); } else if ($arr[$middle] > $val) { return erfen($arr, $val, $min, $middle - 1); } } echo erfen($v, 36); /** Array ( [0] => 2 [1] => 10 [2] => 14 [3] => 23 [4] => 25 [5] => 36 [6] => 45 [7] => 85 [8] => 99 ) **/
二分查找:前提必须是 有序数组
查询结果:
查找36位置的次数:1
查找36位置的次数:2
查找36位置的次数:3
可以看出 共计循环了3次
位置是:
5
如果不使用二分查找,则使用 foreach 查找法,则循环的是 6 次
顺序查找
function shunxuSort($arr,$findVal){ $result=-1; foreach($arr as $key=>$val){ if($val==$findVal){ $result=$key; break; } } return $result; }
2018-11-2练习题
<?php $arr = array(10, 2, 36, 14, 25, 23, 85, 99, 45); function quickSort($arr){ $count=count($arr); if ($count <= 1) { return $arr; } $first=$arr[0]; $left=[]; $right=[]; for($i=1;$i<$count;$i++){ $arr[$i]<$first?$left[]=$arr[$i]:$right[]=$arr[$i]; } $left=quickSort($left); $right=quickSort($right); return array_merge($left,[$first],$right); } $newarr=quickSort($arr); print_r($newarr); //冒泡 function maopao($arr){ if(count($arr)==1) return $arr; for($i=1;$i<count($arr);$i++){ for($j=0;$j<count($arr)-$i;$j++){ if($arr[$j]>$arr[$j+1]){ $temp=$arr[$j]; $arr[$j]=$arr[$j+1]; $arr[$j+1]=$temp; } } } return $arr; } print_r(maopao($arr)); function erfen($arr,$val,$min=0,$big=null){ if(empty($arr)) return $arr; is_null($big) && $big=count($arr); if ($big < $min) { return -1; } //$middle=intval(bcadd($min,$big)/2); $middle=bcdiv(bcadd($min,$big),2); if($arr[$middle]==$val){ return $middle; }else if($arr[$middle]<$val){ return erfen($arr,$val,$middle+1,$big); }else{ return erfen($arr,$val,$min,$middle-1); } } $findval=45; $newdata=maopao($arr); printf("查找数组%s中%s的索引值是%s\n\n",var_export($newdata,true),$findval,erfen($newdata,$findval)); function insertSort($arr){ if(count($arr)<=1){ return $arr; } for($i=1;$i<count($arr);$i++){ $j=$i; while($j>0 && $arr[$j]<$arr[$j-1]){ $temp=$arr[$j]; $arr[$j]=$arr[$j-1]; $arr[$j-1]=$temp; $j--; } } return $arr; } print_r(insertSort($arr));
2018-12-3练习排序法
$arr = array(10, 2, 36, 14, 25, 23, 85, 99, 45); //插入排序 function insertSort($data){ $len=count($data); if($len<=1) return $data; for($i=1;$i<$len;$i++){ $j=$i; while($j>0 && $data[$j-1]>$data[$j]){ $temp=$data[$j-1]; $data[$j-1]=$data[$j]; $data[$j]=$temp; $j--; } } return $data; } printf("原始数组展示:\n%s\n",var_export($arr,true)); printf("插入排序法:\n%s\n",var_export(insertSort($arr),true)); //选择排序 function selectSort($data){ $len=count($data); for($i=0;$i<$len-1;$i++){ $min=$i; for($j=$i+1;$j<$len;$j++){ if($data[$min]>$data[$j]){ $min=$j; } } $temp=$data[$min]; $data[$min]=$data[$i]; $data[$i]=$temp; } return $data; } printf("选择排序法:\n%s\n",var_export(selectSort($arr),true)); //希尔排序 function shell_sort($data){ $len=count($data); $gap=floor($len/2); while($gap>0){ for($i=$gap;$i<$len;$i++){ $j=$i; while($j>0 && $data[$j-$gap]>$data[$j]){ $temp=$data[$j]; $data[$j]=$data[$j-$gap]; $data[$j-$gap]=$temp; $j-=$gap; } } $gap=floor($gap/2); } return $data; } printf("希尔排序法:\n%s\n",var_export(shell_sort($arr),true));