Re: [理工] [資結]台大98-資工

[EntHeEnd (...)]

※ 引述《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
→ taitin:22 21 19沒錯，從第一個開始取遞減
→ taitin:簡單來說，例如五個數字，1 2 3 4 5
→ EntHeEnd:j是最小值的機率是1/j 是因為1~j是先亂數取出
→ EntHeEnd:然後做排列 最小值在j的機率就是1/j嗎 ?
→ taitin:則使 1排在例如 第三個位字的機率 a b 1 c d  = 4!/5!
→ taitin:對，是你說的這樣
→ EntHeEnd:喔喔...

: 又j在每個位置的機率相同，因此總共的期望值就變成
: |G|=p(X1)+p(X2)+...+p(Xn)

請問這邊是什麼意思呢 還是不懂 orz...
※ 編輯: EntHeEnd        來自: 59.126.125.176       (02/07 00:50)
→ taitin:我的寫法是比較itoA跟那個網頁的綜合
→ taitin:譬如說 5 4 3 2 1，j在第一位成為最小值的機率是1
→ taitin:在第二位時成為最小值的機率是1/2
→ taitin:然後3rd 1/3  4th 1/4  5th1/5
→ taitin:這是光就他是第幾位的期望值來討論
→ taitin:又因為j成為第幾位的機率都相等，例如成為第一位的機率是
→ taitin:1/n，成為第二位的機率也是1/n.......
→ taitin:那所有期望值就會是 每個期望值的總和
意思是p(X1)代表j是第一個數前面沒別人 所以他一定是最小值 所以機率是1
P(X2)就是代表考慮到兩個數了第二個數最小的機率就變成1/2這樣...
※ 編輯: EntHeEnd        來自: 59.126.125.176       (02/07 00:57)
→ taitin:這是屬於機率的部分，期望值累加
→ EntHeEnd:不過這樣討論算出來的東西的意義是什麼呢 ?
→ taitin:你得到他了!!!
→ taitin:就是說，在隨機的狀況下，你取任何一個Xj，都可以在
→ taitin:路徑logn的狀況下找到，也就是說，對與每個點深度絕不超過
→ EntHeEnd:意思是Xk插入時 k有p(Xk)的機會是1~k中最小值
→ taitin:logn，那就是樹高為logn的意思
→ EntHeEnd:會在down-records多加入k點這個點 對最後的最長path貢獻
→ EntHeEnd:1的長度這樣嗎 ?
→ taitin:其實我後來想想我那句每次插入的期望值是1/i應該要修掉
→ taitin:1/i應該就單純討論，search j那個點的深度期望值就好
※ 編輯: EntHeEnd        來自: 59.126.125.176       (02/07 01:10)