程式寫好跑不完？Time Limit Exceeded怎麼辦？
前言
在這個時代，程式可說是全民運動，不論科系、目的皆有機會碰到程式。程式說好上手其實也不容易，若只憑直覺寫程式的話可能會遇到一些問題。本篇將簡單介紹一下在寫程式時容易遇到的問題：Time Limit Exceeded （TLE）。
像 LeetCode 等 judge system 為了不讓讀者每次的 submit 佔過多的時間，都會設定時間的上限，因此 TLE 的意思就是程式跑一段時間仍沒有跑完，超過時間限制，於是報錯。
除了 judge system 之外，當我們在自己的電腦跑程式時，也可能會出現程式跑了許久仍沒有跑完而電腦發燙的窘境（尤其是在做大數據分析時，程式跑了三天三夜都跑不完⋯⋯）
Judge System 出現 TLE 或是程式跑不完並不一定代表邏輯有誤，而是讀者的想法太過「直觀」（例如暴搜），使程式的效能過低。
而效能量化的方式之一為計算時間複雜度（Time Complexity）。
時間複雜度 Time complexity
Big O
一般講到計算時間複雜度時，通常會提到 Big O，Big O 為一個數學函數，可以用來評估最糟的情況下要花多少時間來跑這個code。
Big O 的定義如下：Suppose if and only if 存在正實數 M 和實數 x0，使得對於所有x > x0，均有
｜f(x)｜≤ M｜g(x)｜，我們就可以認為f(x) = O(g(x))。
參考資料：維基百科讀者如果讀到這裡還不知道時間複雜度為何不用擔心，快速計算時間複雜度的方法（i.e.懶人包）為：
Step 1.將所有步驟的數目相加Step 2.取最高次方並去掉係數即是這份程式的時間複雜度例如：通常假設資料量為 n，將所有步驟的數目相加後得到 6n² + 3n + 2，最高次方為6n²，去掉係數後為 n²，因此我們可以說該份程式的時間複雜度 O(n²)。
常見的時間複雜度
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(3^n) < O(n!)
由圖片可以看出，隨著資料量越大，不同時間複雜度的效能會相差越大。以下我們將介紹不同的時間複雜度。
Constant Run Time O(1)
執行時間不會因為資料量的大小而有所改變。
說明：
或許讀者會認為，找一個List的最中間數的執行時間會隨著資料量越大而增加，其實不然。
在這個程式中做了兩件事：第一為找到最中間數的 index，這是純粹的數學計算，因此步驟的數目為1；第二為找到 List 中對應該 index 的值，步驟的數目為1。綜合以上，共有1+1 = 2個步驟，接著把係數拿掉，因此時間複雜度為 O(1)。
Logarithmic Run Time O(logn)
雖著資料量的增加，執行時間雖然也增加，但增加率趨緩，比線性增加的還慢。
這個例子要牽涉到二元搜尋法(binary search)，筆者會於下一篇介紹二元搜尋法。
Linear Run Time O(n)
當輸入的資料越多時，執行時間會等比例增加。
說明：
假設 List 裡有 n 個元素，最糟的情況為最大值位在 List 的最後一個位置，且這個List是由小到大排序，因此必須迭代 n 次才能找到最大值。
每一次迭代中會做兩個步驟，第一個為 if 判斷式，第二個為賦值，共有 2n 個步驟。去掉係數後，該程式的時間複雜度為 O(n)。
筆者以這個方式找最大值是想要讓讀者可以清楚看到迭代的效果，當然讀者也可以使用 python 函式庫裡的 max() 來找最大值，這個函式背後程式碼的原理也是將 List 中每一個元素跑過一遍，時間複雜度為 O(n)。
在這邊筆者想要提 python 函式庫裡的 sort()，功能是將 List 遞增排序。這個方法也可以找到最大值，但是 sort() 的時間複雜度為 O(nlogn)，因此在這裡使用 sort() 無非是殺雞用牛刀。
O(n²)
隨著資料量增加，執行時間會以次方增加
以 Big O 為準則，要快速判斷時間複雜度的方法可以看程式中是否有迴圈（for、while迴圈等等）存在，若有迴圈存在且是迭代 n 次的話，我們可以說該迴圈的時間複雜度為 O(n)。
以此類推，雙層迴圈的時間複雜度便是 O(n²)。但讀者要注意並不是所有的情況下有迴圈時間複雜度就是 O(n)，依程式內容而有所不同。
Exponential Run Time O(2^n)
隨著資料量增加，執行時間會以指數倍增加。
很多例子用暴搜法的時間複雜度都會是 O(2^n)，在這裡筆者舉一個很直觀的例子：一筆資料中每個元素都必須進行二擇一，因此當有 n 筆資料時，執行時間為 2^n倍。
Factorial Run Time O(n!)
著名的例子為 Bogo Sort，這是一個非常原始的演算法，其原理為將一堆卡片丟在空中，落下時看卡片有沒有被排序好，如果沒有就再丟一次，其時間複雜度為O(n!)，因為第一個位置放置的卡片有 n 種選擇，接著第二個有 (n-1) 種選擇，以此類推。
(現實生活中極少用到這個方法，讀者當作科普即可ＸＤ）
小結：
通常在初學程式時，難免會很直觀的利用暴搜法來解決問題，然而當暴搜法捕管用時，不妨先算一下自己所寫的程式之時間複雜度，並想盡辦法優化。過程或許不輕鬆，但筆者認為對於邏輯思考很有幫助。
共勉之，程式之路上有你有我：）
