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

看板Grad-ProbAsk作者 (...)時間16年前 (2010/02/07 00:41), 編輯推噓0(0推 0噓 26→)
留言26則, 2人參與, 最新討論串5/7 (看更多)
※ 引述《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
→
02/07 00:44, , 1F
22 21 19沒錯，從第一個開始取遞減
02/07 00:44, 1F
→
02/07 00:44, , 2F
簡單來說，例如五個數字，1 2 3 4 5
02/07 00:44, 2F
→
02/07 00:44, , 3F
j是最小值的機率是1/j 是因為1~j是先亂數取出
02/07 00:44, 3F
→
02/07 00:45, , 4F
然後做排列 最小值在j的機率就是1/j嗎 ?
02/07 00:45, 4F
→
02/07 00:45, , 5F
則使 1排在例如 第三個位字的機率 a b 1 c d = 4!/5!
02/07 00:45, 5F
→
02/07 00:46, , 6F
對，是你說的這樣
02/07 00:46, 6F
→
02/07 00:46, , 7F
喔喔...
02/07 00:46, 7F
: 又j在每個位置的機率相同，因此總共的期望值就變成 : |G|=p(X1)+p(X2)+...+p(Xn) 請問這邊是什麼意思呢 還是不懂 orz... ※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/07 00:50)
→
02/07 00:50, , 8F
我的寫法是比較itoA跟那個網頁的綜合
02/07 00:50, 8F
→
02/07 00:52, , 9F
譬如說 5 4 3 2 1，j在第一位成為最小值的機率是1
02/07 00:52, 9F
→
02/07 00:52, , 10F
在第二位時成為最小值的機率是1/2
02/07 00:52, 10F
→
02/07 00:53, , 11F
然後3rd 1/3 4th 1/4 5th1/5
02/07 00:53, 11F
→
02/07 00:53, , 12F
這是光就他是第幾位的期望值來討論
02/07 00:53, 12F
→
02/07 00:54, , 13F
又因為j成為第幾位的機率都相等，例如成為第一位的機率是
02/07 00:54, 13F
→
02/07 00:54, , 14F
1/n，成為第二位的機率也是1/n.......
02/07 00:54, 14F
→
02/07 00:55, , 15F
那所有期望值就會是 每個期望值的總和
02/07 00:55, 15F
意思是p(X1)代表j是第一個數前面沒別人 所以他一定是最小值 所以機率是1 P(X2)就是代表考慮到兩個數了第二個數最小的機率就變成1/2這樣... ※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/07 00:57)
→
02/07 00:56, , 16F
這是屬於機率的部分，期望值累加
02/07 00:56, 16F
→
02/07 00:57, , 17F
不過這樣討論算出來的東西的意義是什麼呢 ?
02/07 00:57, 17F
→
02/07 00:57, , 18F
你得到他了!!!
02/07 00:57, 18F
→
02/07 00:58, , 19F
就是說，在隨機的狀況下，你取任何一個Xj，都可以在
02/07 00:58, 19F
→
02/07 00:59, , 20F
路徑logn的狀況下找到，也就是說，對與每個點深度絕不超過
02/07 00:59, 20F
→
02/07 00:59, , 21F
意思是Xk插入時 k有p(Xk)的機會是1~k中最小值
02/07 00:59, 21F
→
02/07 00:59, , 22F
logn，那就是樹高為logn的意思
02/07 00:59, 22F
→
02/07 01:00, , 23F
會在down-records多加入k點這個點 對最後的最長path貢獻
02/07 01:00, 23F
→
02/07 01:00, , 24F
1的長度這樣嗎 ?
02/07 01:00, 24F
→
02/07 01:03, , 25F
其實我後來想想我那句每次插入的期望值是1/i應該要修掉
02/07 01:03, 25F
→
02/07 01:04, , 26F
1/i應該就單純討論，search j那個點的深度期望值就好
02/07 01:04, 26F
※ 編輯: EntHeEnd 來自: 59.126.125.176 (02/07 01:10)
‣ 更多 EntHeEnd 的文章
文章代碼(AID): #1BRPl1So (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 7 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共7篇)
‣ 更多 EntHeEnd 的文章
文章代碼(AID): #1BRPl1So (Grad-ProbAsk)