最优二叉搜索树算法的时间复杂性

最优二叉搜索树算法的时间复杂度为 Θ(n^3)，与矩阵链乘法问题的时间复杂度相同。该算法采用自下而上的动态规划方法来求解最优二叉搜索树问题，遍历以 ki, ki+1, …, kj 作为根结点的情况，并选择期望搜索代价最小的情况作为子问题的最优解。根据递归式，我们可以得到最优二叉搜索树子问题的期望搜索代价，并记录最优二叉搜索树子问题的根结点。最后，通过自下而上的动态规划方法求解整个问题。