algorithm - 动态规划：为什么 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]

这个链接已经证明了这一点：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]to的距离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)，这是一个常数

通过简化伸缩式总和。

Answer 2

您可以通过谷歌搜索找到确切的运行时间分析，或者只是开始编写自己的循环分析。但请注意，在所有这些中，总和是通过伸缩总和计算的，我的意思是其中一个可能很大，但在第一个循环的每次迭代中需要 O(n)，并且完全需要 O(n ² )。