怎樣才是一個好算法：空間復(fù)雜度 & 時間復(fù)雜度?

大家好，歡迎來到 Crossin的編程教室 ！

“算法”是一個我們經(jīng)常在編程學(xué)習(xí)、求職面試時聽到的一個詞。那么，什么是算法？以及如何評價一個算法的好壞？今天我們就來給大家說一說。

一、什么是算法

算法：

• 一個有限指令集

• 接受一些輸入(有些情況下不需要收入)

• 產(chǎn)生輸出

• 一定在有限步驟之后終止

• 每一條指令必須：

1. 有充分明確的目標，不可以有歧義

2. 計算機能處理的范圍之內(nèi)

3. 描述應(yīng)不依賴于任何一種計算機語言以及具體的實現(xiàn)手段

其實說白了，算法就是一個計算過程解決問題的方法。我們現(xiàn)在已經(jīng)知道數(shù)據(jù)結(jié)構(gòu)表示數(shù)據(jù)是怎么存儲的，而“程序=數(shù)據(jù)結(jié)構(gòu)+算法”，數(shù)據(jù)結(jié)構(gòu)是靜態(tài)的，算法是動態(tài)的，它們加起來就是程序。

對算法來說有輸入，有輸出，相當(dāng)于函數(shù)有參數(shù)有返回值。我們寫算法的時候習(xí)慣把算法封裝到一個函數(shù)中。

二、什么是好的算法

好，從上面我們知道了什么是算法，下面我再說什么是好的算法？
在解決同一個問題的時候，我們通常會有很多種不一樣的算法，區(qū)別就在于，有的算法比較笨，有的算法比較聰明，那我們怎么去衡量它們誰好誰壞呢？我們通常有下面兩個指標：

• 空間復(fù)雜度:根據(jù)算法寫成的程序在執(zhí)行時占用存儲單元的長度。

• 時間復(fù)雜度：根據(jù)算法寫成的程序在執(zhí)行時耗費時間的長度。

先舉個例子說，如果讓你打印十個整數(shù)，你那個程序可能瞬間就給出結(jié)果了，如果讓你打印十萬個整數(shù)呢？這你就得多等一會了。所以這個程序運行的時間，就跟你要處理的數(shù)據(jù)是十個還是十萬個是相關(guān)的，這個十或十萬就是我們要處理的數(shù)據(jù)的規(guī)模。我們把它叫做n，是一個變量的話，那我們這個程序所用的時間和空間都跟這個n是有直接關(guān)系的。解決一個問題有很多中不同的方法，你在設(shè)計這個方法的時候，一定要把這兩個要素考慮清楚。一不小心，如果空間復(fù)雜度太大的話，你那個程序就可能直接爆掉了，非正常中斷，我一會會在后面講，時間復(fù)雜度如果太大的話，你就可能等很長時間都等不出結(jié)果。

時間復(fù)雜度

1. 四組代碼中，哪組的運行時間最短？

2. 用什么方式來體現(xiàn)算法運行的快慢？

剛才說n可以看作數(shù)據(jù)的規(guī)模，規(guī)模不一樣，運行時間肯定也不一樣，而且所用時間也不好確定，不同的n會得到不同的時間，所以我們用時間復(fù)雜度來表示算法運行的快慢。
先來看下面圖片中的幾個生活中的事件，估計時間：

for?i?in?range(n):
????print('Hello?World')

它的時間復(fù)雜度表示為O(n)，因為這組代碼執(zhí)行了n次。n還是個單位，同理，分析第三個：

for?i?in?range(n):
????for?j?in?range(n):
????????print('Hello?World')

它的時間復(fù)雜度表示為O(),因為是有兩層循環(huán)，所以是,還是個單位。第四個你自己就可以分析了，我就不多此一舉了。但千萬不要以為就是這么簡單，咱再看下面代碼圖片：

看到這個圖片，你是不是感覺很良好，和你猜的差不多是吧，哈哈，不要高興的太早，告訴你們，錯了，它們的時間復(fù)雜度不是這樣的。
為什么？我說了，“1”是單位，但“3”不是單位，3是3乘1，就比如說在生活中，問你一壺水燒多長時間，沒有人回答說是三個幾分鐘或者幾個三分鐘。再說第二個，是單位，n也是個單位，但是比n大，所以我們在估計時用大單位，就好比生活中問你大概睡了多久，你一般說是幾個小時，而不是說幾個小時零幾分鐘，你強調(diào)的是一個大概的時間，明白了吧。
所以正確的時間復(fù)雜度是這樣的：

時間復(fù)雜度小結(jié)

• 時間復(fù)雜度是用來估計算法運行時間的一個式子(單位)

• 一般來說，時間復(fù)雜度高的算法比時間復(fù)雜度低的算法慢

常見的時間復(fù)雜度(按效率排序)

復(fù)雜問題的時間復(fù)雜度

如何簡單快速地判斷算法復(fù)雜度

空間復(fù)雜度