2. 時間複雜度 (下篇)

關於時間複雜度本篇將討論以下幾個項目

1. 什麼是動態情況下的時間複雜度？

2. 最佳情況時間複雜度 (Best case time complexity)

3. 最壞情況時間複雜度 (Worst case time complexity)

4. 平均情況時間複雜度 (Average case time complexity)

測試環境：

OS：Windows 10
IDE：Visual Studio 2019

1. 什麼是動態情況下的時間複雜度？

經由 時間複雜度 (上篇) 介紹的幾種常用時間複雜度分析法後，相信各位應該已經能夠理解並開始試著對手邊程式進行時間複雜度分析了，接下來會用一個例子來說明動態情況下的時間複雜度

範例：

上圖中的 GetIndex 方法，可查找 val 位於 array 中的哪個位置，由於這個範例寫法並不嚴謹，所以假設傳入的 array 中數值皆不重複，這個 GetIndex 方法中只要比對到我們要的資料就會直接 return index，而 val 究竟位於 array 中的哪個位置？

1. 第一個？
2. 最後一個？
3. 中間任意位置？

查找的 val 在 array 不同位置時，會有不同的時間複雜度就稱作「動態情況下的時間複雜度」

2. 最佳情況時間複雜度 (Best case time complexity)

最佳情況就是 val 位於 array[0] 的時候，此時迴圈執行次數：1

最佳情況時間複雜度：O(1)

3. 最壞情況時間複雜度 (Worst case time complexity)

最壞情況就是 val 位於 array[n] 的時候，此時迴圈執行次數：n

最壞情況時間複雜度：O(n)

4. 平均情況時間複雜度 (Average case time complexity)

迴圈執行次數 / val 可能位置數量 = 平均情況時間複雜度

由 array[1] 到 array[n] 的迴圈執行次數依序為：

1, 2, 3, 4, … , n

array 中不包含的 val 時的迴圈執行次數為：

n

迴圈執行次數：

(1+2+3+4+…+n)+n = n(n+3) / 2

val 可能位置數量：

// 存在於 array 中 + 不存在於 array 中
n + 1

平均情況時間複雜度：

// 迴圈執行次數 / val 可能位置數量 = 平均情況時間複雜度
// 時間複雜度：O(n(n+3) / 2(n+1))
// 前篇說過「常數係數可省略」，故簡化成 n²/n = n

平均情況時間複雜度：O(n)

總結

一般情況下，前篇介紹的幾種時間複雜度分析方式已足以應付，只有在不同情況下時間複雜度有量級的差距(O(1) → O(n)) 時才需要使用 最好 / 最壞 / 平均 時間複雜度。

這兩篇所介紹的時間複雜度分析並非絕對準確，而是提供一個快速判斷出一段程式的時間複雜度的方法。

在後續演算法學習中能藉由分析時間複雜度高低，進而作為我們在不同情況下初步判斷使用得演算法是否合適的依據。

新手上路，若有錯誤還請告知，謝謝