❶ 二叉搜索樹和最優二叉搜索樹的時間復雜度各是多少
二叉查找樹（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情況時的子問題， 共T(n-1)種；當第二個元素作為根節點時，左子樹有1個元素，右子樹有n-2個元素，根據乘法原理共有T(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)) / x
= (f(x) - 1) / x
這樣解方程得到 f(x) = [1 - (1 - 4x)1/2 ] / 2x
右邊進行泰勒展開，再與定義式比較最終得到： T(n) = (2n)! / (n!(n+1)!)
然後根據Stirling公式：n! ～ (2πn)1/2 · (n/e)n
於是有(2n)! / n!(n+1)! ～ (4n1/2 · 2n2n ) / (2n1/2 · nn · (2(n+1))1/2 · (n+1)n )
～ 4n · (n+1)-3/2 · (n/(n+1))n
～ 4n · n-3/2
因此最後得到窮舉方法構造最優二叉查找樹的時間復雜度： T(n) = O(4n · n-3/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 = <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(n2 )的演算法。
對於子樹大小為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，則有 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 )
下面介紹一個定理，可以藉此把動態規劃演算法的時間復雜度進一步降到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 )
❷ 求一般圖的最大權匹配的演算法（最好詳細一些，注意數最大權匹配），高分求助！
Algorithmus 3.3 Kruskal's Algorithm 時間復雜度 O(mlog n)
m邊數 n點數
輸入: 圖 G = (V;E) 和 權c : E -》R.
輸出: 一棵最優樹 T.
begin
把所有邊以權的大小按從小到大排序
T := (VG，ET ) := (VG， 空);
for i = 1 to m do
if T + ei 沒有圈 then
T := (VG;ET 並上 {ei});
if end
for end
end
或者 Algorithmus 3.5 Prim's Algorithm 時間復雜度O(m+n log n)