algorithm - 动态规划 : Why Knuth's improvement to Optimal Binary Search Tree O(n^2)?

Question

这是《算法导论》第 3 版的练习 15.5-4，是关于 Knuth 对最优二叉搜索树的 DP 方法的改进。

最优二叉搜索树的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³)。 Knuth 观察到 root[i, j - 1] <= root[i, j] <= root[i + 1, j] , 所以练习 15.5-4 要求通过对原始算法做一些修改来实现 O(n²) 算法。

好吧，经过一番努力，我想通了:在最里面的循环中，替换行

for r = i to j

与

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

此链接已证明这一点:Optimal binary search trees

但是，我不确定这是否真的是 O(n²):因为在每个最内层循环中，从 r[i, j - 1] 到 r[i + 1, j] 的距离] 不是常量，我怀疑它仍然是 O(n³)。

所以我的问题是:你能解释一下为什么对 DP 算法的改进会产生 O(n²) 的复杂度吗？

PS:也许我可能先阅读了 Knuth 的论文，但实际上我在网上搜索但没有发现可以免费访问该论文。

Answer 1

你是对的，从 r[i, j - 1] 到 r[i + 1, j] 的距离在最坏的情况下不是常数，但平均而言它是恒定的，这足以暗示二次运行时间。 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)，这是一个常数

通过简化伸缩和。