[TOC]
## 算法的概念
基本概念
個問題可以有多種算法,每種算法都不同的效率一個算法具有五個特征:有窮性、確切性、輸入項、輸出項、可行性
## 時間復雜度和空間復雜度的概念
算法評定
算法分析的目的在于選擇合適算法和改進算法一個算法的評價主要從時間復雜度和空間復雜度來考慮
### 時間復雜度
執行算法所需要的計算工作量。一般來說,計算機算法是問題規模n的函數f(n),算法的時間復雜度也因此記做`T(n)=O(f(n))`
問題的規模n越大,算法執行的時間的增長率與f(n)的增長率正相關,稱作漸進時間復雜度( Asymptotic Time Complexity)
#### 時間復雜度計算方式
o(n^2)、O(1)、O(n)?
如果 n 的數未知 那么復雜度就是`O(n)`,
如果 n 個數,但是支取前三個,則不用`O(3)`,而是用`O(1)`,括號里為常數則多為1
- 得出算法的計算次數公式
- 用常數1來取代所有時間中的所有加法常數
- 在修改后的運行次數函數中,只保留最高階項
如`O(n^2+n+1)`則只要 `O(n^2)`
- 如果最高階存在且不是1,則去除與這個項相乘的常數
#### 舉例
常數階:`O(1)`
線性階:`O(n)`
平(立)方階:`O(n^2)`或`o(n^3)`
```
由于是循環了n 的平方 所以其復雜度 為 O(n^2)
for($i=1;$i<=$n;$i++){
for($j=1;$j<=$n;$j++){
$sum +=$
}
}
```
特殊平方階:`o(n^2/2+n/2)->o(nA2)`
```
// 其復雜度 為 `O(n^2+n+1) -> O(n^2)
for(){
for(){}
}
for(){}
echo $n
```
對數階`O(log(2n))`;
```
while($n >=1)(
$n=$n/2
}
n(2^m)=1 -> 2^m=2 -> m=log(2n) -> O(log(2n))
```
常見時間復雜度:常數階、線性階、平方階、立方階、對數階、
nlog2n階、指數階
`O(1)>O(log2n)>O(n)>O(nlog2n)>O(n^2)>(n^3)>O(2^n)>O(n!)>O(n^n)`
#### 空間復雜度
算法需要消耗的內存空間,記作`S(n)=O(f(n))`
包括程序代碼所占用的空間,輸入數據所占用的空間和輔助變量所占用的空間這三個方面
計算和表示方法與時間復雜度類似,一般用復雜度的漸近性來表示
有時用空間換取時間
冒泡排序的元素交換,空間復雜度O(1),因為要加的數永遠只有一個
### 排序算法
#### 冒泡排序
原理:兩兩相鄰的數進行比較,如果反序就交換,否則不交換時間復雜度:最壞`(O(n^2),平均(O(n^2)`
如: 對,1,2,3,4,5,6進行 排序
#### 直接插入排序
原理
每次從無序表中取出第一個元素,把它插入到有序表的合適位置,使有序表仍然有序
時間復雜度:最壞(O(n^2),平均(O(n^2)
空間復雜度:O(1)
#### 希爾排序
原理
把待排序的數據根據增量分成幾個子序列,對子序列進行插入排序,直到增量為1,直接進行插入排序;增量的排序,一般是數組的長度的一半,再變為原來增量的一半,直到增量為1
時間復雜度:最差(O(n^2)),平均(O(n(log2n)
空間復雜度:O(1)
#### 選擇排序
原理
每次從待排序的數據元素中選岀最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數據元素排完
時間復雜度:最壞(O(n^2),平均(O(n^2)
空間復雜度:O(1)
#### 快速排序
原理
通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然后再按照此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸完
成
時間復雜度:最差(O(n^2),平均(O(n(log2n)
空間復雜度:最差(O(n),平均(O(log2n)
#### 堆排序
原理
把待排序的元素按照大小在二叉樹位置上排列,排序好的元素要滿足:父節點的元素要大于等于子節點;這個過程叫做堆化過程,如果根節點存放的是最大的數,則叫做大根堆,如果是最小,就叫小根堆,可以把根節點拿出來,然后再堆化,循環到最后一個節點
時間復雜度:最差(O(n(log2n),平均(O(nl(og2n)
空間復雜度:O(1)
#### 歸并排序
原理
將兩個(或兩個以上)有序表合并成一個新的有序表,即把待排序序列分為若干個有序的子序列,再把有序的子序列合并為整體有序序列
時間復雜度:最差O(n(log2n),平均(O(n(log2n)
空間復雜度:O(n)
## 查找算法
### 二分查找
原理:從數組的中間元素開始,如果中間元素正好是要查找的元素,搜索結束,如果某一個特定元素大于或者小于中間元素,則在數組大于或者小于中間元素的那一半中查找,而且跟開始一樣從中間開始比較,如果某一步驟數組為空,代表找不到。
時間復雜度:最差(O(log2n),平均(O(log2n)
空間復雜度:迭代(O(1))、遞歸(O(log2n))
### 順序查找
原理:按一定的順序檢查數組中每一個元素,直到找到所要尋找的特定值為止。
時間復雜度:最差(O(n),平均(O(n))
空間復雜度:O(1)
