Embedded Files
張貼日期：2025/05/15
李家同
最近網路上常常看到轉傳的文章，述說台大和清大停修演算法的人數創新高。大家也許不了解為什麽台大張耀文院長對此感到非常憂心，請允許我在這裡用一些實驗結果來解釋演算法的重要性。這些實驗都是銘傳大學徐熊健教授做的，其中字串比對的演算法是清大資訊研究所博士班畢業生謝一功所提供的。
(1) 排序問題:
我們要將一些數字按大小排列，有三種方法，quick sort、selection sort和bubble sort。
假設我們有500萬個數字要在個人電腦上排序，
quick sort只要0.41秒。
selection sort要11909.60秒，大約是3.3小時。
bubble sort要31026.31秒，大約是8.6小時。
大家可以看出quick sort的速度是bubble sort的7萬5千倍。
(2) 字串比對:
假設我們有一連串的英文字This book introduces the design and analysis of algorithms.這一串字叫做目標字串。我們又有一個測驗字串analysis，我們要知道這個測驗字串在不在目標字串內。
最簡單的方法是所謂的暴力法，analysis的長度是8，所以我們逐一檢查目標字串中長度為8的字串。
以下是一個實驗的結果:
我們的目標字串是來自聖經，一共有4千4百萬個字。我們用了1千個測驗字串，每1個測驗字串的長度是11，用以上的暴力演算法，需要6秒鐘的時間。參考數字串比對演算法所需要的時間只有0.0018秒。
結論是，參考數字串比對演算法比暴力演算法快了3333倍。
(3) minimal spanning tree問題:這個問題我就不解釋了。
這個問題可以用窮舉法和Prim演算法來解決。
以n=13為例，用Prim演算法，所花的時間小於0.001秒。
如果用窮舉法，需要56個小時。
如果n=20000，用Prim演算法，只需要1.31秒。
如果用窮舉法，恐怕要花上幾年功夫。
結論是，如果一個人根本不會演算法，就根本不能利用minimal spanning tree，但是minimal spanning tree在網路設計上是非常有用的。
(4) 傅葉爾轉換:
傅葉爾轉換在工程上是非常重要的一個數學題目，
當n=131072，用普通方法計算，所需要的時間是359.644秒。
當n=131072，如果使用快速傅葉爾轉換，只需要0.014秒。
結論是，快速傅葉爾轉換的速度大約是一般傅葉爾轉換速度的26000倍。
我們都希望軟體工程師可以在很短的時間內完成計算，如果不會演算法，軟體工程師只能土法煉鋼。這是絕對不行的。為何台大、清大有很多學生停修演算法，多多少少是因為演算法牽涉到數學。教育部實在應該檢討108課綱減少了必修課，會不會因此降低了我國菁英份子的數學能力。
最近中國DeepSeek軟體表現得非常好，他們用的硬體是比較便宜的，很顯然的，中國的演算法教育是很成功的。但是要學好演算法，基本的數學和邏輯思考能力卻是絕對必要的。
Page updated
Report abuse