修改后的 MergeSort 的复杂性

Question

我想在使用合并排序对数组进行排序时计算倒置。为此，我在条件语句中添加了一个变量，以便在遇到反转时该变量会递增。伪代码：

mergesort(M, l, r) begin
  if (l < r) then
    int m <- (l + r - 1)/2; //for rounding down I use explicitly int
    inv <- 0; //set number of inversions
    mergesort(M, l, m)
    mergesort(M, m+1, r)
    i <- l;
    j <- m + 1;
    k <- l;
    while(i <= m and j <= r) do
      if (M[i] <= M[j]) then
        M'[k] <- M[i];
        i <- i + 1;
      else 
        M'[k] <- M[j];
        j <- j + 1;
        inv <- inv + 1;  //Counting inversions
      k <- k + 1;
    for (h = i, .. , m) do
      M[k + (h - 1)] <- M[h]; 
    for (h = l, .. , k -1) do
      M[h] <- M'[h];
end.

但是我不确定复杂度是否保持不变：O(n log n)。

仅增加一个变量是否会导致更差的 WC 复杂度？据我所知，它仅取决于最大的加数（n 因子）。并且添加一个常数或最坏情况下 (n - 1) + (n - 2) = 2n - 3 增量会大大改变复杂性吗？如果是，你有什么建议？

Answer 1

如果你看这两行

    j <- j + 1;
    inv <- inv + 1;  //Counting inversions

它们都是T(1)算术运算，它们的深度相同，因此T(1)+T(1) = T(1)。 inv <- inv + 1; 的额外行不能改变复杂性，因为执行时间保持不变。

修改后的 MergeSort 的复杂性

Complexity of modified MergeSort

algorithm

big-o

complexity-theory

mergesort

inversion