#
時間複雜度 (Time Complexity)用來表示程式執行的時間與速度表現。通常與程式內的演算法有關,
例如,當我們再加入一個 input 到某程式時,執行時的時間會變久嗎?多了多久?等等...
這通常會在您面試時的上機考,題目會限制您的程式執行時間,
或是在白板題,面試官會要您描述為什麼兩支程式速度不同?或者某程式該如何改進...
#
範例說明這邊用前面幾篇的題目來說明時間複雜度,體會一下:
#
回顧字串反轉來說明一種時間複雜度在我們之前的章節,字串反轉
上面程式,我們的 str
字串,假如再多加一個字元,就會讓回圈多跑一次,
這個時間複雜度我們稱為 線性時間(Linear Run Time),也稱為 N
。
#
回顧樓梯測驗來說明另一種時間複雜度再看一下我們前幾章的樓梯測驗:
在樓梯測驗中 n
每增加一次,都會多跑好幾次(n * n 次):
這時我們稱這種時間複雜度為 平方時間(Quadratic Time Complexity)。也稱為 N^2
。
#
其他常見時間複雜度這邊稍微說明一下常見的時間複雜度,在面試或上機考時,可能會遇見其中一種,或是兩種的結合:
#
常數時間(Constant Time)表示法:
1
輸入到程式的資料量增加,但執行時間不變:
比如有個神奇的演算法可以把樓梯測驗寫成 n
增加但時間不變,那這種時間複雜度就是常數時間。
#
對數時間(Logarithmic Time)表示法:
log(n)
輸入到程式的資料量增加,但執行時間一開始增加,到一定程度後無明顯增加。
這種情況會發生在做二元搜尋的時候,後面章節我們會介紹。
#
線性對數時間 (Quasilinear Time)表示法:
n * log(n)
通常在比較排列時會用到,比如以下所需的時間:
新的班級座號都是隨機的,這時要用姓名的筆畫多少來排列,修正座號順序,然後在新的座號表上寫上新的座號。
#
指數時間(Exponential Time)表示法:
2 ^ N
隨著輸入資料變多,需要執行的時間以指數增加。
通常我們會避免這種演算法,因為這是時間效率最不好的。因此面試時要盡量避免。
此文同時發佈於鐵人賽