最小值、最大值統計複雜度分析

最小值、最大值統計

給到長度為N的數組a，統計數組a的最小值、最大值很常見。

找到的最小值

• 初始化最小值，然後遍歷a, 分別與最小值比較，看情況更新最小值
• O(N)

找到數組a的最大值

• 與最小值思路相同
• O(N)

同時找到最小值、最大值

• 方法I：按之前的思路，遍歷a, 分別與最小值最大值比較，看情況更新 O(2N) = O(N)
• 方法II：將a中的元素配對配對元素 (a0, a1)內部比較一次，得到min(a0, a1), max(a0, a1)min(a0, a1)與最小值比較, max(a0, a1)與最大值比較O(3N/2)=O(N), 常數因子從2優化到1.5

min, max, top2統計

找到最小值、第二最小值

• 方法I：比較2N次，分別獲取兩個值
• 方法II：O(N+logN)

和淘汰賽賽制類似：第一輪每兩個數對抗，最小者獲勝；第一輪冠軍中，每兩個數對抗，最小者獲勝；依次類推，找到最終的冠軍，即最小值 O(N)

從和冠軍比賽的log(N)只隊伍中，選出最小值，即亞軍，即第二小值淘汰賽制中，亞軍一定輸給過冠軍。反證法：如果亞軍未輸給過冠軍，假設輸給過B隊伍，則亞軍

如何找到數組的Top k？盡請期待，提示和淘汰賽類似，通過堆排序實現。