13

これは、Introduction to Algorithms, 3rd edition の演習 15.5-4 で、最適な二分探索木への DP アプローチに対する Knuth の改善に関するものです。

最適二分探索木の DP アルゴリズムは次のとおりです。

OPTIMAL_BST(p, q, n)
let e[1..n+1, 0..n], w[1..n+1, 0..n], and root[1..n, 1..n] be new tables
for i = 1 to n+1
    e[i, i - 1] = q[i - 1];
    w[i, i - 1] = q[i - 1];
for l = 1 to n
    for i = 1 to n - l + 1
        j = i + l - 1
        e[i, j] = INFINITY
        w[i, j] = w[i, j - 1] + p[j] + q[j]
        for r = i to j
            t = e[i, r - 1] + e[r + 1, j] + w[i, j]
            if t < e[i, j]
            e[i, j] = t
            root[i, j] = r
return e and root

複雑さは O(n 3 ) です。クヌースは を観察していたroot[i, j - 1] <= root[i, j] <= root[i + 1, j]ので、演習 15.5-4 では、元のアルゴリズムに何らかの変更を加えて O(n 2 ) アルゴリズムを実装するよう求めています。

いくつかの努力の後、私はこれを理解しました:最も内側のループで、行を置き換えます

for r = i to j

と

for r = r[i, j - 1] to r[i + 1, j]

これは、このリンクによって証明されています:最適な二分探索木

ただし、これが本当に O(n 2 ) であるかどうかはわかりません。最も内側の各ループの間、r[i, j - 1] から r[i + 1, j] までの距離は一定ではないため、まだ一定であると思われます。 O(n 3 )。

私の質問は、DP アルゴリズムの改善によって O(n 2 ) の複雑さが生じる理由を説明していただけますか?

PS: 私は最初に Knuth の論文を読んだかもしれませんが、実際に Web を検索しましたが、その論文への無料アクセスは見つかりませんでした。

4

2 に答える 2

11

r[i, j - 1]最悪の場合、 からまでの距離r[i + 1, j]は一定ではありませんが、平均的には一定であり、2 次実行時間を暗示するのに十分です。の総反復回数lは

  S = sum_{i = 1}^{n - l + 1} (r[i + 1, j] + 1 - r[i, j - 1]),  j = i + l - 1
    = sum_{i = 1}^{n - l + 1} (r[i + 1, i + l - 1] + 1 - r[i, i + l - 2])
    = r[n - l + 2, n] + n - l + 1 - r[1, l - 1]

ラテックス

したがって、平均は S / (n - l + 1) であり、これは定数です。

伸縮和を単純化することによって。

于 2013-06-07T15:42:38.013 に答える