0

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

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 增量会大大改变复杂性吗？如果是，你有什么建议？

4

1 回答 1

1

如果你看看这两行

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

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

于 2015-11-11T12:43:07.603 回答