Ok, 那就讓我們書接前文,來幫大家科普一下什麼叫做「時間複雜度」與「空間複雜度」。 一、時間複雜度 Time Complexity
在看完 Jason 簡介演算法的文章以後,應該對什麼是時間複雜度有一點概念了!
簡單的來說就是,電腦執行演算法所需要耗費的時間成本。 而這個時間成本並不是真的說電腦花了幾分鐘或花了幾秒鐘執行這個演算法這樣,畢竟每台電腦的計算能力是不一樣的!就像你總不會認為一個在超級電腦上需要跑 1分鐘的程式A,跟另一個在你家電腦上跑 1分鐘的程式B,它們兩個的複雜度會一樣吧... 所以我們會用這個"演算法執行需要幾個指令"來做計算 ( 暫時忽略每個指令執行須要的時間 )。 接著下面舉個例子,來帶你們看一下是要怎麼計算。
Example
在上面的範例裡面名為 example 這個 function,總共需要執行:
1 + (n+1) + n*(n+1) + n*n + (n+1) + n = 2(n*n) + 4n + 3 個指令 但是由於精確計算演算法的執行步驟或時間的工作過於繁瑣。 通常我們會用電腦處理的是大量的資料,我們更關心在資料量非常大的時候,演算法是否夠好。 這時候我們通常會用 Big O 來表示: 只需要看最高次方項,並且可以忽略掉項次前的係數,寫做:O(n^2) 即可。 演算法複雜度的表示方法除了Big O之外,還有:Ω 和 Θ 。 但是這兩個東西我們就比較少拿出來做討論,Jason 覺得吧 這兩個東西留給那些考研的去弄懂就好了! 一般在 Coding 或者職場工作上跟人討論演算法,知道 Big O 基本上就夠用了。 接下來 Jason 會再提幾個範例,讓各位更了解 Big O。
O(1)
像上面這個程式,當你今天 n 不管輸入多大的時候,其實它都不會影響程式的執行時間。
這種程式的時間複雜度我們就會寫作:O(1)
O(n)
而像上面這個程式,很明顯就會因為輸入 n 的大小而影響裡面 for迴圈要做幾次。
時間複雜度寫作:O(n)
O(n^2)
而這個例子基本上就跟上一個差不多,因為我們只需要看最高次方項,輸入n 會被巢狀的 for迴圈做 n*n 次,故時間複雜度寫作:O(n^2)
常見的複雜度還有:O(n)、O(log n)、O(n log n)、O(n^2)、O(2^n) 等,我們可以從下圖中觀察到,隨著 n 越來越大的時候,各個不同複雜度彼此間的增長幅度。 二、空間複雜度 Space Complexity
再來要講的是「空間複雜度」,它的概念跟時間複雜度是相仿的。
簡單的來說就是,電腦執行演算法所需要耗費的空間 ( 記憶體 ) 成本。 一般來說「時間複雜度」與「空間複雜度」之間是可以相互 trade off 的! 而相互 trade off 的意思是: 在某些情況底下,我們是可以讓程式多用一些記憶體空間來多記一些資訊,就可以省去一些重複的運算來加速程式的執行時間;或者我們完全沒有多餘的記憶體資源可以使用,也可以透過把一些原本可以靠記憶體存儲的資訊改用重複計算的方式來取得。 這部份可以參考 Jason 之前寫的【演算法】排序演算法 Sorting Algorithm,一樣是要做排序像 Bubble Sort 就不需要額外的記憶體空間 ( 但是做起來比較久 );Bucket Sort 就需要大量額外的記憶體空間 ( 但是做起來比較快 )。 至於「空間複雜度」科學符號表示的部分,我們跟時間複雜度一樣是用 Big O。
O(1)
像這個程式不會因為 n 輸入的大小而影響需要使用的記憶體容量,故空間複雜度為O(1)。
O(n)
這個程式很明顯就會因為輸入 n 的大小而影響它會使用的記憶體容量,空間複雜度為O(n) 。
Ok, 那這樣大家對「時間複雜度」與「空間複雜度」都有一個基本的瞭解了,以及Big O 是什麼、要怎麼計算大概也知到了!我想這篇寫到這邊大概也可以功成身退了xD 那我們就下一篇再見,謝謝。
13 評論
Steven
5/5/2021 10:44:57
Hi, Jason,
回覆
Jason Chen
5/11/2021 22:46:50
好的,感謝您。
回覆
OTTO
11/11/2022 17:25:48
這個講的概念跟一個遊戲很像,可以介紹給你搭配,更能體會,7 billiion humans
回覆
beginner
2/7/2023 16:47:07
for(i=0;i<n;i++)
回覆
Jason Chen
2/7/2023 19:47:38
Hi beginner,
回覆
beginner
2/8/2023 08:57:31
抱歉問題沒有描述清楚,
Jason Chen
2/8/2023 09:39:16
Hi beginner,
Justin
2/21/2023 16:56:16
講解得非常詳細,受益不少。有個疑問想請教一下。
回覆
Jason Chen
2/22/2023 10:07:37
Hi Justin,
回覆
Jason Chen
2/22/2023 10:12:12
也就是說, 前面的 n 是因為 j 迴圈寫在 i 迴圈裡面, 然後因為 i 迴圈的關係所以會被執行 n 次,後面的 (n + 1) 就是 j 迴圈本身執行的次數。
Justin
4/18/2023 15:36:54
原來如此,完全了解了。您解釋的好詳細,一看就懂了。感謝您 。:)
黃
10/16/2023 13:21:48
x=x+1執行次权
回覆
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|