請問二元搜尋樹插入法 |
|
尚未結案
|
|
pav0914
一般會員   發表：4 回覆：6 積分：2 註冊：2004-01-10 發送簡訊給我 |
|
|
gmobug
一般會員 發表：10 回覆：28 積分：12 註冊：2004-02-04 發送簡訊給我 |
其實我自己對這方面不太懂，但是書上有看到相關的：
(以下轉載自松崗-演算法導論-蕭世文譯)
p.12-5
//---------------------------------------------轉載開始
理論12.1
如果x是一棵有n個節點的子數的根，則呼叫INORDER-TREE-WALK(x)花費θ(n)的時間。
********************************
證明 讓T(n)表示INORDER-TREE-WALK在一棵有n個節點的子數的根部上被呼叫時所花的時間。INORDER-TREE-WALK在每一棵空子樹(測試x≠NIL)上花費一個小量，常數數目的時間，所以T(0)=c其中c是某個正值常數。 對n>0，假設INORDER-TREE-WALK在一個節點x上被呼叫，x的左邊子樹有k個節點，而x的右邊子樹有n-k-1個節點。執行INORDER-TREE-WALK(x)的時間是T(n)=T(k) T(n-k-1) d，其中d是反映執行INORDER-TREE-WALK(x)所需時間，不包函花在遞迴呼叫上的時間，的某個正值常數。 我們使用取代方法來顯示T(n)=θ(n)來證明T(n)=(c d)n c。對n=0，我們有(c d)˙0 c=c=T(0)。對n>0，我們有： T(n)=T(k) T(n-k-1) d
=((c d)k c) ((c d)(n-k-1) c) d
=(c d)n c-(c d) c d
=(c d)n c 此完成證明
//------------------------------------------------轉載結束 看起來像是要帶進去算，但是實際上應該還要加上遞迴呼叫花掉的時間，因為樹內散步是個遞迴演算法。
|
|
pav0914
一般會員 發表：4 回覆：6 積分：2 註冊：2004-01-10 發送簡訊給我 |
發表時間：2004-01-10 15:28:39
IP:220.130.xxx.xxx 未訂閱
系統時間：2024-12-04 1:13:28
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |