Skip to main content

即使最後是相同的風景,耗費的路程與時間卻可能截然不同

演算法

這邊想先說明一下演算法的定義,一般坊間對於演算法的判定有五個要求標準:

  1. 輸入(Input):至少一個輸入
  2. 輸出(Output):至少一個輸出
  3. 明確性(Definiteness):簡單的來說就是量化,例如我考試考得很好並不明確,我考試考90分才明確
  4. 有限性(Finiteness):有限個步驟後能夠終止,簡單的來說在有限的步驟內一定會產生輸出
  5. 有效性(Effectiveness):一個演算法有沒有效,最簡單的方式就是用紙筆也能算出相同的結果

這些標準在網路上都可以找到很多資訊,不再贅述,主要會去特別提演算法的原因在於,寫程式其實不代表能夠解決一些實際的問題,如果不能構成一個演算法,顯然無法在面對特定問題時去提出一個有效的流程來處理問題;用一句比較通俗的說法叫做:[數學符號每個都懂,但沒辦法用數學搭配邏輯來解決問題]

演算法的建構能力實際上可以反映出能不能了解並解決問題的能力,一般會有以下的過程:

  1. 分析並定義問題
  2. 想出解決辦法
  3. 流程化
  4. 寫成程式語言(非必要)

在不斷的建構的同時,這些經驗未來也可以被類似的問題應用上,例如:亂數訂餐–>亂數抽獎/亂數生死籤 之類的。

但方法百百種,要如何去定義一個演算法的好壞?就像以前算數學一樣,7×7可以等於7+7+7+7+7+7+7也可以直接背出來7×7=49,答案都一樣,但顯然99乘法表十分快速節省計算紙。

複雜度

沒錯,靈芝的好壞來自多醣體,男人的好壞來自海X體,而判斷演算法的準則就在時間複雜度跟空間複雜度!如同剛剛的7×7的比較,7加7次就是一個時間複雜度高而且消耗紙張的作法,是比較差的方式,所以在演算法的定義上也是類似這樣的概念。但這個時候有人肯定會說,我7+7+7+7+7+7+7超快阿,比隔壁的老王背99乘法表超級不熟快多了。

的確!在不同的機器上運行程式會受到機體的影響,所以定義複雜的的時候,觀念必須要改為,假設執行的數量呈現倍數成長,執行時間會呈現怎樣的趨勢成長?儲存空間的消耗又是怎麼樣的趨勢成長?換句話說,如果叫你7×777,你再一個一個加給我看啊?

時間複雜度

顧名思義,要花費多少時間來執行?

用中文寫一段程式碼:

整數加總(輸入為n)
A=0
i從1開始
每次A=A+i
i=i+1回到A=A+i直到i=n+1為止
輸出A

這邊可以看到,當n變成兩倍大,計算的次數也變為兩倍,這個時候就可以定義這個演算法的時間複雜度為O(n),也就是運算時間會與執行次數呈現相同倍數成長;
如果題目修改如下:

整數加總(輸入為n)
A=0
i從1開始
j從1開始
每次A=A+i
j=j+1 回到A=A+i直到j=n+1為止
i=i+1回到A=A+i直到i=n+1為止
輸出A

這邊會發現n數量增加兩倍,計算的次數會變成四倍,此時可以知道這個時間的複雜度為O(n2),也就是運算時間會與執行次數呈現平方倍成長。

空間複雜度

同理,空間複雜度代表著需要佔用多少儲存資源,一樣沿用上面的範例,可以發現不管n怎麼改,需要記得的數字永遠只有A,i,n,也就是佔用的記憶體並不會與計算次數相關,空間複雜度為O(1),表示為常數。

基於上面的複雜度就可以判斷出一個演算法在[客觀角度下的好壞],會去強調客觀是因為並不是複雜度低就比較優,只是用假設計算量很大的時候,評估會佔用的時間以及空間;抑或是在有限的時間或資源底下,所選擇的一種方案罷了。

如果說數學的計算,空間的限制來自於紙張,那演算法的運算限制自然來自於記憶體或儲存空間,從這點來看,可以大概看出一個重要性:省時的重要性遠大於空間,原因在於儲存空間是容易取得,而時間卻是非常珍貴,[緊就是快,快就是緊!(台語)]

與我何干

嘿,既然稱為八宅老司激,肯定要給各位一些刺激,那就是演算法其實存在你我之間!一定會有人說放屁!我連程式語言長甚麼樣子都不知道,怎麼可能?

但其實說穿了,演算法只是一套流程:[將輸入經由一定的邏輯與處理之後產生輸出而已],生活中一定都會用上,例如:

你今天打算去阿如家坐坐,又想去周董那邊剪頭髮跟去Vurr喝咖啡,但必須在晚上八點前回家才能趕上鋼蛋特報,而現在是早上七點,到 阿如美家需要30分鐘,小美中午12點後不在;理髮店距離你家10分鐘,但下午才開;Vurr距離你家將近1小時,而且下午5點就關門。

請問你會怎麼安排行程?

這個安排行程就包含了演算法的五個重點特色:

  1. 輸入(Input):去三個地方而且要在八點前回家
  2. 輸出(Output):排出行程
  3. 明確性(Definiteness):各家的地址以及能夠去的時間
  4. 有限性(Finiteness):時間終究會過去
  5. 有效性(Effectiveness):有腦袋都可以安排的出來

工作上也是如此,如何利用時間複雜度以及空間複雜度來思考,並依照所擁有的資源以及時間限制來決定方案,相信不斷練習之後各位將會變成人生中的演算大師或算計大師吧!

即使耗費的路程與時間截然不同,最後卻還是相同的風景

THD

Author THD

More posts by THD

Leave a Reply