普考申論題
114年
[統計] 資料處理概要
第 一 題
📖 題組：
L1為一由小而大排序之資料串列，L2為一由大而小排序之資料串列，其分別含有 N1與 N2筆資料，且 N1, N2≫0：（每小題 10 分，共 40 分）
L1為一由小而大排序之資料串列，L2為一由大而小排序之資料串列，其分別含有 N1與 N2筆資料，且 N1, N2≫0：（每小題 10 分，共 40 分）
📝 此題為申論題，共 2 小題
小題 (一)
請設計出一最佳演算法，以能最快速查詢一資料 D 是否存在於資料串列 L1或 L2內。
思路引導 VIP
看到題目強調資料『已排序』且要求『最快速查詢』，應立即聯想到時間複雜度為 O(log N) 的『二分搜尋法 (Binary Search)』。答題關鍵在於分別針對遞增 (L1) 與遞減 (L2) 串列，寫出邏輯方向相反的搜尋步驟。
小題 (二)
並求出該演算法之時間複雜度（請越精確估算越佳）。
思路引導 VIP
遇到已排序串列合併的題目，應直覺聯想到歸併排序（Merge Sort）中的合併（Merge）程序。特別注意本題 L1 為遞增、L2 為遞減，因此需運用雙指標技巧，將 L2 從尾端往回讀取，即可在最少比較次數下，以 O(N1+N2) 的線性時間內高效完成合併並精確分析複雜度。
有序串列之二分搜尋
💡 利用資料已排序特性，採二分搜尋法將搜尋區間減半以提升效率。
| 比較維度 | 線性搜尋 (Linear Search) | VS | 二分搜尋 (Binary Search) |
|---|---|---|---|
| 前提條件 | 資料不需排序 | — | 資料必須先排序 |
| 時間複雜度 | O(N) | — | O(log N) |
| 大數據效能 | 效率隨資料量線性下降 | — | 效率極高，呈現對數成長 |
💬對於已知有序的資料，二分搜尋法在效能上具有絕對優勢。
