演算法核心——空間複雜度和時間複雜度超詳細解析
- 2019 年 11 月 14 日
- 筆記
演算法核心——空間複雜度和時間複雜度超詳細解析
一、什麼是演算法
演算法：
- 一個有限指令集
- 接受一些輸入(有些情況下不需要收入)
- 產生輸出
- 一定在有限步驟之後終止
- 每一條指令必須：
- 有充分明確的目標，不可以有歧義
- 電腦能處理的範圍之內
- 描述應不依賴於任何一種電腦語言以及具體的實現手段
其實說白了，演算法就是一個計算過程解決問題的方法。我們現在已經知道數據結構表示數據是怎麼存儲的，而“程式=數據結構+演算法”，數據結構是靜態的，演算法是動態的，它們加起來就是程式。
對演算法來說有輸入，有輸出，相當於函數有參數有返回值。我們寫演算法的時候習慣把演算法封裝到一個函數中。
二、什麼是好的演算法
好，從上面我們知道了什麼是演算法，下面我再說什麼是好的演算法？
在解決同一個問題的時候，我們通常會有很多種不一樣的演算法，區別就在於，有的演算法比較笨，有的演算法比較聰明，那我們怎麼去衡量它們誰好誰壞呢？我們通常有下面兩個指標：
- 空間複雜度:根據演算法寫成的程式在執行時佔用存儲單元的長度。
- 時間複雜度：根據演算法寫成的程式在執行時耗費時間的長度。
先舉個例子說，如果讓你列印十個整數，你那個程式可能瞬間就給出結果了，如果讓你列印十萬個整數呢？這你就得多等一會了。所以這個程式運行的時間，就跟你要處理的數據是十個還是十萬個是相關的，這個十或十萬就是我們要處理的數據的規模。我們把它叫做n，是一個變數的話，那我們這個程式所用的時間和空間都跟這個n是有直接關係的。解決一個問題有很多中不同的方法，你在設計這個方法的時候，一定要把這兩個要素考慮清楚。一不小心，如果空間複雜度太大的話，你那個程式就可能直接爆掉了，非正常中斷，我一會會在後面講，時間複雜度如果太大的話，你就可能等很長時間都等不出結果。
時間複雜度
先來看上面圖片中的幾組程式碼，我是用Python表示的，你在看的時候考慮兩個問題：
- 四組程式碼中，哪組的運行時間最短？
- 用什麼方式來體現演算法運行的快慢？
剛才說n可以看作數據的規模，規模不一樣，運行時間肯定也不一樣，而且所用時間也不好確定，不同的n會得到不同的時間，所以我們用時間複雜度來表示演算法運行的快慢。
先來看下面圖片中的幾個生活中的事件，估計時間：
這裡你會發現我們會用“幾”表示一個大概，後面還有相應的時間單位，那時間複雜度也參照類似的方法：
時間複雜度：用來評估演算法運行效率的一個式子
看上面圖片所示，先說print(‘Hello World’),它的時間複雜度表示為O(1),O嚴格來說，它表示數學上一個式子的上界，我們可以簡單的理解為就是一個估計，大約，相當於上面說的“幾”。1可以理解為是個運行單位(類似於秒這樣的單位)，為什麼是O(1)，因為print(‘Hello World’)只執行了一次，同理分析第二個：
for i in range(n):
print('Hello World')
它的時間複雜度表示為O(n)，因為這組程式碼執行了n次。n還是個單位，同理，分析第三個：
for i in range(n):
for j in range(n):
print('Hello World')
它的時間複雜度表示為O(),因為是有兩層循環，所以是
,
還是個單位。第四個你自己就可以分析了，我就不多此一舉了。但千萬不要以為就是這麼簡單，咱再看下面程式碼圖片：
看到這個圖片，你是不是感覺很良好，和你猜的差不多是吧，哈哈，不要高興的太早，告訴你們，錯了，它們的時間複雜度不是這樣的。
為什麼？我說了，“1”是單位，但“3”不是單位，3是3乘1，就比如說在生活中，問你一壺水燒多長時間，沒有人回答說是三個幾分鐘或者幾個三分鐘。再說第二個，是單位，n也是個單位，但是
比n大，所以我們在估計時用大單位，就好比生活中問你大概睡了多久，你一般說是幾個小時，而不是說幾個小時零幾分鐘，你強調的是一個大概的時間，明白了吧。
所以正確的時間複雜度是這樣的：
第一個為什麼是O(1),首先print(‘Hello World’)列印一次和列印三次實際的影響不大吧，就是不管執行幾次，只要它的規模不上升到n這麼大的時候，換句話說，1是個單位，所以不管怎樣，因為這是表示近似，不是表示精確的，所以是O(1).好，再看下面這個圖片：
當你的循環減半的時候，時間複雜度就會變為O(logn)。所以你可以這樣記，當演算法過程出現循環折半的時候，複雜度式子中會出現logn。
時間複雜度小結
- 時間複雜度是用來估計演算法運行時間的一個式子(單位)
- 一般來說，時間複雜度高的演算法比時間複雜度低的演算法慢
常見的時間複雜度(按效率排序)
複雜問題的時間複雜度
如何簡單快速地判斷演算法複雜度
空間複雜度
在空間複雜度中需要注意的一點就是理解“空間換時間”，在研究一個演算法的時候，時間比空間重要。
