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