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