演算法與數據結構：TypeScript實現——Part 0 遞歸與時間複雜度

02-03

計算機就是一個勤勞的笨蛋，我們讓它做什麼他就去做什麼。作為一個程序員，編程就是一個「告訴計算機你要去做哪些事情然後告訴我結果」的過程。很多情況下，我們可能需要讓計算機重複一些事情，比如讓它從0加到100，然後告訴我們答案。一般的程序員都知道，在這種情況下我們會怎麼樣去寫這個代碼：

let result = 0;nfor(let i = 0 ; i < 100 ; i++) {n result += i;n}n

但是這麼寫並不能達到一個程序可復用的標準。我們可能會讓它從0加到100，也可能從25加到80，所以通常我們會這麼做：

function sum(start: number , end: number): number => {n for(let i = start; i < end; i++) {n start += i;n }n return start;n}n

當然，這個代碼也是漏洞百出，至少並沒有在內部驗證過start <= end這個條件。但是拋開這個不管，這個想法是滿足了我們需要的邏輯——疊加。

讓我們來看一個更複雜的情況，就是求Fibonacci數列。這個數列的定義是

F(n) = F(n - 1) + F(n - 2) , n >= 2 , F(0) = 0 , F(1) = 1n

這種情況下我們如何使用for循環解決呢？

function fibonacci(n): number => {n if(n == 0) return 0;n if(n == 1) return 1;n let result = 1;n let f1 = 0;n let f2 = 1;n for(let i = 2; i <= n ; i++) {n result = f1 + f2;n f1 = f2;n f2 = result;n }n return result;n}n

這個時候我們開看這個代碼，顯得非常的難懂。為什麼我需要有一個f1和f2，我還需要互相賦值、換算。儘管工作了，但是難懂啊。所以我們如何使用簡單易懂的方式來解決這個問題呢？

function fibonacci(n): number => {n if(n == 0) return 0;n if(n == 1) return 1;n return fibonacci(n - 1) + fibonacci(n - 2);n}n

沒錯，這不就是fibonacci數列的定義本身嗎？這種組織代碼的方式就是我們所說的遞歸函數——通過自我調用，來解決一個重複性操作晦澀難懂的問題。相比之下，遞歸函數來解決fibonacci數列的代碼更容易維護。

但是回過頭，我們再來看看遞歸所帶來的問題。很明顯，遞歸的方式運行起來更慢——我們需要運算一遍fibonacci(n - 1)，然後還需要運算一遍fibonacci(n - 2)；而在fibonacci(n - 1)函數中，我們需要運算一次fibonacci(n - 2)和一次fibonacci(n - 3)……以此類推，遞歸所需要花費的時間就是循環所要花費的n倍啊！循環所要花費的時間是n，而遞歸所需要花費的時間則是n的平方。

所以在這裡，我們需要引入時間複雜度這樣一個概念。通常，處理數據（對於計算機來說，可能還有I/O）的時間占循環運行時間的大多數，這些時間我們計作單位時間。

1 在一個函數中，就執行一個或者幾個指令，那麼我們將其稱作時間複雜度為1，運行時間就是常量級。
N 在一個函數中，可能需要操作多次，而且次數隨著N的增加而增加，比如n=1，我需要執行兩個操作，n=2我就需要執行四次，這種情況下，我們將其稱作時間複雜度為N。
logN 在一個函數中，我們需要操作多次，但是將其分解成幾個小問題，每個小問題需要的操作都是整體的幾分之一，比如我們在有序的數列中查找一個數字，我們就會使用二分查找。
NlogN 在一個函數中，我們需要操作多次，每次操作都是整個問題的子問題，我們將其分解後再合併所需要的時間就是N倍的logN。比如對一組數據進行二分查找。
N^2 在一個函數中，我們需要操作多次，但是每次操作都需要花費和操作次數一樣多的時間，比如雙重循環，也比如通過遞歸來解決的fibonacci數列問題。
2^N 這種時間複雜度的函數基本就屬於暴力破解了，比如字元串匹配。在工程中，這種演算法通常是不可使用的。

所以我們在談論演算法優化的時候，通常期望將平方級的演算法優化到對數級，或將對數級的演算法優化到線性級。