二叉搜索树和最优二叉搜索树的时间复杂度是多少？

二进制搜索树（BST），也称为二进制搜索树或二进制搜索树，是满足以下条件的树: 1.每个节点包含一个键值2.每个节点最多有两个子节点3. 对于任何两个节点x和y，它们满足以下搜索属性: 如果y在x的左子树中，则键[y] <=键[x] b，如果y在x的右子树中，键[y]> =键[x]最佳二叉搜索树（最佳BST，最佳二进制搜索树）是最佳的二进制搜索树，它使查找每个节点的平均成本最小化. 叉找到树. 具体来说: 给定键值序列K = ，k1

因此，预期的搜索成本为: E [T的搜索成本] =Σi= 1〜n（depthT（ki）+1）·pi时间复杂度1，详尽地构造了最佳二叉搜索树，实际上，这就是问题: 一个具有n个数字的有序节点可以构造多少个不同的BST（以找到最佳的二叉搜索树）？使其构造为T（n），然后将每个元素枚举为根节点. 当第一个元素用作根节点时，其余的n-1个元素形成右子树，而没有左子树，即n-在情况1中有T（n-1）问题. 第二个元素用作根节点，左子树具有1个元素，右子树具有n-2个元素. 根据乘法原理，T（n-1）1）T（n-2）个情况...依此类推: 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）;另外，T（0）= T（1）=1. 让我们求解T（n）: 定义函数f（x）= T（0）+ T（1）·x + T（2）·x2 +. ..然后有: f（x）2 =（T（0）2）+（T（0）T（1）+ T（1）T（0））x +（T（0）T（2） + T（1）T（1）+ T（2）T（0））x2 + ...... = T（1）+ T（2）x + T（3）x2 + ..... =（f（x）-T（0））＆#47; x =（f（x）-1）＆#47; x求解方程，使f（x）= [1-（1-4x）1＆#47; 2]＆#47;在右侧进行2倍泰勒展开，然后与定义进行比较以得到: T（n）=（2n）！ ＆#47; （n！（N + 1）！）然后根据斯特林公式: n！ 〜（2πn）1和#47; 2·（n＆#47; e）n然后（2n）！ ＆#47; n！ （N + 1）！ 〜（4n1＆#47; 2·2n2n）＆#47; （2n1＆#47; 2·Nn·（2（n + 1））1＆#47; 2·（n + 1）n）〜4n·（n + 1）-3＆#47; 2·（n＆#47;（n + 1））n〜4n·n-3＆#47; 2最后，我们得到了穷举方法构造最优二叉搜索树的时间复杂度: T（n）= O（4n·n-3＆#47; 2）2.递归实际上下子树不影响彼此. 不必详尽地组合所有左右子树，因此不需要乘法原理. 加法原理就足够了. 该公式变为: 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），这是一个指数算法. 3.在动态编程中使用上述指数算法的原因是它计算了许多重复的子树. 在某些情况下，某些子树的搜索成本会被多次计算. 如果树是最佳的二叉搜索树，那么它要么是一棵空树，要么它的左右子树也是最佳的二叉搜索树. 因此，仅需记录子树的搜索成本并使用存储搜索或自底向上的动态编程方法. 尽管它需要一定的空间，但可以将时间复杂度从指数级降低到多项式级. 这些空间的消耗也是可以接受的.

以下是一个自下而上的解决方案: 输入: 键值序列K = ，概率序列P = 输出: 两个二维数组，Price [i] [j]表示由ki到kj组成的最优子树的搜索成本，而Root [i] [j]表示由ki到kj组成的最优子树的根节点位置（对于重建最佳二叉搜索树）算法1: 对于子树大小，大小为1到n对于子树的开始，开始= 1到（n大小+1）＆#47; ＆#47; End =开始+ size-1二叉排序树时间复杂度，长度为size对于此子树的所有节点均用作根节点root =开始至结束对于每个根，可以根据之前计算的Price数组直接获得左右最优子树的成本，可以直接获得子树的价格为: 左子树和右子树的最佳子树成本之和+所有节点（因为所有节点均下降了一层）的访问概率之和价格中的昂贵价格和根中的根分别记录在价格[开始] [结束]和根[开始] [结束]中，该算法的时间复杂度分析如下: 要获得价格和根的二维数组还生成了部分冗余的子树，因此该算法不能简单地简化为O（n2）算法.

对于1个子树，我们检查了n个子树；对于大小为2的子树，我们总共生成了（n-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＆#47; 6 = O（n3）或将所有项都视为n2，则T（n）≤n2 + n2 + n2 + n2 + ...... =（n + 1）n2≤2n3将中间n＆#47; 2项，如果n＆#47; 4·3n＆#47; 4，则T（n）≥n＆#47； 2·n＆#47; 4·3n＆#47; 4 =（3＆#47; 32）n3根据时间复杂度定义为T（n）= O（n3）下面介绍一个定理，该定理可用于将动态编程算法的时间复杂度进一步降低为O （n2）. 有关详细证明，请参见参考: 定理1: 根[i] [j-1]≤根[i] [j]≤根[i + 1] [j]（有关根数组的定义，请参见算法1）. 也就是说，算法1中的第三个For可以在不循环遍历子树的情况下使用. 所有节点都在其他两个子树的根节点之间的范围内循环.

算法如下，红色部分为修改后的部分: 算法2: 对于子树大小，大小为1到n对于子树的开始，start = 1到（n-size +1）＆#47; ＆#47;树的终点是end = start + size-1，长度是size对于此子树的所有节点，作为根节点root =根[root] [start] [end-1]到Root [start + 1] [end]每个根根据先前计算的Price数组，可以直接获得左右最优子树的成本. 子树的成本可以直接获得: 左子树和右子树的最佳子树成本之和+所有节点的访问概率之和（因为所有节点都被一层掉）价格和根在内部循环中找到最低成本的价格分别记录在价格[开始] [结束]和根[开始] [结束]中. 在分析算法的时间复杂度时，请注意，所研究的子树与所研究的内循环中的根数一一对应. 提前开始时，上一个根的终点与下一个根的起点完全相同（算法中的红色部分）. 对于固定大小，要检查的根部范围应该首先加起来，并且最多要是刚性的. 覆盖所有节点，因此对于每种大小，最多只检查2n个根（在此处缩放），因此总共检查了2n·n = 2n2个子树. 另一方面，根数组中的每个值都对应一个最佳二叉树，也就是说，至少需要检查n2个子树. 所以根据定义T（n）= O（n2）

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