爱华网
学号：09211524 班级：网工 14班 姓名：李小明
构造最优二叉查找树的时间复杂度
二叉查找树（BST，Binary Search Tree），又名二叉搜索树或二叉检索树，是一颗满足如下条件的树：
1、每个节点包含一个键值
2、每个节点有最多两个孩子
3、对于任意两个节点x和y，它们满足下述搜索性质:
a、如果y在x的左子树里，则key[y] <= key[x]
b、如果y在x的右子树里，则key[y] >= key[x]
c、它的左右子树也分别为二叉排序树
最优二叉查找树（Optimal BST，Optimal Binary Search Tree）
最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是：给定键
值序列 K = <k1, k2, . . . , kn>，k1 < k2 <· · · < kn，其中键值ki,被查找的概率为pi，要求以这
些键值构建一颗二叉查找树T，使得查找的期望代价最低（查找代价为检查的节点数）。
下面是对于查找期望代价的解释：
对于键值ki, 如果其在构造的二叉查找树里的深度（离开树根的分支数）为depthT(ki)，则搜索该键值的代价= depthT(ki) +1（需要加上深度为0的树根节点）。由于每个键值被
查找的概率分别为pi，i=1,2,3…,n。所以查找期望代价为：
E[T的查找代价] = ∑i=1~n(depthT(ki) +1) · pi
时间复杂度
1、分治法
实际上左右子树是互不影响的，不需要穷举所有左右子树的组合，所以不需要用乘法原 理，加法原理就可以了，这样式子变为：
T(n) = T(0) + T(n-1) + T(1) + T(n-2) + T(2) + T(n-3) + ...... + T(n-2) + T(1) + T(n-1) + T(0)
= 2(T(0) + T(1) + T(2) + ...... + T(n-1))
= 3T(n-1)
所以得到T(n) = O(3n)，是指数级的一个算法
2、动态规划
上面得到指数级算法的原因在于，计算了很多重复的子树情况，一些子树的查找代价被计算了很多遍；而一棵树如果是最优二叉搜索树，那么要么它是空树，要么它的左、右子树也是最优二叉搜索树，因此只需要将子树的查找代价记录下来，采用记忆化搜索或者是自底向上的动态规划的方法，虽然需要消耗一定的空间，但可以把时间复杂度从指数级降到多项式级，这些空间消耗也是可以接受的。
以下是采用自底向上的解法：
输入：键值序列 K = <k1, k2, . . . , kn>，概率序列 P = <p1, p2, . . . , pn>
输出：两个二维数组，Price[i][j]表示ki到kj构成的最优子树的查找代价，Root[i][j]表示表示ki到kj构成的最优子树的根节点位置（用于重构最优二叉查找树）
算法1：
For 子树大小size = 1 to n
For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1，长度为size
For 该子树的所有节点作为根节点root = start to end
对于每个root，根据之前计算过的Price数组得到左右最优子树的代价，可直接得到该子树的代价price为：
左右子树的最优子树代价之和 + 所有节点的访问概率之和（因为所有节点都下降了一层）
在内层循环中找到代价最小的price和root分别记录在Price[start][end]和
Root[start][end]中
下面分析这个算法的时间复杂度：
由于除了计算出我们最后需要得到的Price和Root二维数组，还产生了部分冗余的子树，因此不能简单的将算法归结为O(n)的算法。
对于子树大小为1时，我们考察了n个子树；
对于子树大小为2时，一共产生了(n - 1)个最优子树，但是在我们的每次考察中，都将子树的所有节点作为根节点考虑过一次，因此每得到1个大小为2的子树，我们需要考察2个不同的子树来找到一个代价最小的，因此最后我们实际上考察了2(n - 1)个子树； 对于子树大小为3时，类似的，我们考察了3(n - 2)个子树；
……
对于子树大小为n时，我们考察了n个子树。
最后，我们一共考察了T(n) = n + 2(n - 1) + 3(n - 2) + ...... + n个子树。
求解这个公式依然可以借用之前的方法，定义函数 f(x) = 1 + 2x + 3x + ...... = (1 - x) 这样一来 f(x)2 = T(1) + T(2) · x + T(3) · x2 + ......
再借用泰勒展开得到 T(n) = (n + 2)(n + 1)n/6 = O(n3)
或者把所有项视为n2，则有 T(n) ≤ n2 + n2 + n2 + n2 + ...... = (n+1)n2 ≤ 2n3
把中间n/2项都视为n/4 · 3n/4的话，则有 T(n) ≥ n/2 · n/4 · 3n/4 = (3/32)n3
根据时间复杂度的定义有 T(n) = O(n3)
2-22
下面介绍一个定理，可以借此把动态规划算法的时间复杂度进一步降到O(n2)，详细的证明参见参考文献：
定理1：Root[i][j-1] ≤ Root[i][j] ≤ Root[i+1][j] （Root数组定义见算法1）
也就是说，算法1的第3个For就可以不用循环子树中的所有节点了，只要循环另两个子树的根节点之间的范围就可以了。算法如下，红色的为修改的部分：
算法2：
For 子树大小size = 1 to n
For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1，长度为size
For 该子树的所有节点作为根节点root = Root[start][end-1] to Root[start+1][end]
对于每个root，根据之前计算过的Price数组得到左右最优子树的代价，可直接得到该子树的代价price为：
左右子树的最优子树代价之和 + 所有节点的访问概率之和（因为所有节点都下降了一层）
在内层循环中找到代价最小的price和root分别记录在Price[start][end]和
Root[start][end]中
在分析该算法的时间复杂度时应注意，考察的子树是与考察的内层循环中root数量一一对应的，而当start递进时，前一个root的终点正好等于后一个root的起点（算法中的红色部分），也就是说对于固定的size来说，考察的root的范围加起来应当首位相接而且至多刚好覆盖所有节点，因此对于每个size，最多只考察2n个root（这里缩放了一下），因此总共最多考察了2n · n = 2n2个子树；另一方面，Root数组中每一个值对应得到的一个最优二叉查找树，也即至少需要考察n2个子树。因此根据定义得到 T(n) = O(n2)
最优二叉搜索树的动态规划算法代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
typedef struct matrix
{
int row;
int col;
} matrix;
typedef struct minCost
{
int cost;
int mid;
} minCost;
minCost** func(matrix* mt, ssize_t count)
{
int i, j, step, min, temp, mid;
minCost **rows;
rows = (minCost **)malloc(count*(sizeof(minCost*)));
for(i=0;i<count;i++)
rows[i] = (minCost *)malloc((count-i)*sizeof(minCost));
for(i=0;i<count;i++)
{
rows[i][0].cost=0;
rows[i][0].mid=-1;
}
for(step=1;step<count;step++)
for(j=0;j<count-step;j++)
{
min=mt[j].row*mt[j].col*mt[j+step].col
+rows[j][0].cost+rows[j+1][step-1].cost;
mid=j;
for(i=1;i<step;i++)
{
temp=rows[j][i].cost+rows[j+i+1][step-i-1].cost
+mt[j].row*mt[j+i].col*mt[j+step].col;
if(min>temp)
{
min=temp;
mid=j+i;
}
}
rows[j][step].cost=min;
rows[j][step].mid=mid;
}
printf("%d, %dn", rows[0][count-1].cost, rows[0][count-1].mid); return rows;
}
void rel(minCost **mc, ssize_t count)
{
int i;
for(i=0;i<count;i++)
free(mc[i]);
free(mc);
}
int main(int argc, char *argv[])
{
minCost **temp;
matrix ma[]={{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}}; temp=func(ma, sizeof(ma)/sizeof(ma[0]));
rel(temp, sizeof(ma)/sizeof(ma[0]));
return 0;
}
百度搜索“爱华网”,专业资料,生活学习,尽在爱华网
