意義與機制
排序是按照給定順序重新排列資料的過程。氣泡排序比較相鄰資料，歸併排序則將拆分後的列表合併。
演算法的迴圈結構決定輸入規模增大時工作量如何增長。即使資料規模相同，初始順序與實現中的停止條件也可能影響結果。
關係與條件
對於典型的氣泡排序，比較規模為 O(n²)，而歸併排序的規模為 O(n log n)。需要注意的是，具體的比較次數和漸近表示法 O 並不相同。
該實驗並非一個基於統計價值比較、交換和寫入次數來衡量計算機實際時間的基準。它不會將資料寫入和位置交換視為相同的操作。
觀察實驗中需要注意的事物
比較的計數取決於大小、初始順序以及演算法。
我們計算值比較和交換，而不是經過的時間。合併寫入是獨立的。
關鍵關係與符號
bubble: n(n−1)/2 · merge: O(n log₂n)
| 符號 | 含義 | 單位 |
|---|---|---|
| n | 輸入資料項的數量 | 個 |
| O(n log n) | 根據輸入規模的，漸近增長的上界表示式。 | 複雜度 |
透過範例確認
合併寫操作和交換操作是否是相同的操作？
不同的運算·比較取決於大小、初始順序以及演算法。
常見誤解
- 比較次數較少，並不意味著在所有計算機和輸入下，實際執行時間都會按同樣的比例縮短。