實測不同時間複雜度的執行時間
延續上一篇介紹時間複雜度：程式寫好跑不完？Time Limit Exceeded怎麼辦？之後，這篇將實測不同時間複雜度的執行時間。
在進入實測前，筆者將先介紹二元樹（Binary Tree）及二元搜尋法（Binary Search），因為在後面會實際利用這個演算法。
二元樹（Binary Tree）
將陣列中的整數一一加入二元樹中。
Step 1. 若這個二元樹是空的，加入一個節點，並形成一個只含一個節點的二元樹。
Step 2. 將新加入的數字以以下規則推入二元樹的末端：若接下來加入的數字的值比節點還小，則加入左邊的樹，若接下來加入的數字的值比節點還大，則加入右邊的樹。
Step 3. 重複 Step 2.，最後形成二元樹。例子如下圖，而筆者也將詳細解釋這個二元樹生成的步驟。
給定一個陣列 [10, 19, 5, 1, 6, 21, 17]
Step 1. 一開始這個二元樹是空的，因此加入一個節點，該節點的值為 10。
Step 2. 因為 19 > 10，因此將 19 放入 10 右邊的樹。
Step 3. 5 < 10，將 5 放入 10 左邊的樹。
Step 4. 重複上述 Step 2.及 Step 3.，最後形成二元樹。
當一個二元樹建構完成後，將每個節點投影在一平面上會發現這些數字會由小到大排序。也就是說，透過二元樹可以將一個陣列變成一個以遞增排序好的陣列。
因此上述的例子 [ 10, 19, 5, 1, 6, 21, 17 ] 就會形成 [ 1, 5, 6, 10, 17, 19, 21 ]。
二元搜索法（Binary Search）
二元搜索法便是利用二元樹的概念，在有序陣列中搜尋某一特定元素的搜尋演算法。
搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束，這是最佳的狀況，所需的步驟數目為 1。
如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，再來跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
舉例來說，當資料的數量為 4，最糟的情況必須切半 2 次，
也就是說所需步驟數目為 2（2^2 = 4）；
因此假設當資料為 n 時，最糟的情況所需步驟數目為 x 次，
2^x = n，
所以 x = logn（以2為基底的對數）。從上面的推導得出，利用二元搜尋法在一個一維陣列找值的話，所需的時間複雜度為 O(logn) 。（這邊的對數都是以 2 為基底）
若讀者仍然不太明白二元搜尋法如何運作，下面將用圖示法再次解釋二元搜索法的原理。
這是一個已排序的數列，資料數量為 13 ，假設我們要找的數字為 41 。
用直觀的方法為從頭（第 0 個）開始找，找到第10個時即為我們要的答案，如下圖所示。
利用二元搜尋法，首先先找到最中間的數字：20，因為41 > 20，因此接下來我們搜尋範圍 24 到 50 的數列；這個區間的最中間數為 36，41 > 36，因此我們搜尋範圍 36 到 59 的數列；這個範圍的最中間的數為 41，41 = 41，我們找到了欲尋找的數字，搜尋結束。
簡易圖如下。
簡單介紹完二元樹及二元搜索法之後，筆者將進入本篇文章的重點——實測不同的時間複雜度。
O(n) v.s. O(logn)
Q : 給定一個已排序好、無重複的一維陣列，找特定值的位置（index）。
解法一：暴搜法，時間複雜度 = O(n)。
說明1：
用直觀的方法在一維陣列中把每個值都跑一遍找我們要的值。
因為我們要找的值是一維陣列中的最後一個元素，
需要把陣列的每個元素從頭跑到最後才會找到我們要的答案，
這是最壞的情況，時間複雜度為O(n)。解法二：二元搜尋法，時間複雜度 = O(logn)。
說明2：
利用二元搜尋法來找值，將我們要找的值跟中位數比較，
不段重複此步驟以減少搜尋的範圍，直到找到答案。
因為我們要找的值為一維陣列中的最後一個元素，因此所需的步驟數目 x = log(10000)
（ 2^x = 10000 ）
當資料數量為 n 時，時間複雜度為 O(logn)。在上面兩個程式碼中，我們利用 python 的 time.time() 來計算程式的執行時間。計算程式執行時間方法如下：令 t0 為開始的時間，放在程式碼開始前的位置；令 t1 為結束的時間，放在程式碼結束的位置；t1 - t2即為該段程式碼的執行時間（單位：秒）。
筆者認為這是個非常實用的功能，在往後寫結構更加複雜的程式時，更需要計算程式的執行時間是否太大。
小結
由此可知，執行時間上 O(logn) 確實小於 O(n) 。雖然在這一個例子，讀者試用解法一實作時並沒有覺得時間上有多大的差異，原因是因為這個例子是一個非常簡單的例子：只有一維陣列且資料數量沒有很多。
因此下面一個例子更加複雜，希望讀者在讀完後能更加體會時間複雜度的重要性。
O(n²) v.s. O(logn + logn)
呈上個例子，但此時由一維陣列變成二維陣列。
Q：給定一個已排序、無重複的二維陣列，由左至右為遞增排序且每一列的第一個元素會大於前一列的最後一個元素。找特定值的位置（index）。
解法一：暴搜法，時間複雜度 = O(n²)。
說明3：
資料為一個 1024 X 1024 的方陣，總共的資料數量為 1024 * 1024 = 1048576。
在尚未知道二元搜尋法(binary search)時，
多數人（包含我）的解法就是暴搜：
從矩陣的第一列開始找我們要的值，如果沒有，就換下一列，以此類推直到找到值為止。
最壞的情況為欲找的值在二維陣列的最後一個，
因此每一列每個值都要跑過，時間複雜度為O(n^2)。解法二：二元搜尋法，時間複雜度 = O(logn + logn)。
說明4：
利用一樣的例子，但利用二元搜尋法來尋找答案。
從上面的程式碼可以知道，筆者利用了兩個 while 迴圈來進行搜索。
第一個 while 迴圈是利用二元搜尋法找欲找的值位於哪一列；依照說明2，這個 while 迴圈的時間複雜度為 O(logn)。
找到該列後，在該列中再次利用二元搜尋法找到最後的答案，也就是第二個 while 迴圈做的事情；此 while 迴圈的時間複雜度為 O(logn)。
綜合以上所述，這個程式碼的時間複雜度為 O(logn + logn)。小結
在這個較複雜的例子中，讀者可以發現這兩份程式碼的執行時間有更大的差距。
隨著資料量的增加，暴搜法的執行時間會以指數倍增加，幅度較大，需花更多的時間；而二元搜尋法的執行時間雖然也會隨著資料量的增加而增加，但幅度較小，所花的時間比暴搜法少。
總結
在未來寫程式之路上，利用暴搜法或一些直觀的方法容易踢到鐵板，筆者建議可以從現在開始，每次寫程式時都大略算一下時間複雜度，並且思考有沒有比現在這個更快的方法，慢慢地就可以減少自己寫出跑不動（XD）的程式。
筆者認為與朋友、同學討論是一個很好的方法，聽或看其他人是怎麼想的，增加自己邏輯的多元性。
共勉之，程式之路上有你有我：）
