資訊專欄INFORMATION COLUMN
摘要：首先說下算法對于前端的作用和應用作用不用說了提高效率和性能應用目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。
首先說下算法對于前端的作用和應用
作用：不用說了提高效率和性能
應用：目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直接說下現(xiàn)在已經(jīng)應用的兩個地方
trie樹結構，對于后端扁平化數(shù)據(jù)轉樹形結構適用于前端的應用，終于把遞歸改成動規(guī)了
動態(tài)規(guī)劃在前端瀑布流中的應用
第一點我也是看了這篇博客才下定決心邁向算法大坑的，具體不多說直接附上地址
連接描述
第二點的動態(tài)規(guī)劃參考以下博客，其中說的非常清晰，我主要是列舉下對于此篇介紹中已實現(xiàn)的js，做 空間復雜度優(yōu)化的代碼，不足之處請指出
鏈接描述
首先我是按照數(shù)據(jù)的倒退圖里面以物品數(shù)組作為外層數(shù)組，背包容量作為內(nèi)層數(shù)組的形式寫的js（按照圖的推導順序）
1 用來生成隨機大小的物品重量和價值數(shù)組function getNum() {
return parseInt(Math.random()*100+1);
}
function getArr(size) {
var arr = [];
for (var i = 0;i
2 實現(xiàn)
function aaa(wight,value,all) {
var startTime = new Date().getTime();
var returnList = [];
for (var i = 0;i=0?nowV:0;
fV = fV+(i>0&&returnList[i-1][lastW-1]?returnList[i-1][lastW-1]:0);
var nV = i>0&&returnList[i-1][j]?returnList[i-1][j]:0;
returnList[i][j] = Math.max(fV,nV);
}
}
var endTime = new Date().getTime();
return returnList[wight.length-1][all-1]+"耗時："+(endTime-startTime)+"ms";
}
console.log(aaa(weight,value,V));
這種方式需要構建龐大的二維緩存數(shù)組（用來把每次的最優(yōu)解存下,類似于斐波那契函數(shù)動規(guī)的緩存），這一步完全可以優(yōu)化成只構建上一步的最優(yōu)解供給下一次使用
function bbb(wight,value,all) {
var startTime = new Date().getTime();
var returnList = [];
var returnList_prev = [];
var flag = true;
for (var i = 0;i=0?nowV:0;
fV = fV+(i>0&&returnList_prev[lastW-1]?returnList_prev[lastW-1]:0);
var nV = i>0&&returnList_prev[j]?returnList_prev[j]:0;
returnList[j] = Math.max(fV,nV);
} else {
var fV = lastW>=0?nowV:0;
fV = fV+(i>0&&returnList[lastW-1]?returnList[lastW-1]:0);
var nV = i>0&&returnList[j]?returnList[j]:0;
returnList_prev[j] = Math.max(fV,nV);
}
}
flag = !flag;
}
var endTime = new Date().getTime();
return returnList[all-1]+"耗時："+(endTime-startTime)+"ms";
}
console.log(bbb(weight,value,V));
對比了兩次的結果時間分別是：
可以看到bbb方法明顯比aaa快了一倍之多
這里只是想把自己看書后應用的東西分享下，大家有更好的方法也可以指正-。-
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://www.ezyhdfw.cn/yun/54865.html
摘要：首先說下算法對于前端的作用和應用作用不用說了提高效率和性能應用目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。 首先說下算法對于前端的作用和應用 作用：不用說了提高效率和性能 應用：目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
摘要：首先說下算法對于前端的作用和應用作用不用說了提高效率和性能應用目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。 首先說下算法對于前端的作用和應用 作用：不用說了提高效率和性能 應用：目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
摘要：首先說下算法對于前端的作用和應用作用不用說了提高效率和性能應用目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。 首先說下算法對于前端的作用和應用 作用：不用說了提高效率和性能 應用：目前也是買了算法導論這本書，看得頭暈，各種數(shù)學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
閱讀 3093·2023-04-26 02:22
閱讀 2431·2021-11-17 09:33
閱讀 3349·2021-09-22 16:06
閱讀 1249·2021-09-22 15:54
閱讀 3675·2019-08-29 13:44
閱讀 2104·2019-08-29 12:37
閱讀 1444·2019-08-26 14:04
閱讀 2051·2019-08-26 11:57
