## 算法 > 算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜度與時間復雜度來衡量。 ### 算法的特征 - 有窮性 算法的有窮性是指算法必須能在執行有限個步驟之后終止； - 確定性 算法的每一步驟必須有確切的定義； - 輸入 一個算法有0個或多個輸入 - 輸出 一個算法有一個或多個輸出，以反映對輸入數據加工后的結果 - 可行性 算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步 ### 時間復雜度 時間復雜度是執行算法所需要的工作量，一般來說，計算機算法是問題規模n 的函數f(n)，算法的時間復雜度也因此記做。 `T(n)=Ο(f(n))` 因此，問題的規模n 越大，算法執行的時間的增長率與f(n) 的增長率正相關 ### 空間復雜度 算法的空間復雜度是指算法需要消耗的內存空間。其計算和表示方法與時間 復雜度類似。  ### 常見算法 #### 排序算法 - [冒泡排序](https://github.com/xianyunyh/arithmetic-php/blob/master/package/Sort/BubbleSort.php) ```php function BubbleSort(array $container) { $count = count($container); for ($j = 1; $j < $count; $j++) { for ($i = 0; $i < $count - $j; $i++) { if ($container[$i] > $container[$i + 1]) { $temp = $container[$i]; $container[$i] = $container[$i + 1]; $container[$i + 1] = $temp; } } } return $container; } ``` - [插入排序](https://github.com/xianyunyh/arithmetic-php/blob/master/package/Sort/InsertSort.php) ```php function InsertSort(array $container) { $count = count($container); for ($i = 1; $i < $count; $i++){ $temp = $container[$i]; $j = $i - 1; // Init while($j >= 0 && $container[$j] > $temp){ $container[$j+1] = $container[$j]; $j--; } if($i != $j+1) $container[$j+1] = $temp; } return $container; } ``` - [希爾排序](https://github.com/xianyunyh/arithmetic-php/blob/master/package/Sort/ShellSort.php) ```php function ShellSort(array $container) { $count = count($container); for ($increment = intval($count / 2); $increment > 0; $increment = intval($increment / 2)) { for ($i = $increment; $i < $count; $i++) { $temp = $container[$i]; for ($j = $i; $j >= $increment; $j -= $increment) { if ($temp < $container[$j - $increment]) { $container[$j] = $container[$j - $increment]; } else { break; } } $container[$j] = $temp; } } return $container; } ``` - [選擇排序](https://github.com/xianyunyh/arithmetic-php/blob/master/package/Sort/SelectSort.php) ```php function SelectSort(array $container) { $count = count($container); for ($i = 0; $i < $count; $i++){ $k = $i; for ($j = $i + 1; $j < $count; $j++){ if($container[$j] < $container[$k]){ $k = $j; } } if($k != $i){ $temp = $container[$i]; $container[$i] = $container[$k]; $container[$k] = $temp; } } return $container; } ``` - [快速排序](https://github.com/xianyunyh/arithmetic-php/blob/master/package/Sort/QuickSort.php) ```php function QuickSort(array $container) { $count = count($container); if ($count <= 1) { // 基線條件為空或者只包含一個元素，只需要原樣返回數組 return $container; } $pivot = $container[0]; // 基準值 pivot $left = $right = []; for ($i = 1; $i < $count; $i++) { if ($container[$i] < $pivot) { $left[] = $container[$i]; } else { $right[] = $container[$i]; } } $left = QuickSort($left); $right = QuickSort($right); return array_merge($left, [$container[0]], $right); } ``` - 歸并排序 - 堆排序 #### 查找算法 - 順序查找 ```php function find($array ,$target) { foreach ($array as $key=>$value) { if($value === $target) { return key; } } return false; } ``` - 有序查找（二分查找） ```php function BinaryQueryRecursive(array $container, $search, $low = 0, $top = 'default') { $top == 'default' && $top = count($container); if ($low <= $top) { $mid = intval(floor($low + $top) / 2); if (!isset($container[$mid])) { return false; } if ($container[$mid] == $search) { return $mid; } if ($container[$mid] < $search) { return BinaryQueryRecursive($container, $search, $mid + 1, $top); } else { return BinaryQueryRecursive($container, $search, $low, $mid - 1); } } } ``` - 動態查找（BST） - 哈希表 O（1） ### 算法的思想 - 迭代 - 遞歸 - 動態規劃 - 回溯 - 分治 - 貪心 ### 算法相關的面試題 - 字符串 - 查找字符串中的字符 - 翻轉字符串 - 排序 - 冒泡排序 - 快速排序 - 歸并排序 - 鏈表 - 翻轉鏈表 - 鏈表有沒有環 - 二叉搜索樹 - 二叉樹的深度 - 二叉樹的遍歷 - 重建二叉樹 [《編程之法：面試和算法心得》](https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/index.html)