演算法 1:做菜與演算法、複雜度與大歐小歐


Posted by Lai Yen Ju on 2020-06-17

演算法是什麼

演算法是由能夠一步步解決問題的步驟所組成,就像是料理新手學習做一道菜時,通常會跟著食譜一步一步做出來,這時候「食譜」可以說是做出料理的演算法。

假設我今天想學做麻婆豆腐,所以去 Google 麻婆豆腐該怎麼做,結果發現有超多食譜在教人怎麼做出麻婆豆腐,接下來就要開始考量以下問題,選出一份適合我的麻婆豆腐食譜:

  1. 根據這份食譜,我大概需要花多久時間才能做出來?
  2. 家裡放得下食譜中需要採買的食材嗎?
  3. 食譜中需要的食材或廚具會不會很貴?
  4. 不想出門買菜的話,我能根據這份食譜用家中現有的食材做嗎?
  5. 如果我照著這份食譜做,有信心做出成功的麻婆豆腐嗎?

好的演算法 vs 不夠好的演算法

如果把一個電腦程式看作演算法,就像食譜一樣,需要考慮類似的問題,而衡量這些問題的評估方式也不同:

  1. 花的時間 → 時間複雜度
  2. 佔用的空間 → 空間複雜度
  3. 正確率 → 實際跑過超多次,看看是否都能成功;或者以理論判斷
  4. 相容性 → 在 Windows 跟 MacOS 分別跑過,看是否能運作
  5. 開發成本 → 是不是需要額外學習新的理論或技術

複雜度 Complexity

複雜度的全稱是「漸進複雜度」,主要是從時間與空間的角度來評估演算法的好壞。

  • 時間複雜度(Time Complexity):執行時間的長短
  • 空間複雜度(Space Complexity):佔用的儲存空間大小

複雜度會受到量級影響,不同時間複雜度/空間複雜度的演算法,在處理大規模資料時,可以看出在時間與空間上的優劣差異。

精確衡量複雜度的方式:大歐跟小歐

說到要比較不同演算法的複雜度,要比較的是當資料量變多時,演算法成長的速度。

假設演算法動一次步驟,花費的時間都是一樣的,這個步驟次數就是 n。因為要模擬處理大規模資料的情境,所以會假想當 n 趨近無窮大來比較複雜度。

極限概念 1
當 n 趨近無窮大,哪個總和會比較大?

  • $3n^2 + n + 20$ 與 $100n$
  • $n^{100}$ 與 $2^n$
  • $n^2$ 與 $10_nlog n$
  • $100^n$ 與 $n!$
  • $30*2^n$ 與 $3^n$
  • $100n$ 與 $200n$

極限的概念 2
上面的比較方式,只單純比較總和結果,但如果只比較總和結果其實不準,就像 A 第一次跟第二次的考試成績分別是 80 跟 100,B 則是 40 跟 50,但 $\frac{80}{40} = \frac{100}{50}$,兩人的進步幅度(成長速度)是相同的,而複雜度要比較的也是成長的速度,為了知道成長的速度差距,就會像前面計算兩人成績的方式一樣,將比較的兩個數相除

  • 在 n 趨近無限大時,$\frac{f(n)}{g(n)}$ 的結果趨近於 0,表示 f(n) 的成長速度比 g(n) 小
  • 在 n 趨近於無限大時,$\frac{f(n)}{g(n)}$ 的結果也趨近於無限大,表示 f(n) 的成長速度比 g(n) 大
  • 否則當兩者是一樣量級,也就是成長速度差不多快

現在問題來了,由於都在假設 n 趨近無限大的情況下比較複雜度量級,每次都要假裝將 n 帶入後心算結果,不論怎麼想都覺得麻煩,所以有了特殊符號,能以簡潔的方式表示複雜度,方便人快速做判斷。這些特殊符號有很多種類,這裡只說明大歐(Big-O)、小歐(Little-o)跟(Big-theta)三種。

大歐(Big-O)

  • 通常記為 $O(f(n))$
  • $f(n)$ 指的是複雜度量級的上界(最大值),實際執行的結果可能會比用(Big-O)紀錄的數值小。

以下是將演算法改用為大歐符號表示的例子:

演算法算式 複雜度符號
$3n^2 + n + 20$ $O(n^2)$
$100n$ $O(n)$
$n^{100}$ $O(n^{100})$
$2^n$ $O(2^n)$
$n^2$ $O(n^2)$
$10nlog n$ $O(nlogn)$
$100^n$ $O(100^n)$
$n!$ $O(n!)$
$100n$ $O(n)$
$3^n$ $O(3^n)$
$30*2^n$ $O(2^n)$
$200n$ $O(n)$

下圖則表示當資料量變多時,每種大歐需要執行的步驟,例如:$O(1)$ 表示輸入的數值大小與需要執行的步驟無關,執行步驟不受輸入數值影響。

小歐(Little-o)

  • 記為 $o(f(n))$
  • $f(n)$ 指的是複雜度量級的嚴格上界(絕對的最大值),代表實際執行的數值一定會比轉成 $o(f(n))$ 紀錄的數值小

例如 $3n^3 + 5n^2 + 10n + 3$,以大歐(Big-O)紀錄是 $O(n^3)$,但在小歐(Little-o)要記錄成 $o(n^4)$。兩者的複雜度量級不同。

(Big-theta)

  • 記為 $θ(f(n))$
  • $f(n)$ 指的是複雜度量級的嚴格上下界,實際執行的數值與(Big-theta)紀錄的數值完全相同。代表不管用哪種複雜度符號紀錄,結果都屬於相同複雜度量級,不會像 $3n^3 + 5n^2 + 10n + 3$,以不同複雜度符號紀錄時,會有不同結果。

這篇文章大致說明了演算法的概念、評估演算法好壞的方式、不同的時間複雜度量級、表示時間複雜度的方式。由於剛接觸演算法,還沒真實體驗到演算法在實務開發的重要性,較難以實際案例比較不同複雜度的演算法。但跟著程式導師計畫的課程進度往下走,下篇內容預計是排序用的演算法,順便了解一個演算法的最理想情況與最壞情況。


參考資料


#演算法 #複雜度 #程式導師計畫 #程式導師計畫第四期







Related Posts

Checked and Unchecked Exception in Java

Checked and Unchecked Exception in Java

【Day02】一起來建立靜態頁面吧

【Day02】一起來建立靜態頁面吧

【Day07】總複習!摻在一起做成...

【Day07】總複習!摻在一起做成...


Comments