作者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)