高考申論題
113年
[資訊處理] 資料結構
第 二 題
📖 題組：
二、(一)快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為 O(n2)，請說明是在何種情況下造成？（10 分） (二)請列出其最壞的時間複雜度為 O(n2)的推導過程。（15 分）
二、(一)快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為 O(n2)，請說明是在何種情況下造成？（10 分） (二)請列出其最壞的時間複雜度為 O(n2)的推導過程。（15 分）
📝 此題為申論題，共 2 小題
小題 (二)
請列出其最壞的時間複雜度為 O(n2)的推導過程。（15 分）
思路引導 VIP
推導時間複雜度通常使用「遞迴關係式（Recurrence Relation）」。在最壞情況下，規模為 n 的問題被簡化為規模為 n-1 的問題加上一次 Partition 的成本。接著使用代換法或展開法將其化簡。
小題 (一)
快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為 O(n2)，請說明是在何種情況下造成？（10 分）
思路引導 VIP
回想快速排序的核心機制：Partition（分割）。理想情況是每次分割都能將序列對半分（像合併排序），而最壞情況則是「極度不平衡的分割」。思考什麼樣的資料輸入會導致 Pivot（基準值）每次都選到極端值？