算法核心——空間複雜度和時間複雜度超詳細解析

admin 環保清潔

算法核心——空間複雜度和時間複雜度超詳細解析

一、什麼是算法

算法：

  • 一個有限指令集
  • 接受一些輸入(有些情況下不需要收入)
  • 產生輸出
  • 一定在有限步驟之後終止
  • 每一條指令必須：
  1. 有充分明確的目標，不可以有歧義
  2. 計算機能處理的範圍之內
  3. 描述應不依賴於任何一種計算機語言以及具體的實現手段

其實說白了，算法就是一個計算過程解決問題的方法。我們現在已經知道數據結構表示數據是怎麼存儲的，而“程序=數據結構+算法”，數據結構是靜態的，算法是動態的，它們加起來就是程序。

對算法來說有輸入，有輸出，相當於函數有參數有返回值。我們寫算法的時候習慣把算法封裝到一個函數中。

二、什麼是好的算法

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

  • 空間複雜度:根據算法寫成的程序在執行時佔用存儲單元的長度。
  • 時間複雜度：根據算法寫成的程序在執行時耗費時間的長度。

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

時間複雜度

先來看上面圖片中的幾組代碼，我是用Python表示的，你在看的時候考慮兩個問題：

 

  1. 四組代碼中，哪組的運行時間最短？
  2. 用什麼方式來體現算法運行的快慢？

剛才說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。

 

時間複雜度小結

  • 時間複雜度是用來估計算法運行時間的一個式子(單位)
  • 一般來說，時間複雜度高的算法比時間複雜度低的算法慢
常見的時間複雜度(按效率排序)

複雜問題的時間複雜度

如何簡單快速地判斷算法複雜度

空間複雜度

在空間複雜度中需要注意的一點就是理解“空間換時間”，在研究一個算法的時候，時間比空間重要。

 

此篇完

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?