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)。

変数を 1 つだけインクリメントすると、WC の複雑さが悪化しますか? 私が知っているように、それは最大の被加数 (n-factor) のみに依存します。また、定数を追加するか、最悪の場合 (n - 1) + (n - 2) = 2n - 3 のインクリメントを追加すると、複雑さが大きく変わりますか? はいの場合、何を提案しますか?

4

1 に答える 1

1

この2行を見ると

    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 に答える