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

TIme complexity of two reversed sorted arrays

提问人：amateur0724 提问时间：5/17/2022 最后编辑：Ted Lyngmoamateur0724 更新时间：5/18/2022 访问量：109

问：

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

是 O（n） 还是 O（log n）？

数组 算法 排序 时间复杂度 语言不可知

评论

1赞 Federico klez Culloca 5/17/2022
取决于算法。
0赞 amateur0724 5/17/2022
@TedLyngmo很抱歉，我是这里的新手，也是这类东西的新手，所以我认为 Java 也很合适，因为它围绕着我们的主题展开。我不小心删除了与语言无关的标签
0赞 Ted Lyngmo 5/17/2022
@amateur0724 不用担心！我认为这个问题现在看起来不错了，我又添加了两个标签，希望能吸引更多人关注这个问题。
0赞 Ted Lyngmo 5/18/2022
顺便说一句，我查了一下@维基百科：“在对 n 个对象进行排序时，合并排序的平均和最坏情况性能为 O（n log n）”，所以这两种选择似乎都不正确。

答：

0赞 DimitrijeCiric 5/18/2022 #1

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

但是，如果数组未排序，则有 2 个选项：

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

上一个：检查多维数组是否包含另一个数组的算法？

下一个：在大小为 n-k 的数组中查找 k 个缺失的元素 [duplicate]