常見算法總結

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)