作者EntHeEnd (...)
看板Grad-ProbAsk
標題Re: [理工] [資結]台大98-資工
時間Sun Feb 7 00:41:34 2010
※ 引述《taitin (小南)》之銘言：
: 抱歉這邊錯了，應該要修正成
: 1.{G|for all Xi;Xk>Xi>Xj;1<=k<=i<j<=n}
: 2.{L|for all Xi;XK<Xi<Xj;1<=k<=i<j<=n} (<= 小於或等於)
: G的意思是，所有在位置j之前，Xk為key值大於Xj的數字
: 而Xi，為Xk到Xj中所有符合的數字
: 例如： 21 9 4 25 8 19 29 17 5 6 4 30
: 若Xj選定為 17
: 則Xk可為21 25 19 29 >Xj的數字 且k<j
: 又Xi必須在 21<Xi<17，之間，故為21 19
: 簡單說就是數列中，大於Xj的數字且成遞減排序
請問是要從第一個大於Xj的數字還使取遞減排序的嗎(看起來是這樣 也合理)
因為21是第一個大於17的數 如果21之前再加上 2 22
要取的Xi就變成 22 21 19 這樣 ?
這樣是相當於網頁中的down-records嗎 ?
: L恰好相反
: 數列中，小於Xj的數字且成遞增排序
相當於網頁中的up-records ?
: : 請問插入第i的點 增加高度的期望值為什麼是1/i呢
: 就討論G中，要使XK>Xi>Xj，及討論，Xj為最小值的機率
: 因此，在1~j中，j恰為最小值的機率就是1/j
(Xi~Xj Xj恰為最小值的機率 是這個意思嗎?)
所以第1~第j個數中 最小值位在第j個的機率是1/j...
意思是任意(亂數)取出j個數 第j個是其中最小值的機率是1/j嗎 ?
請問一下這是為什麼呢...orz...
: 然而，這跟j位在第幾個位置有關係，可以肯定的是，j以後的數字完全不用考慮
: 因此依照j可能在的位置的期望值，可知道p(Xj)=1/j
: 又j在每個位置的機率相同，因此總共的期望值就變成
: |G|=p(X1)+p(X2)+...+p(Xn)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.125.176
1F：→ taitin:22 21 19沒錯，從第一個開始取遞減 02/07 00:44
2F：→ taitin:簡單來說，例如五個數字，1 2 3 4 5 02/07 00:44
3F：→ EntHeEnd:j是最小值的機率是1/j 是因為1~j是先亂數取出 02/07 00:44
4F：→ EntHeEnd:然後做排列 最小值在j的機率就是1/j嗎 ? 02/07 00:45
5F：→ taitin:則使 1排在例如 第三個位字的機率 a b 1 c d = 4!/5! 02/07 00:45
6F：→ taitin:對，是你說的這樣 02/07 00:46
7F：→ EntHeEnd:喔喔... 02/07 00:46
: 又j在每個位置的機率相同，因此總共的期望值就變成
: |G|=p(X1)+p(X2)+...+p(Xn)
請問這邊是什麼意思呢 還是不懂 orz...
※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/07 00:50)
8F：→ taitin:我的寫法是比較itoA跟那個網頁的綜合 02/07 00:50
9F：→ taitin:譬如說 5 4 3 2 1，j在第一位成為最小值的機率是1 02/07 00:52
10F：→ taitin:在第二位時成為最小值的機率是1/2 02/07 00:52
11F：→ taitin:然後3rd 1/3 4th 1/4 5th1/5 02/07 00:53
12F：→ taitin:這是光就他是第幾位的期望值來討論 02/07 00:53
13F：→ taitin:又因為j成為第幾位的機率都相等，例如成為第一位的機率是 02/07 00:54
14F：→ taitin:1/n，成為第二位的機率也是1/n....... 02/07 00:54
15F：→ taitin:那所有期望值就會是 每個期望值的總和 02/07 00:55
意思是p(X1)代表j是第一個數前面沒別人 所以他一定是最小值 所以機率是1
P(X2)就是代表考慮到兩個數了第二個數最小的機率就變成1/2這樣...
※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/07 00:57)
16F：→ taitin:這是屬於機率的部分，期望值累加 02/07 00:56
17F：→ EntHeEnd:不過這樣討論算出來的東西的意義是什麼呢 ? 02/07 00:57
18F：→ taitin:你得到他了!!! 02/07 00:57
19F：→ taitin:就是說，在隨機的狀況下，你取任何一個Xj，都可以在 02/07 00:58
20F：→ taitin:路徑logn的狀況下找到，也就是說，對與每個點深度絕不超過 02/07 00:59
21F：→ EntHeEnd:意思是Xk插入時 k有p(Xk)的機會是1~k中最小值 02/07 00:59
22F：→ taitin:logn，那就是樹高為logn的意思 02/07 00:59
23F：→ EntHeEnd:會在down-records多加入k點這個點 對最後的最長path貢獻 02/07 01:00
24F：→ EntHeEnd:1的長度這樣嗎 ? 02/07 01:00
25F：→ taitin:其實我後來想想我那句每次插入的期望值是1/i應該要修掉 02/07 01:03
26F：→ taitin:1/i應該就單純討論，search j那個點的深度期望值就好 02/07 01:04
※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/07 01:10)