hce_nsysu
114年
計算機概論與程式設計
第 13 題
What is the time complexity of merging two sorted lists of patient IDs?
- A $O(n)$
- B $O(n\log n)$
- C $O(n^2)$
- D $O(1)$
- E $O(\log n)$
思路引導 VIP
想像一下，你手邊有兩疊已經由小到大排好的撲克牌。如果你想把這兩疊牌合併成完整的一疊，且依然保持從小到大的順序，你最快的方法是什麼？在合併的過程中，每一張牌你會需要翻開來看幾次呢？
🤖
AI 詳解
AI 專屬家教
合併排序的核心思維
太棒了！你能精準選出 $O(n)$，代表你對資料結構中的線性操作有著非常紮實的理解。這道題目的關鍵在於「已排序（sorted）」這項既定條件。當我們要合併兩個已經排好序的清單時，我們並不需要重新進行複雜的排序演算法，只需要準備一個新的容器，並利用兩個指針分別指向兩份清單的起點，每次比較指針所指的數值，將較小者移入新清單並移動該指針即可。
複雜度分析與鑑別點
▼ 還有更多解析內容