常見算法總結(jié)
php 算法
算法是我們遇到復(fù)雜問題時，處理程序的利器。說到算法，我們先來理解算法復(fù)雜度，其實(shí)算法復(fù)雜度是一個概念，一定程度上反映一個算法的好壞程度。算法復(fù)雜度分為兩個部分，時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度反應(yīng)算法執(zhí)行的時間長短，空間復(fù)雜度反應(yīng)是算法占用內(nèi)存(或叫存儲空間)的大小。 必須說一下，所謂的復(fù)雜度，不是一個具體的值，只是一個估值，在比較兩種算法優(yōu)劣時使用。
1、時間復(fù)雜度
時間復(fù)雜度就是是一個函數(shù)，這個函數(shù)含有兩個變量，一個算法的運(yùn)行時間，一個算法要處理數(shù)據(jù)的數(shù)量。這里有一個關(guān)系：處理數(shù)據(jù)的數(shù)量越大，算法運(yùn)行的次數(shù)和時間越長。假設(shè)處理數(shù)據(jù)的數(shù)量是n，算法運(yùn)行的次數(shù)就是f(n)。這里的f()是一個函數(shù)，它的大小隨著n增大而增大，數(shù)學(xué)上叫單調(diào)遞增函數(shù)。
所以，在計算時間復(fù)雜度T(n)的時候，步驟如下： 1、先要拿出算法的基本單元。 2、根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)f(n)。 3、找出T（n）的同數(shù)量級，將這個同數(shù)量等級賦值給f(n)。 4、因?yàn)門(n)/f(n)求極限可以得到一個常數(shù)C。（求極限值是高等數(shù)學(xué)內(nèi)容，自行百度腦補(bǔ)一下），我們可以確定時間的復(fù)雜度T(n) = O(f(n));
總結(jié)：常用的時間復(fù)雜度所耗費(fèi)的時間從小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。
2、空間復(fù)雜度
空間復(fù)雜度是指算法在內(nèi)存內(nèi)所需要的存儲空間的度量，一般是指除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。和時間復(fù)雜度類似，這樣標(biāo)記：S(n)=O(f(n))。n為問題規(guī)模，f(n)為語句關(guān)于n所占存儲空間的函數(shù)；
3、PHP冒泡排序法
PHP
$arr = array();
for($i=0;$i<10000;$i++){
$arr[] = mt_rand(1,100000);
}
$t1 = microtime(true);
//這是一個中間變量
$temp=0;
//我們要把數(shù)組，從小到大排序
//外層循環(huán)
$flag=false;//這個優(yōu)化之后效率會很高，一般夠用
for($i=0;$i<count($arr)-1;$i++){
for($j=0;$j<count($arr)-1-$i;$j++){
//說明前面的數(shù)比后面的數(shù)大，就要交換
if($arr[$j]>$arr[$j+1]){
$temp=$arr[$j];
$arr[$j]=$arr[$j+1];
$arr[$j+1]=$temp;
$flag=true;
}
}
if(!$flag){
//已經(jīng)是有序了
break;
}
$flag=false;
}
$t2 = microtime(true);
echo $t2 -$t1;
算法部分代碼平均運(yùn)行時間(php 5.6): 11.246428012848 冒泡算法的平均時間復(fù)雜度為：O(n2)
4、PHP選擇排序法
選擇排序法思路： 每次選擇一個相應(yīng)的元素，然后將其放到指定的位置
PHP
//實(shí)現(xiàn)思路 雙重循環(huán)完成，外層控制輪數(shù)，當(dāng)前的最小值。內(nèi)層 控制的比較次數(shù)
$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++){
//假設(shè)$i就是最小的數(shù) 是需要參與比較的元素
$minVal=$arr[$i];
//記錄我認(rèn)為的最小數(shù)的下標(biāo)
$minIndex=$i;
for($j=$i+1;$j<count($arr);$j++){
//說明我們認(rèn)為的最小值，不是最小
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;
算法部分代碼平均運(yùn)行時間 6.1832849979401 快速排序法平均時間復(fù)雜度：O(n2)
5、插入排序法(小到大排序)
效率又比 選擇排序法要高一些 插入排序法思路：將要排序的元素插入到已經(jīng) 假定排序號的數(shù)組的指定位置
PHP
$arr=array();
for($i=0;$i<10000;$i++){
$arr[] = mt_rand(1,100000);
}
$t1 = microtime(true);
//先默認(rèn)下標(biāo)為0的這個數(shù)已經(jīng)是有序
for($i=1;$i<count($arr);$i++){
//$insertVal是準(zhǔn)備插入的數(shù)
$insertVal=$arr[$i];
//準(zhǔn)備先和誰下標(biāo)為$inserIndex的比較
$inserIndex=$i-1;
//如果這個條件滿足，說明我們還沒有找到適當(dāng)?shù)奈恢?
while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){
//同時把數(shù)后移
$arr[$inserIndex+1] = $arr[$inserIndex];
$inserIndex--;
}
//插入（這時就給$inserIndex找到適當(dāng)?shù)奈恢茫?
$arr[$inserIndex+1] = $insertVal;
}
$t2 = microtime(true);
echo $t2 -$t1;
算法部分代碼平均運(yùn)行時間 2.6323339939117 插入法的平均時間復(fù)雜度：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) {
//先判斷是否需要繼續(xù)進(jìn)行
$length = count($arr);
if($length <= 1) {
return $arr;
}
//如果沒有返回，說明數(shù)組內(nèi)的元素個數(shù) 多余1個，需要排序
//選擇一個標(biāo)尺
//選擇第一個元素
$base_num = $arr[0];
//遍歷 除了標(biāo)尺外的所有元素，按照大小關(guān)系放入兩個數(shù)組內(nèi)
//初始化兩個數(shù)組
$left_array = array();//小于標(biāo)尺的
$right_array = array();//大于標(biāo)尺的
for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
//放入左邊數(shù)組
$left_array[] = $arr[$i];
} else {
//放入右邊
$right_array[] = $arr[$i];
}
}
//再分別對 左邊 和 右邊的數(shù)組進(jìn)行相同的排序處理方式
//遞歸調(diào)用這個函數(shù),并記錄結(jié)果
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
//合并左邊 標(biāo)尺 右邊
return array_merge($left_array, array($base_num), $right_array);
}
算法部分代碼平均運(yùn)行時間 0.055506944656372 快速排序法的平均時間復(fù)雜度：O(n*log2n)
