下面程序的 Merge_Sort 函数时间复杂度为：
void Merge(int a[], int left, int mid, int right) { /* 合并两段, O(区间长) */ }
void Merge_Sort(int a[], int left, int right) {
if (left == right) return;
int mid = (left + right) / 2;
Merge_Sort(a, left, mid);
Merge_Sort(a, mid + 1, right);
Merge(a, left, mid, right);
}
- A. O(n log n)
- B. O(n²)
- C. O(2ⁿ)
- D. O(log n)
正确答案：A