1

P = [a1, a2, ... , aN]最初のN自然数の順列は反転 I = [i1, i2, ... , iN]のリストで表すことができます。ここで、順列で以前に見つかったiKよりも大きい数がいくつあるかがわかります。KKP

例: の場合P = [3, 1, 4, 2]、I = [1, 2, 0, 0](3 は 1 に配置され、3 と 4 は 2 の前に配置されますが、3 と 4 の前にはそれ以上の数字はありません)。

順列を標準形式から反転形式に変換して実行する明らかなアルゴリズムがありますO(N^2)(定義に従ってカウントするだけです)。同じことが逆変換にも当てはまります (これはやや単純ではありません)。

時間の複雑度が低いアルゴリズムはありますか?

4

2 に答える 2

1

これを解決するための単純な反復動的プログラミング アルゴリズムがあります。1 からn(順列の長さ) までのすべての i について、その数を取り、 の左側にあるi要素の数を調べます。昇順で処理するため、表示されない要素はより大きな要素であることがわかります。したがって、それらの要素の数を数えて書き留めます。秘訣は、どの要素がすでに見られているかを追跡するよりも、外部リストを導入することです。PiiiP

まず、方法でそれを行う方法を見てみましょうO(n^2)。たとえば、 の場合P=[4, 3, 2, 1]、アルゴリズムは次のように実行されます。

  1. treeゼロに初期化された構造体を作成します。jj番目の位置にある要素がP反復アルゴリズムによってすでに見られている場合、位置に「1」を保持します。

  2. 1 を取り、 を決定しpos==3ます。に「1」と書きtree[pos]ます。どちらが 0 に等しいかを計算します。 にnum_seen=sum(tree[0:3])書き留めます。この後：pos - num_seen + 1I[0]tree = [0, 0, 0, 1], I = [3, 0, 0, 0]

  3. 2 を取り、ツリー [1] に「1」を書き、I[1] に 1 を書きます。tree = [0, 1, 0, 1], I=[3,1,0,0].

  4. 3 を取り、ツリー [2] に「1」を書き込み、I[2] に 0 を書き込みます。tree = [0, 1, 1, 1], I=[3,1,0,0].

  5. 4 を取り、ツリー [0] に「1」を書き込み、I[3] に 0 を書き込みます。tree = [1, 1, 1, 1], I=[3,1,0,0].

O(n log n)2 番目のトリックは、効率的なデータ構造を使用して、上記の代わりに時間内に表示された要素の数をカウントすることO(n^2)です。

以下は、フェンウィック ツリーを使用して表示された要素の数を高速にカウントする Python コードです。

def ft_sum(tree, a, b):
  if a == 0:
      s = 0;
      while  b >= 0:
          s += tree[b];
          b = (b & (b + 1)) - 1
      return s
  return ft_sum(tree, 0, b) - ft_sum(tree, 0, a - 1)

def ft_adjust(tree, k, v):
    while k < len(tree):
        tree[k] += v
        k |= k + 1

def calcI(P):
    n = len(P)
    tree = [0] * n
    I = [0] * n
    positions = [0] * n
    for i in xrange(n):
        positions[P[i]-1] = i
    tree = [0] * n
    for i in xrange(n):
        pos = positions[i]
        ft_adjust(tree, pos, 1)
        num_seen = ft_sum(tree, 0, pos)
        I[i] = pos - num_seen + 1
    return I
于 2016-01-06T11:35:30.247 に答える