归并排序的合并步骤的时间复杂度是多少？

Question

我知道这个算法的时间复杂度是o(nlogn)，但是如果我们只讨论合并步骤，这还是o(nlogn)吗？或者减少到o(logn)？我相信第二个是答案，但由于我们仍然必须接触数组中的每个元素，我怀疑复杂性保持不变

干杯！

Answer 1

“拆分”步骤是需要 o(logn) 的步骤，而合并步骤是 o(n)，刚刚通过评论意识到这一点。

Answer 2

归并排序的分割步骤将花费 O(n) 而不是 O(log(n))。 如果我们有分步的运行时功能：

T(n) = 2T(n/2) + O(1)

T(n) 是输入大小 n 的运行时间，2 是新问题的数量，n/2 是每个新问题的大小，O(1) 是将数组分成两半的常数时间。

我们还有基本情况：T(4) = O(1) 和 T(3) = O(1) 。

我们可能会想出（不太准确）：

T(n) = n/2 * O(1) = O(n/2) = O(n)

此外，要了解合并步骤（手指算法）的时间复杂度，我们应该了解子数组的数量。

最坏情况下子数组的数量具有渐进增长率 = O(n/2 + 1) = O(n)。

“手指算法”随着子数组数量的增长而线性增长，它将循环遍历每个子数组 O(n)，并且在最坏情况下每个子数组需要再循环 2 次 - > 合并步骤的时间复杂度（手指算法） = O(2n) = O(n).

Answer 3

T(n) =T(n/2) +T(n/2) + θ (n) 
=2T(n/2) + θ(n) 
  =2T(n/2) + c.n
  So, Time complexity of Merge procedure 
  is  θ(n) 

Answer 4

等等等等，合并函数不是 O(n + m) 吗？我以为是的。因为我们遍历了两个列表，对吗？我现在很困惑，有人可以帮助我吗？