最优二叉搜索树是一种算法

算法设计第五次作业part2

1.纸面题：对最优二叉树和矩阵连乘两种算法验证四边形法则，如果符合四边形法则则举几个正例，如果不符合则举几个反例

四边形法则

四边形法则是动态规划算法中用于优化计算复杂度的重要性质，其数学表达形式如下：

i < i^`\ \ \ j < j^` \\ w(i,j) + w(i^`,j^`) \le w(i^`,j) + w(i,j^`)

这一不等式揭示了权重函数在特定区间组合下的单调性特征，若满足该条件，通常意味着最优分割点具有单调性，从而可以利用Knuth优化将时间复杂度从 O(n^3) 降低至 O(n^2)。

最优二叉树

符合四边形法则，举正例

经过理论推导与实例验证，最优二叉搜索树（Optimal Binary Search Tree, OBST）的期望代价函数严格符合四边形法则。为了直观展示这一性质，我们构建了一个具体的数值案例进行验证。

对于如下输入数据：

节点概率表

节点	p1	p2	p3	p4	p5
概率	0.15	0.10	0.05	0.10	0.20

伪节点概率表

|节点|(-无穷, p1)|(p1,p2)|(p2,p3)|(p3,p4)|(p4,p5)|(p5, 无穷)|