#引言
為什么要學(xué)習(xí) 算法, 它到底能給我?guī)硎裁茨?
- 對(duì)于求職者而,
算法 能力能成為你拿到優(yōu)質(zhì) offer 的敲門磚, 不管是大廠還是國外面試都要求有一定 算法 能力 算法 是解決某類問題的思路, 通過它可以很好培養(yǎng)我們的邏輯思維能力- 也許在平常工作中你用不到你所學(xué)的
算法, 但是當(dāng)遇到一些復(fù)雜問題, 它可以幫助你在復(fù)雜的情況中更好地分析問題、解決問題、從而尋找出最優(yōu)的解決問題的思路 - 讓我們自己研究
算法 很難, 但是目前很多 算法 都是幾代人努力, 研究出來的, 我們可以直接研究學(xué)習(xí), 站在巨人的肩膀上成就自我, 何樂而不為呢 算法 是一種解決問題的思路和方法, 也許有機(jī)會(huì)應(yīng)用到生活和事業(yè)的其他方面呢- 長期來看, 大腦思考能力是個(gè)人最重要的核心競爭力, 而算法是為數(shù)不多的能夠有效訓(xùn)練大腦思考能力的途徑之一
所以相信我, 學(xué)習(xí) 算法 應(yīng)該是一件很酷的事情, 下面請(qǐng)開始進(jìn)入正題...
#一、什么是算法
首先一句話說明什么是算法, 算法是解決問題的思路或步驟!
比如 '如何將任意排列的數(shù)字, 按從小到大的順序排列'、'尋求出發(fā)點(diǎn)到目的地的最短路徑'等, 它們是一個(gè)個(gè)實(shí)際的問題, 那么基于問題有多種解題思路, 而這些思路, 其實(shí)就是所謂的算法。
#1.1 算法和程序的區(qū)別
上文提到算法是解題思路, 我們可以通過人類所能夠理解的方式進(jìn)行描述, 可以是文字、可以是圖片、可以是動(dòng)畫....
而程序則是計(jì)算機(jī)所能理解的代碼段, 本質(zhì)上它和算法是有所不同的:
- 程序則是計(jì)算機(jī)能夠理解的語法、步驟, 封裝而成的代碼塊
同一個(gè)問題, 可以有多種解法, 也就是有多種算法。算法是具體的思路, 是可以被人類所理解的, 而同一個(gè)算法它可以使用不同的計(jì)算機(jī)語言去實(shí)現(xiàn)。當(dāng)然相同的編程語言、相同算法, 編寫出來的代碼也是有可能不同的(因?yàn)橛玫降幕A(chǔ)語法可能存在差異)但底層的思路是相同的!!
當(dāng)然實(shí)際上我們?cè)谠O(shè)計(jì)算法的過程中, 也是需要根據(jù)所選擇的編程語言進(jìn)行合理的設(shè)計(jì)!! 切勿天馬行空, 最后發(fā)現(xiàn)設(shè)計(jì)出來的算法, 計(jì)算機(jī)編程語言并不能實(shí)現(xiàn)!!!
#1.2 舉個(gè)栗子: 排序
排序算法是將一組隨機(jī)數(shù)字, 按照一定順序(升序或降序)進(jìn)行排列的算法。在計(jì)算機(jī)科學(xué)中, 排序算法有很多種, 常見的包括冒泡排序、選擇排序、插入排序、快速排序、歸并排序、堆排序等等。
下面我們以 選擇算法 為例, 講解下如果針對(duì)一組數(shù)字進(jìn)行升序排序
在設(shè)計(jì)算法時(shí), 假設(shè)整個(gè)程序是一個(gè)函數(shù), 那么我們則需要考慮幾個(gè)點(diǎn):
- 輸入, 在這里輸入就是一組數(shù)字, 這里可以是一個(gè)數(shù)字?jǐn)?shù)組
- 輸出, 這里輸出也是一組數(shù)字, 是一組排序完成后的數(shù)字, 這里同樣可以是一個(gè)數(shù)字?jǐn)?shù)組
- 主體邏輯, 其實(shí)就是算法部分, 也就是排序的一個(gè)思路
const main = (nums: number[]): number[] => {
// 算法邏輯
}
那么對(duì)于 選擇排序 算法, 其思路是怎樣的呢? 如下圖所示:
- 第一次先循環(huán)所有數(shù)字, 從列表中找到最小的一個(gè)數(shù)字, 然后和最左邊的數(shù)字進(jìn)行交換
- 第二次循環(huán)從第二個(gè)位置開始, 從剩余的列表中找到最小的一個(gè)數(shù)字, 然后和循環(huán)開始位置(第二個(gè)位置)的數(shù)字進(jìn)行交換
- 第三次循環(huán)從第三個(gè)位置開始, 從剩余的列表中找到最小的一個(gè)數(shù)字, 然后和循環(huán)開始位置(第三個(gè)位置)的數(shù)字進(jìn)行交換
這里我們沒有限制數(shù)組長度, 輸入數(shù)組長度為 n, 不管 n 多大, 思路是一樣的, 我們的算法都應(yīng)該可以解決問題
#二、選擇合適的算法
針對(duì)同一個(gè)問題, 解決的算法可以是多種多樣的, 我們又可以如何一個(gè)合適的算法呢? 在算法的評(píng)判上, 可以考量的標(biāo)準(zhǔn)各有不同。我們通常會(huì)綜合考慮算法的可理解性(方便編寫程序)、算法運(yùn)行所需占用的空間資源以及算法運(yùn)行所需的時(shí)間。
當(dāng)然, 一般情況下我們更重視算法的所運(yùn)行的時(shí)間, 即從輸入數(shù)據(jù)到輸出結(jié)果整個(gè)過程所要花費(fèi)的時(shí)長。
下面我們來看個(gè)例子, 來說明下不同算法之間的差距到底有多大!!
#2.1 全排列算法
下面我們看一個(gè)低效率的排序算法, 來感受下其威力, 該方法被稱為 全排列算法 你可以理解為暴力破解, 其主要思路就是:
- 根據(jù)輸入數(shù)字, 隨機(jī)打亂生成一個(gè)數(shù)列(不和前面生成的數(shù)列順序重復(fù))
- 如果上面一步生成的數(shù)列是按從小到大的順序排列, 則將其輸出, 否則繼續(xù)上一步操作
該算法若在運(yùn)氣好的情況下, 很快就隨機(jī)出正確的數(shù)列, 結(jié)果也就立馬出來了。然而, 實(shí)際情況往往并不如我們所愿。最差的情況, 也就是直到最后才出現(xiàn)正確排列的情況下, 計(jì)算機(jī)就不得不列出所有可能的數(shù)列了。
假設(shè)這里 n 為 50, 那么在最差情況下, 全排列次數(shù)則為:
50! = 50 * 49 * 48 ... * 13 * 12 * 11 * 10... * 3 * 2 * 1 > 10^40
這里為方便計(jì)算, 我們姑且 50 個(gè)數(shù)字全排列次數(shù)按 10^40 來算, 那么假設(shè) 1 臺(tái)高性能計(jì)算機(jī) 1 秒能檢查 1萬億(=10^12)個(gè)數(shù)列, 那么檢查 10^40 個(gè)數(shù)列將花費(fèi)的時(shí)間為 10^40 ÷ 10^12 = 10^28 秒。1 年為 31536000 秒, 不到 10^8 秒, 因此, 10^28 秒 > 10^20 年
然而, 你要知道從大爆炸開始宇宙也就經(jīng)歷了約 137 億年, 那么即便如此也少于 10^11 年。也就是說, 僅僅是對(duì) 50 個(gè)數(shù)字進(jìn)行排序, 若使用全排列算法, 就算花費(fèi)宇宙年齡的 10^9 倍時(shí)間也得不出答案。
#2.2 選擇排序
上文情況, 我們?nèi)绻麚Q成 選擇排序 又會(huì)是啥情況呢?
在 選擇排序 中假設(shè)輸入為 n, 為了在第 1 輪找到最小的數(shù)字, 則需要從左往右確認(rèn)數(shù)列中的數(shù)字, 如此只要查詢 n 個(gè)數(shù)字即可。在接下來的第 2 輪中, 只需要從 n-1 個(gè)數(shù)字中尋找最小值, 所以需要查詢 n-1 個(gè)數(shù)字, 在接下來的第 3 輪中, 需要從 n-2 個(gè)數(shù)字中尋找最小值, 所以需要查詢 n-2 個(gè)數(shù)字, 以此類推, 我們需要查詢的次數(shù)為:
n + (n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n(n + 1)/2 <= n^2
如此的話, 同樣當(dāng) n 等于 50 情況下, 選擇排序 也只需要 n^2 = 2500 即可, 同樣假設(shè) 1 秒能確認(rèn) 1 萬億(=1012)個(gè)數(shù)字, 那么 2500 ÷ 10^12=0.0000000025 秒便能得出結(jié)果, 這不知比全排列算法的效率高了不知道多少倍!!
#三、時(shí)間復(fù)雜度
算法運(yùn)行時(shí)間和輸入數(shù)據(jù)量呈正相關(guān): 從上面內(nèi)容不難得出結(jié)論, 不同的算法很大程度上會(huì)影響到算法運(yùn)行的時(shí)長。 當(dāng)然不難想象在使用相同算法情況下, 數(shù)據(jù)量的不同同樣會(huì)影響算法的運(yùn)行時(shí)間, 數(shù)據(jù)量越大運(yùn)行時(shí)間自然也越久。
#3.1 運(yùn)行時(shí)間計(jì)算
實(shí)際情況, 給我們一個(gè)算法我們其實(shí)根本沒法精確的計(jì)算出程序所需要運(yùn)行的時(shí)長, 因?yàn)槌绦蜻\(yùn)行時(shí)間是會(huì)根據(jù)所運(yùn)行的計(jì)算機(jī)環(huán)境所影響, 即便在同一機(jī)器上, 運(yùn)行相同的程序, 最終的運(yùn)行時(shí)間也是存在差異的。
所以這里我們其實(shí)可以用 步數(shù) 來描述一個(gè)算法所能運(yùn)行的時(shí)間, 通過計(jì)算程序從開始到結(jié)束所需要執(zhí)行多少步, 從而得出算法的一個(gè)運(yùn)行時(shí)間。如此在輸入相同情況下, 通過比較算法所執(zhí)行的 步數(shù), 我們就可以得出哪個(gè)算法時(shí)間效率最高。
下面我們還是拿 選擇排序 為例, 我們先回顧下選擇排序的思路:
- 從剩余的數(shù)列中, 尋找最小的數(shù)字(這里我們假設(shè)每次循環(huán)中, 確認(rèn)最小值所需時(shí)間為
T1) - 將最小值和剩余隊(duì)列的最左邊數(shù)字交換位置, 本輪循環(huán)結(jié)束, 回到上一步 ????(這里我們假設(shè), 交換數(shù)字所需時(shí)間為
T2)
而, 選擇排序 算法運(yùn)行時(shí)間計(jì)算結(jié)果則如下:
#3.2 運(yùn)行時(shí)間表示方法
雖然在上文我們已經(jīng)得出運(yùn)行時(shí)間的結(jié)果, 但是實(shí)際上還是可以進(jìn)行一個(gè)簡化的:
- 在公式中,
T1 和 T2 都是基本的單位, 和輸入數(shù)據(jù)量 n 沒有任何關(guān)系, 所以它們其實(shí)可以忽略 - 同時(shí)在整個(gè)公式中, 隨著輸入數(shù)據(jù)量的增加或減小, 對(duì)整個(gè)運(yùn)行時(shí)間影響最大的是
n^2 所以我們只需要保留它即可
最后上面公式簡化后結(jié)果如下:
上面公式結(jié)果中, 我們使用了 O 來進(jìn)行表示, O 這個(gè)符號(hào)的意思是 忽略重要項(xiàng)以外的內(nèi)容 讀音同 Order。O(n^2) 的含義就是算法的運(yùn)行時(shí)間最長也就是 n2 的常數(shù)倍, 準(zhǔn)確的定義請(qǐng)參考相關(guān)專業(yè)書籍。重點(diǎn)在于, 通過這種表示方法, 我們可以直觀地了解算法的時(shí)間和數(shù)據(jù)量 n 的關(guān)系。
同樣的,
- 假設(shè)某個(gè)算法運(yùn)行時(shí)間計(jì)算為
5 * T1 * n^3 + 12 * T2 * n^2 + 3 * T3 * n 那么其時(shí)間復(fù)雜度可以表示為 O(n^3) - 假設(shè)某個(gè)算法運(yùn)行時(shí)間計(jì)算為
3 * n * logn + 2 * T1 * n 那么其時(shí)間復(fù)雜度可以表示為 O(n * logn)
從時(shí)間復(fù)雜度上來看, 對(duì)于不同時(shí)間復(fù)雜度的算法, 我們很容易就可以判斷出這幾個(gè)算法哪個(gè)更為高效。比如, 當(dāng)我們知道選擇排序的時(shí)間復(fù)雜度為 O(n^2)、快速排序的時(shí)間復(fù)雜度為 O(nlogn) 時(shí), 很快就能判斷出快速排序的運(yùn)算更為高速。二者的運(yùn)行時(shí)間根據(jù)輸入 n 產(chǎn)生的變化程度也一目了然。
#四、空間復(fù)雜度
這里的空間復(fù)雜度其實(shí)和上面講到的時(shí)間復(fù)雜度很是類似, 只是衡量的維度不同:
- 時(shí)間復(fù)雜度描述的是, 數(shù)據(jù)量
n 和程序運(yùn)行時(shí)間的一個(gè)關(guān)系(趨勢) - 而空間復(fù)雜度則是描述, 數(shù)據(jù)量
n 和程序運(yùn)行時(shí)所占用內(nèi)存空間的一個(gè)關(guān)系(趨勢)
而算法程序在運(yùn)行期間, 涉及到的內(nèi)存空間主要有: 輸入空間、暫存空間、輸出空間
空間復(fù)雜度推算方法和表示方式, 基本和時(shí)間復(fù)雜度一樣, 但是空間復(fù)雜度這里則需要注意幾個(gè)要點(diǎn):
- 以最差情況為準(zhǔn): 假設(shè)輸入數(shù)據(jù)量不同, 空間復(fù)雜度不同, 那么這里就要取最差的情況! 比如, 當(dāng)輸入數(shù)據(jù)量
n < 10 時(shí), 空間復(fù)雜度為 O(1), 當(dāng)輸入數(shù)據(jù)量 n > 10 時(shí), 空間復(fù)雜度為 O(n), 那么我們則需要取 O(n) - 以程序運(yùn)行的峰值內(nèi)存為準(zhǔn): 在算法程序運(yùn)行期間可能存在不同的情況, 我們需要以內(nèi)存占用最高的為止。比如, 程序在運(yùn)行的最初占用
O(n) 空間, 當(dāng)運(yùn)行到最后一行, 內(nèi)存占用為 O(1), 那么我們則需要取 O(n) - 在遞歸函數(shù)中, 需要注意統(tǒng)計(jì)棧幀空間(具體看下面例子)
- 在循環(huán)過程中, 定義的塊級(jí)變量或調(diào)用的函數(shù), 在下一輪循環(huán)后會(huì)被銷毀, 因此這里是不會(huì)累積占用空間復(fù)雜度, 空間復(fù)雜度依然是
O(1)
下面是遞歸函數(shù)演示代碼:
- 函數(shù)
loop() 執(zhí)行了 constFunc, 執(zhí)行期間創(chuàng)建一個(gè)上下文, 執(zhí)行完成則銷毀, 所以這里空間復(fù)雜度為 O(1) - 遞歸函數(shù)
recur() 在運(yùn)行過程中會(huì)同時(shí)存在 n 個(gè)未返回的 recur() 也就是同時(shí)存在 n 個(gè)上下文, 所以這里空間復(fù)雜度為 O(n)
function constFunc() {
// 執(zhí)行某些操作
return 0;
}
/* 循環(huán)的空間復(fù)雜度為 O(1) */
function loop(n) {
for (let i = 0; i < n; i++) {
constFunc();
}
}
/* 遞歸的空間復(fù)雜度為 O(n) */
function recur(n) {
if (n === 1) return;
return recur(n - 1);
}
#五、常見復(fù)雜度類型
下圖是幾種常見的復(fù)雜度類型, 從低到高依次為: 常數(shù)階: O(1)、對(duì)數(shù)階: O(logn)、線性階: O(n)、平方階: O(n^2)、指數(shù)階: O(2^n)
下表是相關(guān)復(fù)雜度類型的簡介:
| |
|---|
常數(shù)階: O(1) | 輸入數(shù)據(jù)量 n 不影響需要衡量的指標(biāo) |
對(duì)數(shù)階: O(logn) | |
線性階: O(n) | 輸入數(shù)據(jù)量 n 和要衡量的指標(biāo)成正相關(guān), 常見于: 數(shù)組、鏈表、棧、隊(duì)列等 |
平方階: O(n^2) | 常見于矩陣和圖, 輸入數(shù)據(jù)量 n 和要衡量的指標(biāo)成平方關(guān)系 |
指數(shù)階: O(2^n) | |
#六、權(quán)衡時(shí)間與空間
每個(gè)人都追求完美, 故而在理想情況下, 我們肯定希望算法的時(shí)間復(fù)雜度和空間復(fù)雜度都能夠達(dá)到最優(yōu)。然而現(xiàn)實(shí)情況中, 兩者很難兼得, 因?yàn)橥瑫r(shí)優(yōu)化時(shí)間復(fù)雜度和空間復(fù)雜度通常非常困難。
大部分情況下降低時(shí)間復(fù)雜度通常需要以提升空間復(fù)雜度為代價(jià), 反之亦然。我們將犧牲內(nèi)存空間來提升算法運(yùn)行速度的思路稱為 以空間換時(shí)間; 反之, 則稱為 以時(shí)間換空間。
當(dāng)然選擇哪種思路取決于我們更看重哪個(gè)方面。在大多數(shù)情況下, 我們更在乎的是程序的運(yùn)行時(shí)間, 因此 以空間換時(shí)間 通常是更常用的策略。當(dāng)然, 在數(shù)據(jù)量很大的情況下, 控制空間復(fù)雜度也非常重要。
#七、參考
