地特四等申論題
111年
[統計] 資料處理概要
第 一 題
📖 題組：
一、設 M 與 N 分別含有 m 及 n 個元素之兩個數列陣列。 (一)試設計一演算法 Sort（M, N, P, m, n），將 M 與 N 內之元素，合併成一個新陣列 P。合併後 P 內之元素需依小而大排序；該演算法的執行時間需最佳。（15 分） (二)試計算所設計出之演算法 Sort（M, N, P, m, n）的執行時間複雜度。（10 分）
一、設 M 與 N 分別含有 m 及 n 個元素之兩個數列陣列。 (一)試設計一演算法 Sort（M, N, P, m, n），將 M 與 N 內之元素，合併成一個新陣列 P。合併後 P 內之元素需依小而大排序；該演算法的執行時間需最佳。（15 分） (二)試計算所設計出之演算法 Sort（M, N, P, m, n）的執行時間複雜度。（10 分）
📝 此題為申論題，共 2 小題
小題 (一)
試設計一演算法 Sort（M, N, P, m, n），將 M 與 N 內之元素，合併成一個新陣列 P。合併後 P 內之元素需依小而大排序；該演算法的執行時間需最佳。（15 分）
思路引導 VIP
看到此題應先釐清原陣列 M 與 N 的初始狀態。若題目未言明「已排序」，則必須考慮一般未排序的情況，最佳策略是將兩者複製後，使用最差時間複雜度最佳的演算法（如合併排序 Merge Sort）；同時，為了展現邏輯嚴密性與拿取高分，應當補充「若原陣列已排序」的雙指標合併作法（O(m+n)）。
小題 (二)
試計算所設計出之演算法 Sort（M, N, P, m, n）的執行時間複雜度。（10 分）
思路引導 VIP
看到計算時間複雜度，應先確認前一小題所設計的演算法核心邏輯（是否假設原陣列已排序）。作答時需點出基本操作（比較與搬移）的執行次數，並運用 Big-O 漸近符號嚴謹地推導出結論，建議涵蓋「已排序」與「未排序」兩種情境以確保答案無懈可擊。