目錄
如何衡量一個電腦科學問題複雜程度
要怎麼衡量一個電腦科學問題要運算多久的時間？我們可以說這個問題在我的電腦上跑10秒來衡量這個問題執行的很快嗎？
答案是不能的，同一個問題在超級電腦上跑可能不到一秒，但放到2009年的第一代Pentium CPU上跑，運算的時間也許超過100秒。執行時間的長短不是用來衡量問題複雜程度的好方法。那麼我們可以怎麼量化運算多久呢？
這個問題可以簡化成 “完成這個問題，電腦要經過幾次的計算”，這樣就不牽涉電腦的CPU能力了。更白話的說，就是計算電腦要解決這個問題，需要做幾次操作。
舉一個例子，華容道這款遊戲是一個在平面中平行或是垂直移動方塊的遊戲，目的就是找到最少的移動次數來讓其中一個方塊移動到指定位置，老經驗的玩家看到擺盤，大概就可以估算出要操作幾次才能完成任務。
回到電腦科學的問題，我們就是要估算出解決這一道問題需要幾次的操作，估算出來的數值就是所謂的時間複雜度 (time complexity)，或者稱為 Big-O。這個名詞非常重要，一定要牢記，在學習資料結構與演算法一定會常常看到這個名詞，在資料結構與演算法的世界，即便要解決同一個問題都有非常多種不同的方法，如何快速找到符合使用情境的方法，都可以透過時間複雜度來查找。
舉例來說，都是要用到List的功能，這個List很頻繁的操作新增刪除的行為，那麼我就應該要選擇 LinkedList而不是ArrayList。
時間複雜度種類
衡量一個資料結構或演算法的好壞取決於他的時間複雜度的程度，時間複雜度這裡先簡單介紹幾個比較常看到的種類，如 
常數時間(Constant time)、
對數時間(Logarithmic time)、
線性時間(Linear time)、
平方時間(Quadratic time)。
常數時間(Constant Time)
計算次數永遠是1次，不會因為資料量的大小而影響運算的次數。舉例來說，取得ArrayList的第10的index的資料就是一個常數問題。這個運算次數永遠只會一次，不管這個ArrayList的元素個數有1000個或者是10萬個，取 index =10 的操作就是一次。
常數時間是演算法裡面的God，每個人都希望系統用到的演算法或資料結構時間複雜度是 O(1)，而資料結構當中就有一個家族是神級的存在，在沒有碰撞下(Collision)，HashMap的 get()、add()、remove() 都是O(1)常數時間，未來我們會對Map家族做深入的探討。
常數時間複雜度我們寫成 O(1)
對數時間(Logarithmic Time)
當演算法問題在選擇要處理的資料時，往往這些資料會被分成好幾類(至少2類以上)，而你必須在這些元素群中選擇一個。
舉例來說，若想在電話簿中搜尋 “郝簡單先生” 的電話，你不會從電話簿的第一筆開始找，你會直接找到姓氏是 “郝”的區域，這樣就會減少非常多的搜尋時間，手機的電話簿就是針對姓氏分成好幾群。
像是這種分散克服(divide and conquer)的方法，其演算法的時間複雜度就會是對數時間。另外一個很有名的對數時間演算法就是二元搜尋樹，如下圖所示，這個演算法將資料建構在二元樹上，當要搜尋時都是在這棵二元樹的左邊或是右邊找尋下一個目標，這個作法就是把下一個要搜尋的資料分成兩類，是一種對數時間複雜度的演算法。當要找3這個資料首先從最上面的4開始，因為3小於4所以走左邊，碰到2後由於3大於2所以走2的右邊，如此一來就找到3了。
對數時間複雜度我們寫成 O(log n)
線性時間(Linear Time)
處理問題的次數與輸入資料量正相關，若有 n 個資料量則需要處理 n 次。最經典的問題就是搜尋一個 n 個元素的陣列，你要找到需要的元素最慘的情況下會需要找 n次。舉例來說有一個 5個元素的ArrayList，ArrayList內的資料有數字 [3, 8, 1, 200, 7]。你要在這個ArrayList內找數值最保險的方式就是一個一個找，如果要找3 當然是處理一次就找到了，但是如果要找7這個元素，那麼就要花5次也就是整個資料量的次數，而時間複雜度基本上要看的是最糟糕狀況(worst case)。
對數時間複雜度我們寫成 O(n)
平方時間(Quadratic Time)
處理問題的次數會跟著輸入的資料量n成次方比例的增加，比較經典的問題如選擇排序。這裡我們用文字並搭配圖例說明一下選擇排序這個演算法。有一個陣列裡面有數字元素 36, 18, 45, 9, 16五個元素，我們想要由小到大進行排序，排序的結果希望是 9, 16, 18, 36, 45。
選擇排序的操作(文字說明如下)
首先選擇排序的要點就是從還沒有排序過的元素中找到一個最小的把它與還沒排序過的最前面元素交換位置，所以第一次會找到 9 並且跟36對換
[ 36, 18, 45, 9, 16 ] 變成 [ 9, 18, 45, 36, 16]
接下來從 18, 45, 36, 16 再選擇最小的是16並且與18對換
[ 9, 18, 45, 36, 16 ] 變成 [ 9, 16, 45, 36, 18 ]
再來是 45,36,18裡面選擇，選擇18與45對換
[ 9, 16, 45, 36, 18 ] 變成 [ 9, 16, 18, 36, 45 ]
再來是 36, 45 內選擇，選擇 36跟36對換(就是跟自己換XD)
[ 9, 16, 18, 36, 45 ] 變成 [ 9, 16, 18, 36, 45 ]
當碰到最後一個元素的時候，排序就完成了。
我們來分析一下，假設陣列中有 n個元素，那麼第一次可能需要搜尋 n 次找到最小值進行對換。接著我們分析第二次需要搜尋的次數，第二次會從第二個元素開始搜尋對吧，因為第一個元素已經被我們確定好了，所以需要搜尋的元素就是 n-1 個。第三次的話就是 n-2，依此類推到最後一次就是1。
這樣的數學式我們可以把它寫成 n + (n-1) + (n-2) + (n-3) + … + 1 ，這個數列可以推導成 (n+1) * n /2 ，我們把n 乘進去變成 (n² + n) /2 這樣的公式。
接著，有一個規則必須要熟記，時間複雜度只關心最高次項，而忽略其低次項，以及所有的係數來簡化表達方法。舉例來說 n³ + n² + n 這樣的方程，時間複雜度會寫成 O(n³)，其原因是只取方程的最高次項。
為什麼要這麼做呢？原因是當n無敵大的時候，係數與低次方的項都不足以造成影響。若我們把數字帶入到這個方程式 n² + n，試想當 n 有200萬的時候 n²的數值是 4兆，而 n 就只有200萬，相較之下 n 是不是就遜色很多，這也是我們會把低次項與係數忽略掉的原因。
用程式碼判斷複雜度
對數時間
程式碼在處理 for迴圈的時候，每一次的參數都少一半。
線性時間
當for 迴圈的上界是 input 的參數個數時，時間複雜度就是線性時間。
平方時間
平方時間複雜度很明顯可以看到有兩層 for迴圈在主導著演算法。
小技巧，一般程式碼除非使用到遞迴處理，通常都是用 for-loop 來看，for-loop的上界 i< xxx，以及共有幾層 for-loop 就可以粗略的判斷出該演算法的時間複雜度。
時間複雜度比較
四個時間複雜度的執行時間從快排到慢是這樣的
O(1) < O (logn) < O(n) < O(n²)
下表列出輸入參數的個數對應各個時間複雜度所需要執行的步驟。
O(1)常數時間飛快無比，不管有幾個輸入的參數，他的執行步驟永遠都是常數次，而O(log n) 介於 O(n) 與 O(1)之間，雖然執行時間會隨著輸入的參數變多而變長，但隨著輸入的參數越來越多，所執行的步驟也不會增長的很快。而平方時間的效率最差勁，可以但到當輸入參數是 1024個，執行步驟就需要 約104萬次。所以我們在設計系統的時候，一定要盡可能的使用時間複雜度低的演算法或是資料結構喔。
下圖是用圖表的方式來描述時間複雜度。不論是表格或者試圖跟很明確的告訴程式設計師，當演算法已經到 O(n²) 的時候，千萬要開始思考優化的方式。否則執行時間會以倍數成長。
時間複雜度總結
- 估算演算法或資料結構運算的快慢，不可以用執行時間來看，要用執行次數也就是時間複雜度來看。
- 估算時間複雜度的符號是Big-O annotation，我們會用 O( ) 來表示。
- 在估算 O()的時候，有多次項我們只取最高次項的那一個，例如 n³ + n² + n 我們會寫 O(n³)
- 在估算 O()的時候，我們會將係數去掉， ½ n² ，使用Big-O表示為 O（n²)
- 追蹤程式碼來判斷時間複雜度時，可以觀察程式碼使用幾層的迴圈，與迴圈終止的參數來做初步判斷