資料結構與演算法
在合併排序中，把已依升冪排序的兩個序列 1, 4, 7, 9 與 2, 3, 8, 10，以「比較兩者開頭並輸出較小者」的方式反覆進行，合併成一個序列。其中一個序列變空時，其餘部分不比較直接輸出。比較次數為幾次？
- A4次
- B7次
- C8次
查看答案與解析
正確答案：B. 7次
依序比較1與2、4與2、4與3、4與8、7與8、9與8、9與10，此時第一個序列已空，剩下的10不比較直接輸出。比較共7次，相當於合併長度 m 與 n 的序列時的最多次數 m + n − 1 = 7。合併只需把已排序的序列從開頭各看一次，為 O(m + n)，合併排序重複 log₂ n 層，因此整體為 O(n log n)。
- A. 並不是只比較其中一個序列長度的次數就夠了。值會交替輸出，因此比較次數較多。
- B. 正確。只有最後的10不比較直接輸出，比較共7次。
- C. 最後一個元素沒有比較的對象，因此不會是8次。