本系列前面兩篇講的都是一些背景知識，從這一篇開始我們正式講算法，從算法的一些基本概念講起。

什么是算法

通過上一篇對圖靈機原理的講解，我們知道，一個計算問題描述的是輸入/輸出之間的關系，如果根據給定的輸入能設計一個程序計算出期望的輸出，就認為這個問題可解。這個程序的計算過程就是用算法來描述的，通過算法這個工具我們就容易設計出這樣的一個程序。

確切地說，算法是有限步驟的計算過程，該過程取某個值或集合作為輸入，并產生某個值或集合作為輸出。

算法的正確與錯誤

如果算法對于每個輸入都可以正確的停機，則稱該算法是正確的，并稱正確的算法解決了給定的計算問題。一個不正確的算法對于某個輸入可能根本不停機，也可能以不正確的結果停機，比如一個排序問題：

輸入：一個長度為n的數組(a1,a2,a3...) 輸出：輸入數組排序后的一個數組(b1,b2,b3....)，滿足：b1≤b2≤b3

如果根據這個問題設計出來的算法交給圖靈機運行輸出的結果與人們的期望相反（比如輸出：b3,b2,b1…），那么這個算法就是錯誤的。

隨機訪問機模型

針對同一計算問題，可以設計出多種算法，其中有好有壞，我們可以通過預測算法需要的資源來篩選出好的算法。雖然有時我們關心內存、帶寬這類硬件資源，但通常我們度量的是運行時間。

度量算法的運行時間，人們通常用的是隨機訪問機模型（Random-Access Machine, RAM）。在 RAM 模型中：

• 指令一條接著一條執行的，沒有并發操作。
• 指令包含了真實計算機的常見指令：算數指令（加法，減法，乘法，除法，取余等）、數據移入指令（裝入，存儲，復制）和控制命令（條件與無條件轉移、子程序調用與返回）;
• 每條指令所用的時間均為常量。

RAM 模型假定的觀點是，運行每行偽代碼所需的時間是一個常量時間，雖然真實計算機執行一行代碼與另一行代碼需要不同的常量時間。依此，一個算法在特定輸入上的運行時間不是指現實意義的時間，而是執行指令的次數。

比如下面這段 foo 函數的代碼：

// prettier-ignore
function foo(n) {
for (let i = 0; i < n; i++) { // 2n+1 次
console.log('Hello, World!') // n 次
}
return 0 // 1 次
}

上面的代碼需要執行 2n + 1 + n + 1 = 3n + 2 次指令，也就是說執行時間是 3n + 2，如果用一個時間函數來表示，就是 T(n) = 3n + 2。

算法的時間復雜度

根據 RAM 模型，一個算法可以在給定的輸入規模 n 下分析出一個運行時間的函數 T(n)。研究 T(n) 常用的一種策略是分析輸入規模 n 增大的情況下 T(n) 的變化（如線性增長、指數增長等）。如果用 f(n) 來表示 T(n) 的增長速度，那么 f(n) 和 T(n) 的關系我們約定用一個大 O 來表示，即：

T(n) = O(f(n))

這就是 大 O 表示法。由于輸入規模 n 的增長率與 f(n) 的增長率是正相關的，所以稱作 漸近時間復雜度（Asymptotic Time Complexity），簡稱 時間復雜度。相對應的，還有空間復雜度，這里我們不作討論。

當 n 足夠大時或趨于無窮大時，T(n) 的常數部分就變得不重要，我們真正關心的是運行時間的 增長量級 或 增長率。如果用 f(n) 來表示增長數度，上面 foo 示例代碼的增長速度可以表示為 f(n) = n，把它代入到 T(n) = O(f(n)) 就是：

T(n) = O(n)

這時，我們稱 foo 的時間復雜度為 O(n)。

常見的時間復雜度有：

• 常數階 O(1)，
• 對數階 O(log2^n)，
• 線性階 O(n)，
• 線性對數階 O(nlog2^n)，
• 平方階 O(n^2)，
• 立方階 O(n^3)，
• k 次方階 O(n^k)，
• 指數階 O(2^n)。

隨著問題規模 n 的不斷增大，上述時間復雜度不斷增大，算法的執行效率也越低。大 O 表示法只是一種估算，當輸入規模足夠大的時候才有意義。

注意，大 O 表示法考慮的是最壞的情況。比如，從一個長度為 n 的數組中找一個值等于 10 的元素，開始遍歷掃描這個數組，有可能第 1 次就掃到了，也有可能是第 n 次才掃到。這里最壞的情況是 n 次，所以時間復雜度就是 O(n)。

大部分情況下你用直覺就可以知道一個算法的大 O 表示。比如，如果用一個循環遍歷輸入的每個元素，那么這個算法就是 O(n)；如果是用循環套循環，那就是 O(n^2)，以此類推。

參考：《算法導論，第三版》

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法系列教程04 - 算法相关的基础概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。