常見(jiàn)算法
邏輯思維
對(duì)于無(wú)序數(shù)組排序，最優(yōu)的時(shí)間復(fù)雜度是什么
歸并排序 ，用php寫(xiě)出一個(gè)實(shí)際的例子
一個(gè)有序數(shù)組中，查詢特定item是否存在的最優(yōu)算法是什么，時(shí)間復(fù)雜度是什么
二分查找法? o(log2n)
請(qǐng)寫(xiě)出常見(jiàn)的排序算法，并用php實(shí)現(xiàn)冒泡排序，將數(shù)組按照 從小到大的方式進(jìn)行排序
那個(gè)算法最快
歸并排序? 快速排序 同樣快 但是 快速排序不穩(wěn)定? 歸并排序是理想算法
冒泡排序原理和實(shí)現(xiàn)
算法的概念
解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令 表示一個(gè)或多個(gè)操作
一個(gè)問(wèn)題可以有多重算法，每種算法都有不同效率
一個(gè)算法具有五個(gè)特征:
有窮性 可以計(jì)算完不然是死循環(huán)
確切性? 每一步都要有意義
? 輸入項(xiàng) 1+100
輸出項(xiàng)? 有結(jié)果
可行性 每一步都是正確的
1+2+3+n? n(n+1)/2(Sn=(a1+an)*n*d/2,d是公差（相鄰2數(shù)之間的差），a1是首項(xiàng)，an是末項(xiàng)，n是項(xiàng)數(shù).這是個(gè)等差數(shù)列.)
時(shí)間復(fù)雜度和空間復(fù)雜度的概念
算法評(píng)定
算法分析的目的在于選擇合適算法和改進(jìn)算法
一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮
時(shí)間復(fù)雜度
執(zhí)行算法所需要的計(jì)算工作量，一般來(lái)說(shuō)，計(jì)算機(jī)算法是問(wèn)題規(guī)模n的函數(shù)f(n)，算法的時(shí)間復(fù)雜度也因此記做 T(n)=O(f(n))
問(wèn)題的規(guī)模n越大，算法執(zhí)行的時(shí)間的增長(zhǎng)率與 f(n)的增長(zhǎng)率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time? Complexity）
時(shí)間復(fù)雜度計(jì)算方式
得出算法計(jì)算次數(shù)公式
用常數(shù)1來(lái)取代所有時(shí)間中的所有加法常數(shù)
在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
如果最高階存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)
平（立方階 ）o(n^2) 雙/三重循環(huán)? 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)? ? 如果最高階存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù) 如 是 n^2+n+1? 只保留最高階層
線性階 o(1)? 只要次數(shù)是常數(shù)都用1來(lái)替代? o(1) 用常數(shù)1來(lái)取代所有時(shí)間中的所有加法常數(shù)
常數(shù)階? o(n)? 計(jì)算次數(shù)? 如 1+2+3+n? 得出算法計(jì)算次數(shù)公式
對(duì)數(shù)階 o(log2n)
while($n>=1){
$n=$n/2;
}
n/(2^m)=1
2^m=n
m=log2n
O(2^n)
20? n? ? ?
10? n/2
5? ? n/2/2
2.5 n/2/2/2
1? ? n/2/2/....
效率 O(1)>O(log2n)>O(n)>O(nlog2n)>O(n^2)>O(n^3)>O(2^n)>O(n!)>O(n^n)
最壞情況，最壞情況時(shí)的運(yùn)行時(shí)間，一種保證，如果沒(méi)有特別說(shuō)明，說(shuō)的時(shí)間復(fù)雜度即為最壞的時(shí)間復(fù)雜度
平均情況，期望運(yùn)行的時(shí)間
空間復(fù)雜度
算法需要消耗的內(nèi)存空間，記做 S(n)=o(fn)
包括程序代碼所占用的空間，輸入數(shù)據(jù)所占用的空間和輔助變量所占用的空間這三個(gè)方面
計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般用復(fù)雜度的漸進(jìn)性來(lái)表示
有時(shí)用空間換區(qū)時(shí)間
冒泡排序的元素交換 空間復(fù)雜度O(1)--只會(huì)有一個(gè)臨時(shí)變量
常見(jiàn)的排序算法
冒泡排序
原理:兩兩相鄰的數(shù)進(jìn)行比較，如果反序就交換，否則就不交換
時(shí)間復(fù)雜度 最壞? O(n^2) 平均 O(n^2)
空間復(fù)雜度? O(1)
//冒泡排序
$arr=array(8,2,11,1);
for($i=0,$c=count($arr);$i<=$c;$i++){
? ? for($j=0;$j<$c-1;$j++){
? ? ? ? if($arr[$j]>$arr[$j+1]){//判斷數(shù)組大小，顛倒位置
? ? ? ? ? ? $temp=$arr[$j+1];
? ? ? ? ? ? $arr[$j+1]=$arr[$j];
? ? ? ? ? ? $arr[$j]=$temp;
? ? ? ? }
? ? }
}
dump($arr);
直接插入排序
原理:每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序
時(shí)間復(fù)雜度 最壞? O(n^2) 平均 O(n^2)
空間復(fù)雜度? O(1)
希爾排序
原理:將待排序的數(shù)據(jù)根據(jù)增量分成幾個(gè)子序列，對(duì)子序列進(jìn)行插入排序，知道增量為1.直接進(jìn)行插入排序，增量的排序，一般是數(shù)組的長(zhǎng)度的一般，再變?yōu)樵瓉?lái)增量的一般，知道增量為1
時(shí)間復(fù)雜度 最壞? O(n^2) 平均O(n*log2n)
空間復(fù)雜度? O(1)
選擇排序
原理：每次從待排序的數(shù)組元素中選出最小(或最大)的一個(gè)元素，存放在序列的起始位置，知道全部待排序的數(shù)據(jù)元素排完
時(shí)間復(fù)雜度 最壞? O(n^2) 平均 O(n^2)
空間復(fù)雜度? O(1)
快速排序
原理 ；通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按照此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸完成
時(shí)間復(fù)雜度 最壞? O(n^2) 平均O(n*log2n)
空間復(fù)雜度? O(n) 平均O(log2n)
堆排序
原理 把待排序的元素按照大小在二叉樹(shù)位置上排列，排序好的元素要滿足，父節(jié)點(diǎn)的元素要大于等于子節(jié)點(diǎn)，這個(gè)過(guò)程就做對(duì)話過(guò)程，如果分界點(diǎn)存放的是最大的數(shù)，則叫做大根堆，如果是最小，就叫小根堆，可以把根節(jié)點(diǎn)拿出來(lái)，然后再堆化，循環(huán)到最后一個(gè)節(jié)點(diǎn)
時(shí)間復(fù)雜度 最壞? O(nlog2n)平均O(nlog2n)
空間復(fù)雜度? O(1)
歸并排序(最理想算法)V? -》快速排序V
原理:將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)有序的子序列 再把有序的子序列合并為整體有序序列
時(shí)間復(fù)雜度 最壞? O(nlog2n)平均O(nlog2n)
空間復(fù)雜度? O(n)
常見(jiàn)的查找算法
二分查找
原理:從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，搜索結(jié)束，如果某一個(gè)特定元素大于或者小于中間元素，則在數(shù)組大于或者小于中間元素的那一半中查找 而且跟開(kāi)始一樣從中間開(kāi)始比較 如果某一步驟數(shù)組為空 代表找不到
時(shí)間復(fù)雜度 最壞? O(log2n)平均O(log2n)
空間復(fù)雜度? 迭代O(1) 遞歸o(log2n)
順序查找
按一定的順序檢查數(shù)組中每一個(gè)元素，直到找到所要尋找的特定值為止
時(shí)間復(fù)雜度 最壞? O(n)平均O(n)
空間復(fù)雜度? O(1)
總結(jié)，二分查找算法的時(shí)間復(fù)雜度最差是O(log2n),順序查找的時(shí)間復(fù)雜度最差為o(n),所以二分查找法更快，但是遞歸情況下，二分查找法更消耗內(nèi)容，時(shí)間復(fù)雜度為O(log2n)
