构造最优二叉查找时间复杂度 动态规划

学号：09211524班级：网工 14 班姓名：李小明构造最优二叉查找时间复杂度二叉查找识娌檎沂ST，Binary Search Tree），又名二叉搜随检爽是一颗满足如 ， ） 下棠?、每搞包含一傅 2、每搞有最多两赣 3、对于任意两搞 x 和 y，它们满足下适: a、如果 y 在 x 的赚詙[y] <= key[x] b、如果 y 在 x 的右子尸詙[y] >= key[x] c、它的子手炳叉排凶钣哦娌檎沂最优二叉查找蕄timal BST，Optimal Binary Search Tree） ， ） 最优二叉查找使查找搞平均损失最低的二叉查找蔬体来说就是：给定键 值蠯 = <k1, k2, . . . , kn>，k1 < k2 <· · · < kn二叉排序树时间复杂度，其中索引 ki,被查找的概率为 pi，要氢 些键值构建一颗二叉查找尸使得查找的希望代价最低（查找代价为检测的节点数）。 下面是针对查找期望代价的解释： 对于键值 ki, 如果其在构造的二叉查找誓深度 （离开誓分支数） depthT(ki)， 为 渣值的代价= depthT(ki) +1（需要加上深度为 0 的授点）。

由于每傅被 查找的概率分眕i，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、动态规划 、 上面得到指数级算法的原亿， 计算了这些重复的子室恍┳邮檎掖郾 计算了这些遍；而一棵墅是最优二叉搜爽那么要么它是空湿么它的滓子适亲钣哦嫠阉 一必须将子书找代价记录下来， 采用记忆化搜诉是自底 夏动态规划的方式， 虽然必须消耗必定的空间， 但可以把时间复杂度从指数级降至多项 式级，这些空间消耗也是可以接受的。 以下是运用自底夏解法： 输入：键值蠯 = <k1, k2, . . . , kn>，概率蠵 = <p1, p2, . . . , pn>输辰脯数组，Price[i][j]表示 ki 到 kj 构成的最优子书找代价，Root[i][j]表示 表示 ki 到 kj 构成的最优子戍节点位置（用于构建最优二叉查找仕惴 1： For 子省 size = 1 to n For 子蕇tart = 1 to (n - size + 1) //这样子收点即为 end = start + size - 1，长 度为 size For 该子戍有节点座节点 root = start to end 对于每竜t，根据之前计算过的 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 + 3x2 + ...... = (1 - x)-2 这样一来 f(x)2 = T(1) + T(2) · x + T(3) · x2 + ...... 再借用泰勒展开得到 T(n) = (n + 2)(n + 1)n/6 = O(n3) 谎所有项视为 n2，訲(n) ≤ n2 + n2 + n2 + n2 + ...... = (n+1)n2 ≤ 2n3 把中间 n/2 项都视为 n/4 · 3n/4 的话，訲(n) ≥ n/2 · n/4 · 3n/4 = (3/32)n3 根据时间复杂度的定义有 T(n) = O(n3)下面介绍一疙， 可以以此把动态规划算法的时间复杂度进一步降至 O(n2)， 详细的证 名参考文献： 定理 1：Root[i][j-1] ≤ Root[i][j] ≤ Root[i+1][j] （Root 数组定义见算法 1） 也就是说，算法 1 的第 3 竢 就可以不用循环子誓所有节点了，只要循环另两甘诘阒涞姆段Ь涂梢粤恕Ｋ惴ㄈ缦拢焐奈薷牡牟糠郑算法 2： For 子省 size = 1 to n For 子蕇tart = 1 to (n - size + 1) //这样子收点即为 end = start + size - 1，长 度为 size For 该子戍有节点座节点 root = Root[start][end-1] to Root[start+1][end] 对于每竜t，根据之前计算过的 Price 数组得到更优子竖价，可直接得 到该子竖价 price 为： 子暑优子售之跟 + 所有节点的访问概率之跟（淫有节点都下 降了一层） 在表层循环中找到代价最小的 price 和 root 分奔在 Price[start][end]和 Root[start][end]中 在分毋法的时间复杂度时要切记，考察的子孰考察的内层循环中 root 数量一一 对应的，而当 start 递进时，前一竜t 的终点正好等于簅t 的屁算法中的蓝色 部分），也就是说对于固定的 size 来说，考察的 root 的范围加痞当首位相接而且至多 刚好覆盖所有节点，以于每竮e，最多只考察 2n 竜t（这里怂一下）二叉排序树时间复杂度，易芄沧疃嗫疾炝 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, %d\n", 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; }

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-137285-1.html