两个反向排序数组的时间复杂度

Question

将两个反向数组合并成一个有序数组的时间复杂度是多少？

是 O(n) 还是 O(log n)？

Answer 1

如果给定的两个数组都按相反的顺序排列，它将是 O(m + n)(m - length of 1. array, n - length of 2. array)，因为您需要线性迭代两个数组。

但是如果数组没有排序，你有两个选择：

1. 对它们进行排序，排序后合并它们O(nlogn + mlogm)。
2. 连接数组并对连接后的数组进行排序 O(nlogn + mlogm)。