最好情況時間複雜度

習題預習

1. 在已排序的列表中查找一個元素，時間複雜度為O(log n)，其中n是列表的長度。
2. 在一個數組中找到最小值或最大值，時間複雜度為O(n)，其中n是數組的長度。
3. 在一個已排序的數組中合併兩個數組，時間複雜度為O(n)，其中n是數組的長度。
4. 在一個有向無環圖(DAG)中求所有節點的最短路徑，時間複雜度為O(V+E)，其中V是節點數，E是邊數。
5. 在一個二叉搜索樹上完成插入、查找和刪除操作，時間複雜度均為O(log n)，其中n是樹中節點的數量。

說明知識

Best-Case Time Complexity指的是當算法面對最佳情況（即算法的輸入最符合算法所預期的狀況）時，經過該算法的運算所需的最少時間。

舉例來說，假設有一個在已排序的陣列中尋找目標值的算法，當目標值恰好在陣列的中央時，此算法的Best-Case Time Complexity為O(1)，因為只需在中央位置進行一次比較即可找到目標值。

再舉一個例子，假如有一個在大小為n的陣列中尋找最小值的算法。當最小值恰好在陣列的第一個位置時，此算法的Best-Case Time Complexity為O(1)，因為只需要一次比較即可找到最小值。而當最小值位於中間位置或者最後一個位置時，此算法的Best-Case Time Complexity為O(n)，因為需要逐一比較每一個元素。

彙總重點

1. 最好時間複雜度是指在最理想的情況下，算法執行所需的最少時間。

2. 最好時間複雜度通常是對排序或搜索算法進行分析時使用的概念。

3. 在最好的情況下，算法可以獲得最優化的結果，例如當數據集已經排序時，排序算法的最好時間複雜度是O(n)。

4. 最好時間複雜度不一定代表算法的效率，因為在大多數情況下，最好的情況不常見。

5. 知道算法的最好時間複雜度對於通過優化算法以提高效率具有重要意義。

知識測驗

1. 求一個n x n矩陣的轉置矩陣
   Best-Case Time Complexity：O(n^2)
   答案：將矩陣遍歷一遍，將第i列與第j行的元素交換位置，其中i < j。

2. 給定一個有序數組和一個目標值，查找目標值的索引。如果目標值不存在，返回-1。
   Best-Case Time Complexity：O(1)
   答案：當目標值在數組的中央位置時，查找的時間最短，此時的時間複雜度是O(1)。

3. 給定一個包含n個數的數組，找到所有的3個數的組合，使得它們的總和為0。
   Best-Case Time Complexity：O(n^2)
   答案：採用雙指針法，將數組排序，遍歷每個數字，設一個左指針和一個右指針，分別指向該數字的下一個和數組的最後一個元素，判斷三個數之和是否為0，如果小於0，左指針就往右移，如果大於0，右指針就往左移。

4. 給定一個字符串，找到最長的不包含重複字符的子串。
   Best-Case Time Complexity：O(n)
   答案：採用滑動窗口法，記錄每個字符出現的位置，當遇到重複字符時，將窗口左端點移到該字符上一次出現的位置的下一個位置。

5. 給定一個具有n個節點的二叉搜索樹，找到其中第k小的元素。
   Best-Case Time Complexity：O(h + k)，h為樹的高度
   答案：使用中序遍歷，在遍歷的過程中，計數器不斷累加，當計數器的值等於k時，返回當前節點的值。因為二叉搜索樹的中序遍歷結果是一個有序的數組，所以在最好情況下，只需要遍歷到第k個節點就可以結束遍歷。