4

私はアルゴリズムの問​​題に取り組んでおり、高速化で壁にぶつかっています。

私は関数を持っていますf(i,j)。ここで、iおよびjは整数であり1 <= i <= j <= n、上限がありnます。この関数は既に作成されています。

さらに、この関数は等式 を満たしf(i, j) + f(j, k) = f(i, k)ます。

f(x, y)多くの異なるペアを計算する必要がありx, yます。考えられるすべてのペアnを格納するには十分な大きさであると仮定します。f(x,y)x,y

このタイプの質問に対する既知のアルゴリズムはありますか? 私が現在使用しているものは、上記の等式を使用してメモ化し、以前に計算された数値のペアにf還元しようとしますが、スマートな方法で還元していないため、時間がかかっていると思います。x,y

編集：素朴な方法で計算されたときにf(i, j)比例して時間がかかると仮定します。j-i

4

3 に答える 3

6

2 のべき乗サイズの暗黙的なツリーを使用できます。

  • ごとf(i,i+1)に保存i
  • 偶数f(i,i+2)ごとに保存i
  • 4 で割り切れる数f(i,i+4)ごとにストアi
  • ...

O(log n)テーブル (正確には )がfloor(log_2(n))あり、合計サイズはO(n)(~ 2*n) です。

f(i,j)whereを取得するにはi<=j:

  • iが異なる最上位ビットを見つけjます。
  • このビットnが設定され、すべての下位ビットがクリアされた値とします。これにより、次の手順が常に成功することが保証されます。
  • f(i, n)右からできるだけ大きな塊を繰り返し切り取って見つける
  • f(n, j)左からできるだけ大きな塊を繰り返し切り取って見つける

取得は各テーブルに最大 2 回アクセスするため、 で実行されO(log n)ます。

于 2013-04-08T08:43:34.793 に答える
2

関数はルールを満たします

f(i, j) + f(j, k) = f(i, k)

あなたが言うように 。

したがって、関数を f(i,j) =g(j)-g(i) のようなものに変更します。ここで、g(i)= f(1,x)

ように

f(i,k)=g(k)-g(i)
      =g(k)-g(j)+g(j)-g(i)
      =f(j,k) + f(i,j)

したがって、f(i,j) のすべての組み合わせを保存しようとすると、約 o(n^2) スペースがかかるため、i のすべての値に対して g(i) の値を保存する方がよいと思います。 o(n) スペース

したがって、 f(i,j) を見つける必要があるときはいつでも、実際には g(j)-g(i) として見つけることができます。

として

  f(i,j)= g(j)-g(i) // as we already calculated and stored the g(i) .
于 2013-04-08T08:53:55.470 に答える
0

O(n)これは、スペース、O(n^2)セットアップ時間、O(1)評価ごとの時間を必要とするソリューションです。

私たちはそれを持ってf(i, j) = -f(j, i)いi <= jます。

が与えられますf(i, k) = f(i, j) + f(j, k)。したがって、f(i, k) = f(i, j) + f(j, k) = -f(j, i) + f(j, k). セットアップ段階で、j = 1任意に修正します。f(1, i)次に、すべてを計算しi、結果を保存します。これにはO(n)スペースとO(n^2)時間がかかります:nの実行時間での評価1, 2, 3, ..., n。

クエリの場合、とf(i, k)の 2 つの一定時間のルックアップが必要です。f(i, 1)f(k, 1)

于 2013-04-08T09:00:42.053 に答える