下面是本人在看算法書籍時(shí)做的筆記。因?yàn)榍懊娴谋容^基礎(chǔ)，就從第五章才開始做的筆記
第五章：散列表
個(gè)人理解：概念類似于hash索引數(shù)據(jù)結(jié)構(gòu)，通過散列表函數(shù)(hash函數(shù)) 計(jì)算出int值，然后存儲(chǔ)數(shù)據(jù) - 復(fù)雜度 為 O(1)，遇到計(jì)算出同樣int值時(shí)，則將該位置 當(dāng)做鏈表來處理（沖突的概念）
1，知識(shí)點(diǎn)：
（1），散列函數(shù)總是將同樣的輸入映射到相同的索引位置
（2），散列函數(shù)將不同的輸入映射到不同的索引， 偶然情況也會(huì)將不同的輸入映射到相同的索引位置，這時(shí)將會(huì)把該索引位置當(dāng)做鏈表來處理
（3），散列函數(shù)知道數(shù)組有多大，總會(huì)返回有效的索引
（4），散列表 是無序的
2，適用場(chǎng)景：防止重復(fù)，web緩存，
3，性能：
（1），一般情況下散列表執(zhí)行各種操作的時(shí)間均為O(1)，?
O(1) 被稱為常量時(shí)間，意思指不管散列表多大，查找任意元素的時(shí)間都相同
也有最壞情況，即散列表分配不合理，所有元素都存到同一索引位置，故此時(shí)操作時(shí)間為O(n)
? ? ? ? ? ? ? ? ? 平均情況? ? ? ? ? 最糟情況
查找? ? ? ? ? O(1)? ? ? ? ? ? ? ? ? O(n)
插入? ? ? ? ? O(1)? ? ? ? ? ? ? ? ? O(n)
刪除? ? ? ? ? O(1)? ? ? ? ? ? ? ? ? O(n)
（2）查找對(duì)比
簡(jiǎn)單查找的運(yùn)行時(shí)間為 線性時(shí)間 ，復(fù)雜度為O(n)
二分法的運(yùn)行時(shí)間為 對(duì)數(shù)時(shí)間 ，復(fù)雜度為O(log n)
散列表中查找的運(yùn)行時(shí)間為 常量時(shí)間 ，復(fù)雜度為O(1)
（3）散列表，數(shù)組，鏈表 對(duì)比
? ? ? ? ? 這里不支持表格，就不列舉了
（4），避免沖突，需要 有較低的填裝因子和較好的散列函數(shù)
填裝因子： 散列表包含的元素?cái)?shù) / 位置總數(shù)
一般填裝因子超過0.7，則需要調(diào)整散列表的長(zhǎng)度，一般調(diào)整散列表的長(zhǎng)度時(shí)，增大一倍
第六章 廣度優(yōu)先搜索? (breadth first search)? BFS
1，圖算法 - 廣度優(yōu)先搜索 - 適用于解決最短路徑問題? （是否有A到B的路徑，如果有，將找到最短路徑）
圖由節(jié)點(diǎn)和邊組成， 一個(gè)節(jié)點(diǎn)可能與多個(gè)節(jié)點(diǎn)直接相連，這些節(jié)點(diǎn)被稱為鄰居
A----------------->? B? ? ? ? ? ? ? ? ? ?
A,B 叫做節(jié)點(diǎn) ，---->? 這個(gè)叫做邊
有向圖： A ---> B , A <----- B ,
無向圖： A ---- B? ? 意味著兩個(gè)節(jié)點(diǎn)彼此指向?qū)Ψ?，即環(huán)? ? A <----> B
2，隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)
? ? 棧是一種 后進(jìn)先出的 數(shù)據(jù)結(jié)構(gòu)
3，廣度優(yōu)先搜索的PHP代碼解釋：
查找你朋友中有在騰訊上班的人，如果沒有則在朋友的朋友中找，? 求最短路徑，與你關(guān)系相對(duì)最近
每個(gè)人的朋友 - 可以用散列表結(jié)構(gòu)來解決? 即? $arr['zhangsan'] = ['lisi','wangwu'];? ? $arr['wangwu'] = ['zhaoliu','songqi'];
邏輯：優(yōu)先查第一層關(guān)系的（你的朋友）
其次查第二層關(guān)系，（你朋友的朋友）
再次查第三層關(guān)系，（你朋友的朋友的朋友）
。。。。。。
知識(shí)點(diǎn)：使用到隊(duì)列，散列表。? 每個(gè)人的朋友用散列表存儲(chǔ)，查找搜索的列表 用 隊(duì)列。先進(jìn)先出
代碼表示：
首先關(guān)系表
$relation['zhangsan'] =? ['lisi','wangwu'];
$relation['wangwu'] = ['zhaoliu','songqi'];?
。。。。。
function breadth_first_search($name){
$searchList = array();? //先弄個(gè) 搜索隊(duì)列? - 該出用php數(shù)組做隊(duì)列
$searchList = array_merge($searchList, $relation[$name]);? // 把該人的朋友加入到隊(duì)列中
$searchAlready = array();? ? // 已搜索過的人，防止死循環(huán)
while($searchList){
$people = array_shift($searchList); // 彈出查找人 ，順序
if(! in_array($searchAlready)){ //未查找過
if( check_in_tencent($people) ){
return $people; // 找到了
}else{
array_push($people, $searchAlready);? // 加入已查找列表
$searchList = array_merge($searchList, $relation[$people]);? // 將該的朋友 加入搜索隊(duì)列中
}
}
}
return "";? //沒找到
}
function check_in_tencent($name){
// 隨便寫個(gè)邏輯 判斷是不是在騰訊，不是此處講的重點(diǎn)
}
運(yùn)行時(shí)間：
要找到該人，即意味著將要沿著每條邊前行，故運(yùn)行時(shí)間為 O(邊數(shù))
還用到了隊(duì)列，要檢查每個(gè)人。將一人添加入隊(duì)列的時(shí)間是固定的，為0(1)， ---? 隊(duì)列數(shù)據(jù)類型 插入操作的運(yùn)行時(shí)間為O(1)
要對(duì)每個(gè)人都進(jìn)行這樣的操作。即為 O(人數(shù))
所以：廣度優(yōu)先搜索的運(yùn)行時(shí)間為 O(人數(shù)+邊數(shù))，? 即 O(V+E)? ? 其中 V 為頂點(diǎn)數(shù)，E為邊數(shù)
PS： 還 可以用 Python 腳本寫。 先不寫了。
第七章 狄克斯特拉算法? ? Dijkstra
個(gè)人理解： 圖搜索 分為 有向圖，無向圖，加權(quán)圖，負(fù)權(quán)圖 等等? ? ? 狄克斯特拉算法比廣度優(yōu)先搜索 強(qiáng)在 適用于 計(jì)算 加權(quán)圖
1，知識(shí)點(diǎn)
（1），狄克斯特拉算法 對(duì)于每條邊上的相關(guān)數(shù)字，稱為? 權(quán)重（weight）
（2），帶權(quán)重的圖稱為加權(quán)圖，不帶權(quán)重的圖稱為 非加權(quán)圖
（3），計(jì)算非加權(quán)圖中的最短路徑，可使用 廣度優(yōu)先搜索（BFS），計(jì)算加權(quán)圖中的最短路徑可使用狄克斯特拉算法
（4），含有負(fù)權(quán)邊的圖，要計(jì)算最短路徑，不能使用狄克斯特拉算法，應(yīng)該使用 "貝爾曼-福德算法" 。
2，狄克斯特拉算法 分4個(gè)步驟
（1），找到 最便宜的節(jié)點(diǎn)，即可在最短時(shí)間內(nèi)到達(dá)的節(jié)點(diǎn)
（2），更新該節(jié)點(diǎn)鄰居的開銷，即 計(jì)算鄰居節(jié)點(diǎn)的最低開銷 然后更新（是否有前往鄰居節(jié)點(diǎn)的更短路徑，如果有則更新）
（3），重復(fù)這個(gè)過程，直到把所有節(jié)點(diǎn)的最低開銷都統(tǒng)計(jì)過
（4），計(jì)算最終路徑
3，廣度優(yōu)先搜索（BFS） 跟 狄克斯特拉（Dijkstra） 算法的 概念與區(qū)別
BFS 概念邏輯： 一層一層的挨個(gè)搜索，定義一個(gè)隊(duì)列，然后 優(yōu)先搜索第一級(jí)別節(jié)點(diǎn)，不匹配則將其鄰居節(jié)點(diǎn) 壓入隊(duì)列，保持好子節(jié)點(diǎn)與父節(jié)點(diǎn)對(duì)應(yīng)關(guān)系，直至循環(huán)找到目標(biāo)節(jié)點(diǎn)。然后從子父節(jié)點(diǎn)對(duì)應(yīng)關(guān)系中? 計(jì)算出 最短路徑
Dijkstra 概念邏輯：從節(jié)點(diǎn)列表中找到最便宜的節(jié)點(diǎn)，循環(huán)計(jì)算其鄰居節(jié)點(diǎn)的開銷，如若有比之前更低的開銷則更新節(jié)點(diǎn)列表，更新子父節(jié)點(diǎn)關(guān)系，循環(huán)處理所有節(jié)點(diǎn)。最終從子父節(jié)點(diǎn)對(duì)應(yīng)關(guān)系中統(tǒng)計(jì)出最短路徑
3個(gè)散列表集合
* 1個(gè)存 節(jié)點(diǎn)以及開銷（不可直接到達(dá)的節(jié)點(diǎn)，默認(rèn)開銷為無窮大）
* 1個(gè)存 節(jié)點(diǎn)對(duì)應(yīng) 鄰居以及開銷
* 1個(gè)存 已遍歷過的節(jié)點(diǎn)
4，JavaScript 代碼 實(shí)現(xiàn) 狄克斯特拉算法 跟 廣度優(yōu)先算法
/**
* 狄克斯特拉算法
* 最短路徑 + 加權(quán)重
*
* A 為起點(diǎn)
*
*
* Z 為終點(diǎn)
*
* 3個(gè)散列表集合
* 1個(gè)存 節(jié)點(diǎn)以及開銷
* 1個(gè)存 節(jié)點(diǎn)對(duì)應(yīng) 鄰居以及開銷
* 1個(gè)存 已遍歷過的節(jié)點(diǎn)
* */
var wuxiongda = 99999;
//節(jié)點(diǎn)集合 以及各自開銷
var allNode = {
? ? 'B' : 5,
? ? 'C' : wuxiongda,
? ? 'D' : wuxiongda,
? ? 'E' : 6,
? ? 'F' : wuxiongda,
? ? 'G' : wuxiongda,
? ? 'Z' : wuxiongda,
};
//各節(jié)點(diǎn)的父節(jié)點(diǎn)? eg B的父節(jié)點(diǎn)是A，'B':A
var allParentNode = {
? ? 'B' : 'A',
? ? 'E' : 'A',
};
//各節(jié)點(diǎn)的 鄰居節(jié)點(diǎn)以及開銷 集合
var graphNodeObj = {
? ? 'A' : {
? ? ? ? 'B' : 5,
? ? ? ? 'E' : 6,
? ? },
? ? 'B' : {
? ? ? ? 'C' : 16,
? ? ? ? 'D' : 9,
? ? },
? ? 'C' : {
? ? ? ? 'B' : 16,
? ? ? ? 'G' : 8,
? ? ? ? 'Z' : 7,
? ? },
? ? 'D' : {
? ? ? ? 'B' : 9,
? ? ? ? 'G' : 3,
? ? ? ? 'Z' : 8,
? ? },
? ? 'D' : {
? ? ? ? 'B' : 9,
? ? ? ? 'G' : 3,
? ? ? ? 'Z' : 8,
? ? },
? ? 'E' : {
? ? ? ? 'F' : 3,
? ? ? ? 'G' : 5,
? ? },
? ? 'F' : {
? ? ? ? 'E' : 3,
? ? ? ? 'G' : 8,
? ? },
? ? 'G' : {
? ? ? ? 'C' : 1,
? ? ? ? 'E' : 5,
? ? ? ? 'F' : 8,
? ? ? ? 'Z' : 4,
? ? },
};
//已遍歷過的節(jié)點(diǎn)
var usedList = {};
//計(jì)算最短路徑算法： 狄克斯特拉算法
function getShortest(){
? ? var node = getNewNode();//獲取一個(gè)未遍歷的 最便宜的 節(jié)點(diǎn)
? ? while(node != 'Z'){//非終點(diǎn)
? ? ? ? var cost = allNode[node];//該節(jié)點(diǎn) 的開銷成本
? ? ? ? var neighbor = graphNodeObj[node];// 該節(jié)點(diǎn)的 鄰居
? ? ? ? for(var neighNodeKey in neighbor){ //遍歷鄰居節(jié)點(diǎn)
? ? ? ? ? ? var new_cost = cost + neighbor[neighNodeKey]; //計(jì)算從起點(diǎn) 到 該鄰居節(jié)點(diǎn)的 開銷成本
? ? ? ? ? ? if(allNode[neighNodeKey] > new_cost){ //比較 若發(fā)現(xiàn)有較低開銷出現(xiàn)時(shí)，則更新 節(jié)點(diǎn)散列表 里的節(jié)點(diǎn)開銷 以及父節(jié)點(diǎn)散列表里的對(duì)應(yīng)關(guān)系
? ? ? ? ? ? ? ? allNode[neighNodeKey] = new_cost; //更新節(jié)點(diǎn)散列表
? ? ? ? ? ? ? ? allParentNode[neighNodeKey] = node;//更新 父節(jié)點(diǎn)散列表
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? usedList[node] = 1;//加入已遍歷過的節(jié)點(diǎn)散列表
? ? ? ? node = getNewNode();
? ? }
}
//獲取一個(gè)沒用過的節(jié)點(diǎn)
function getNewNode(){
? ? var rtn = '';
? ? var cost = 99999;
? ? for(var k in allNode){
? ? ? ? if(k in usedList){
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? if(allNode[k] < cost){
? ? ? ? ? ? cost = allNode[k];
? ? ? ? ? ? rtn = k;
? ? ? ? }
? ? }
? ? return rtn
}
function rtnRoute(list, Node){
? ? if(Node == 'A'){
? ? ? ? return 'A';
? ? }
? ? for(var n in list){
? ? ? ? if(n==Node){
? ? ? ? ? ? return n += '-->'+rtnRoute(list,list[n]);
? ? ? ? }
? ? }
}
//開始計(jì)算
getShortest();
//console.log(allNode);
//console.log(allParentNode);
//計(jì)算完畢后 整理路線
var finalRoute = '';
var finalNode = 'Z';
//rtnRoute(allParentNode, finalNode);
finalRoute = rtnRoute(allParentNode,finalNode);
console.log('最短路徑 = '+finalRoute);
console.log('最短路徑開銷成本 = '+allNode[finalNode]);
var graphNodeObj_BFS = {
? ? 'A' : {
? ? ? ? 'B' : 5,
? ? ? ? 'E' : 6,
? ? },
? ? 'B' : {
? ? ? ? 'C' : 16,
? ? ? ? 'D' : 9,
? ? },
? ? 'C' : {
? ? ? ? //'B' : 16,
? ? ? ? 'G' : 8,
? ? ? ? 'Z' : 7,
? ? },
? ? 'D' : {
? ? ? ? //'B' : 9,
? ? ? ? 'G' : 3,
? ? ? ? 'Z' : 8,
? ? },
? ? 'D' : {
? ? ? ? 'B' : 9,
? ? ? ? 'G' : 3,
? ? ? ? 'Z' : 8,
? ? },
? ? 'E' : {
? ? ? ? 'F' : 3,
? ? ? ? 'G' : 5,
? ? },
? ? 'F' : {
? ? ? ? //'E' : 3,
? ? ? ? 'G' : 8,
? ? },
? ? 'G' : {
? ? ? ? //'C' : 1,
? ? ? ? //'E' : 5,
? ? ? ? //'F' : 8,
? ? ? ? 'Z' : 4,
? ? },
};
//廣度優(yōu)先搜索算法
var allParentNode_BFS = {
? ? 'B' : 'A',
? ? 'E' : 'A',
};
var usedList_BFS = {};
function breadth_first_search(list, start, end){
? ? var graph = graphNodeObj_BFS[start];
? ? while(graph){
? ? ? ? var first = '';
? ? ? ? for(var n in graph){
? ? ? ? ? ? first = n;
? ? ? ? ? ? delete graph[n];
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? if(!(first in usedList_BFS)){
? ? ? ? ? ? if(first != end){
? ? ? ? ? ? ? ? // 該改點(diǎn)的鄰居 壓入 要搜索的隊(duì)列? start? -- 相對(duì)于php則會(huì)很簡(jiǎn)單 直接合并數(shù)組即可 JS 則為對(duì)象
? ? ? ? ? ? ? ? var graphChild = graphNodeObj_BFS[first];
? ? ? ? ? ? ? ? if(graphChild){
? ? ? ? ? ? ? ? ? ? for(var nchil in graphChild){
? ? ? ? ? ? ? ? ? ? ? ? graph[nchil] = graphChild[nchil];
? ? ? ? ? ? ? ? ? ? ? ? if(!(nchil in allParentNode_BFS)){ //不必多搜索重復(fù)節(jié)點(diǎn)-因?yàn)檫壿嫷览硐嗤?若重復(fù)節(jié)點(diǎn)搜索時(shí) 子節(jié)點(diǎn)父節(jié)點(diǎn) 散列表會(huì)混亂
? ? ? ? ? ? ? ? ? ? ? ? ? ? allParentNode_BFS[nchil] = first;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? // 該改點(diǎn)的鄰居 壓入 要搜索的隊(duì)列? end
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? graph = {};
? ? ? ? ? ? ? ? console.log('找到了');
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
breadth_first_search(graphNodeObj,'A','Z');
//console.log(allParentNode_BFS);
var finalRoute_BFS = '';
finalRoute_BFS = rtnRoute(allParentNode_BFS,'Z');
console.log('廣度優(yōu)先搜索計(jì)算出來最短路徑 = '+finalRoute_BFS);
//console.log();
第八章 貪婪算法? ?
1，個(gè)人理解：
貪婪算法是一種近似算法。即 接近最終答案，大致解決問題的算法
貪婪算法：每步都采取最優(yōu)的做法，即 每步都選擇局部最優(yōu)解，最終得到的就是全部最優(yōu)解
2，集合覆蓋問題，近似算法，貪婪算法
eg：覆蓋所有州，多個(gè)電臺(tái)，每個(gè)電臺(tái)可能覆蓋一個(gè)或多個(gè)州，計(jì)算出最優(yōu)的選擇電臺(tái)。
方法：選出一個(gè)覆蓋了最多未覆蓋州的 電臺(tái)，記錄進(jìn)去，然后再重復(fù)第一步，直至覆蓋完所有的州
貪婪算法的運(yùn)行時(shí)間為 O(n的2次方)? ? ? n為電臺(tái)數(shù)
3，NP完全問題，最佳的做法是使用近似算法
/*
* 貪婪算法 - 近似完全算法
*
* 事例：
* 美國(guó)N個(gè)州，M個(gè)電臺(tái)，每個(gè)電臺(tái)可能覆蓋1個(gè)或多個(gè)州，問：最終選最少的電臺(tái)覆蓋所有州
* **/
//所有的州
var allZhou = {
? ? a:1, b:1, c:1, d:1, e:1, f:1, g:1, h:1, i:1, j:1, k:1, l:1, m:1, n:1, o:1, p:1, q:1, r:1, s:1,t:1,
? ? u:1, v:1, w:1, x:1, y:1, z:1,
};
//所有的電臺(tái) -- 個(gè)電臺(tái)對(duì)應(yīng)的包含州
var allDj = {
? ? dj1 : ['q','w','e'],
? ? dj2 : ['r'],
? ? dj3 : ['t','y','u','o','p'],
? ? dj4 : ['a','s','f','a','p','v','o'],
? ? dj5 : ['d','f','g','h'],
? ? dj6 : ['j','a','k'],
? ? dj7 : ['l'],
? ? dj8 : ['z','x','c'],
? ? dj9 : ['v','b','n','l'],
? ? dj10 : ['q','a','z','m','d','p'],
? ? dj11 : ['r','o','s'],
? ? dj12 : ['i','d','l'],
? ? dj13 : ['e','k','v','r'],
? ? dj14 : ['u','p'],
};
var resultDj = [];//結(jié)果電臺(tái)
var finishStatus = false;
while(Object.keys(allZhou).length > 0){
? ? var mostPoint = getMostPoint(allDj, allZhou);
? ? if(!mostPoint || mostPoint==''){
? ? ? ? finishStatus = true;
? ? ? ? break;
? ? }
? ? resultDj.push(mostPoint);
? ? for(var i in allDj[mostPoint]){
? ? ? ? delete allZhou[allDj[mostPoint][i]];
? ? }
? ? if(Object.keys(allZhou).length==0){
? ? ? ? finishStatus = true;
? ? }
}
if(finishStatus){
? ? console.log('執(zhí)行結(jié)束');
? ? console.log('執(zhí)行結(jié)果：');
? ? console.log(resultDj);
}
//查找覆蓋最多的 點(diǎn)
function getMostPoint(obj1, obj2){
? ? var resultP = '';//結(jié)果點(diǎn)
? ? var resultPV = 0;//結(jié)果點(diǎn)覆蓋的量
? ? for(var i in obj1){
? ? ? ? if(typeof obj1[i] == 'function'){ continue; }
? ? ? ? var tmpPV = 0;
? ? ? ? for(var i2 in obj1[i]){
? ? ? ? ? ? if(obj1[i][i2] in obj2){
? ? ? ? ? ? ? ? tmpPV += 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(tmpPV > resultPV){
? ? ? ? ? ? resultPV = tmpPV;
? ? ? ? ? ? resultP = i;
? ? ? ? }
? ? }
? ? return resultP;
}
第九章 動(dòng)態(tài)規(guī)劃?
1，個(gè)人理解
動(dòng)態(tài)規(guī)劃 是將問題 采用畫網(wǎng)格的方式 計(jì)算出 最優(yōu)最終的答案，網(wǎng)格行的排列順序變化 對(duì)計(jì)算沒有影響
2，最長(zhǎng)公共子串
3，小結(jié)
在給定約束條件下優(yōu)化某種指標(biāo)時(shí)，動(dòng)態(tài)規(guī)劃很有用
問題可分解為離散子問題時(shí)，可用動(dòng)態(tài)規(guī)劃
每種動(dòng)態(tài)規(guī)劃解決方案都涉及 網(wǎng)格
單元格中的值 通常是要優(yōu)化的值，每個(gè)單元格都是一個(gè)子問題
第十章 K最近鄰算法? （KNN）
1，計(jì)算兩點(diǎn)的距離，可使用 畢達(dá)哥拉斯 算法
2，回歸
回歸就是預(yù)測(cè)結(jié)果。
3，可適用于? 創(chuàng)建推薦系統(tǒng)。
3.1，OCR -- 光學(xué)字符識(shí)別
即 計(jì)算機(jī)可識(shí)別照片中的內(nèi)容，文字
語音識(shí)別，人臉識(shí)別 等也是基于KNN等簡(jiǎn)單理念的
一般來說，OCR算法提取線段，點(diǎn)，曲線 等特征
OCR的第一步是查看大量的數(shù)字圖像并提取特征，這被稱為 訓(xùn)練
4，小結(jié)：
KNN用于分類和回歸，需要考慮最近的鄰居
分類就是編組
回歸就是預(yù)測(cè)結(jié)果（如數(shù)字）
能否挑選合適的特征 事關(guān)KNN算法的成敗
