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

二叉搜索树
最好：以2为底n的对数
最坏：n
最优二叉搜索树
最好/最坏：以2为底n的对数

二叉查找树（BST，Binary Search Tree） ，又名二叉搜索树或二叉检索树，是一颗满足如下条件的树：
1、每个节点包含一个键值
2、每个节点有最多两个孩子
3、对于任意两个节点x和y，它们满足下述搜索性质:
a、如果y在x的左子树里，则key[y] <= key[x]
b、如果y在x的右子树里，则key[y] >= key[x]

最优二叉查找树（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、穷举
穷举构造最优二叉查找树，其实就是这样的一个问题：
给一个拥有n个数的已排序的节点，可以将其构造成多少种不同的BST（用来找到一个最优的二叉查找树）？
设可以构造成T(n)个，那么枚举每一个元素作为根节点的情况，当第一个元素作为根节点时，其余n-1个构成右子树，无左子树，是n-1情