時間複雜度與空間複雜度 Time Complexity and Space Complexity


上一篇了解了基本的演算法概念後,我們知道了需要針對不同的資料集或問題、不同的處理環境與不同的目標來選用不同的演算法。

那我們要怎麼知道一個演算法的設計好不好或是適不適合呢?

時間複雜度 Time Complexity

進行演算法抉擇時所要考慮的最重要的因素之一為:能夠完成結果的速度

演算法的時間複雜度是指演算法需要消耗的時間資源。

白話一點來說,今天老師出了一個作業,要學生寫一個程式解決這個問題,A同學寫了50行的代碼,而B同學寫了200行代碼,乍看之下會覺得A同學寫的程式比較好,因為代碼比較少,但是在執行的時候,A同學的程式要跑3秒才能完成執行,而B同學的程式卻只要跑1秒就能執行,這樣看來是不是反而代表說其實 B 寫的程式是比 A 寫的好呢?

當我們去計算電腦執行一個程式所需要的時間,這個概念就稱為時間複雜度。

評比一個演算法到底好不好的最客觀的方法就是利用時間複雜度和空間複雜度了。

當然我們不時真正用時間去算一個演算法的時間複雜度。每台電腦執行同一個城市的時間本來就會因為電腦的效能去做決定,執行同一個程式執行的時間本來就會因為電腦的效能而不同,這裡我們會用演算法執行需要幾個指令來做計算。

常見的效能分類如下,其中是以效率遞減的順序排列:

  • 常數:O(1)

  • 對數:O(log n)

  • 次線性: O(n^2) 且d<1

  • 線數:O(n)

  • 線性對數:O(n logn)

  • 指數: O(2^n)

隨著問題規模n的不斷增大,上述時間複雜度不斷增大,演算法的執行效率越低。

空間複雜度 Space Complexity

A 跟 B 寫出來的程式丟在電腦上執行須要花費的時間是一樣的,但 A 的卻需要更多的記憶體資源,這樣一來我們也會認為 B 的程式比 A 好,因為它更省電腦資源,所以當我們的程式在執行時所需要耗費多少的記憶體資源,這樣的概念就稱為空間複雜度。


圖片
圖片
圖片
圖片
圖片
圖片
(使用 Facebook 留言外掛程式 留言無法滿足本網站參加活動之資格,僅供非會員討論使用)
互動地圖
interactive taiwan map