动态编程:为什么Knuth对最优二叉搜索树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]

这已通过以下链接证明:最佳二叉搜索树

但是,我不确定这是否真的是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]是不是在最坏的情况下恒定的,但它是恒定的平均水平,这足以暗示二次运行时间.lis 的迭代总数

  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-1 + 1),这是一个常数

通过简化伸缩总和.