面試官：說說你對(duì)算法的理解？應(yīng)用場(chǎng)景？
一、是什么
算法(Algorithm)是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制
也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出
如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題
一個(gè)程序=算法+數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)，算法總是要依賴于某種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的，兩者不可分割
因此，算法的設(shè)計(jì)和選擇要同時(shí)結(jié)合數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)單地說數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)就是選擇存儲(chǔ)方式，如確定問題中的信息是用數(shù)組存儲(chǔ)還是用普通的變量存儲(chǔ)或其他更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)
針對(duì)上述，可以得出一個(gè)總結(jié)：不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)
二、特性
關(guān)于算法的五大特性，有如下：
- 有限性(Finiteness)：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束
- 確切性(Definiteness)：一個(gè)算法的每一步驟必須有確切的定義
- 輸入(Input)：一個(gè)算法有零個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂零個(gè)輸入是指算法本身給定了初始條件
- 輸出(Output)：一個(gè)算法有一個(gè)或多個(gè)輸出。沒有輸出的算法毫無意義
- 可行性(Effectiveness)：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成(也稱之為有效性)
三、應(yīng)用場(chǎng)景
在前端領(lǐng)域中，數(shù)據(jù)結(jié)構(gòu)與算法無法不在，例如現(xiàn)在的vue或者react項(xiàng)目，實(shí)現(xiàn)虛擬DOM或者Fiber結(jié)構(gòu)，本質(zhì)就是一種數(shù)據(jù)結(jié)構(gòu)，如下一個(gè)簡(jiǎn)單的虛擬DOM：
- {
- type: 'div',
- props: {
- name: 'lucifer'
- },
- children: [{
- type: 'span',
- props: {},
- children: []
- }]
- }
vue與react都能基于基于對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)diff算法，提高了整個(gè)框架的性能以及拓展性
包括在前端javascript編譯的時(shí)候，都會(huì)生成對(duì)應(yīng)的抽象語法樹AST，其本身不涉及到任何語法，因此你只要編寫相應(yīng)的轉(zhuǎn)義規(guī)則，就可以將任何語法轉(zhuǎn)義到任何語法，也是babel， PostCSS, prettier， typescript
除了這些框架或者工具底層用到算法與數(shù)據(jù)結(jié)構(gòu)之外，日常業(yè)務(wù)也無處不在，例如實(shí)現(xiàn)一個(gè)輸入框攜帶聯(lián)想功能，如下：
如果我們要實(shí)現(xiàn)這個(gè)功能， 則可以使用前綴樹，如下：
包括前端可能會(huì)做一些對(duì)字符串進(jìn)行相似度檢測(cè)，例如"每日一題"和"js每日一題"兩個(gè)字符串進(jìn)行相似度對(duì)比，這種情況可以通過“最小編輯距離”算法，如果a和b的編輯距離越小，我們認(rèn)為越相似
日常在編寫任何代碼的都需要一個(gè)良好的算法思維，選擇好的算法或者數(shù)據(jù)結(jié)構(gòu)，能讓整個(gè)程序效率更高
參考文獻(xiàn)
https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
https://lucifer.ren/blog/2019/09/18/algorthimn-fe-1/
