动态规划:为什么Knuth对最优二叉搜索树O(n ^ 2)有改进? [英] Dynamic Programming: Why Knuth's improvement to Optimal Binary Search Tree O(n^2)?

问题描述

这是第三版算法简介的练习15.5-4，它涉及Knuth对DP最优二叉搜索树方法的改进.

This is Exercise 15.5-4 of Introduction to Algorithms, 3rd edition, which is about Knuth's improvement to the DP approach to Optimal Binary Search Tree.

最优二叉搜索树的DP算法为:

The DP algorithm of Optimal Binary Search Tree is:

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 ² )算法.

The complexity is O(n³). Knuth had observed that root[i, j - 1] <= root[i, j] <= root[i + 1, j], so Exercise 15.5-4 asks to implement an O(n²) algorithm by doing some modification to the original algorithm.

经过一番努力，我已经弄清楚了:在最内层的循环中，替换该行

Well after some effort I have figured this out: in the innermost loop, replace the line

for r = i to j

使用

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

此链接已证明了这一点:

This has been proved by this link: Optimal binary search trees

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

However, I'm not sure this is really O(n²): since during each innermost loop, distance from r[i, j - 1] to r[i + 1, j] is not constant, I suspect it is still O(n³).

所以我的问题是:您能否向我解释为什么改进DP算法会产生O(n ² )复杂度?

So my question is: can you please explain to me why the improvement to DP algorithm yields O(n²) complexity?

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

PS: Maybe I might have read Knuth's paper first, but really I searched the web but found no free access to the paper.

推荐答案

您正确的说，在最坏的情况下，从r[i, j - 1]到r[i + 1, j]的距离不是恒定的，但平均而言是恒定的，足以满足暗示二次运行时间. l的迭代总数为

You're correct that the distance from r[i, j - 1] to r[i + 1, j] is not constant in the worst case, but it is constant on average, which suffices to imply a quadratic running time. The total number of iterations for l is

  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)，这是一个常数

therefore the average is S / (n - l + 1), which is a constant

通过简化伸缩总和.

这篇关于动态规划:为什么Knuth对最优二叉搜索树O(n ^ 2)有改进?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！