作者fp60403 (雨萧)
看板Soft_Job
标题Re: [请益] 想请问这个 time complexity 估法？
时间Mon Nov 19 22:11:57 2018
算一下期望值看看，有错请鞭小力一点。
因为你的rand没说只取整数，从线段来看就是总长是R，
落在N以内就结束(机率N/R)，N到R之间就继续(机率(R-N)/R)。
期望值 E = 1*(N/R) + 2*(N/R)*((R-N)/R) + 3*(N/R)*((R-N)/R)^2 + ......
((R-N)/R) * E = 1*(N/R)*((R-N)/R) + 2*(N/R)*((R-N)/R)^2 + ......
相减後得
(N/R) * E = (N/R) + (N/R)*((R-N)/R) + (N/R)*((R-N)/R)^2 + ......
= (N/R) / (N/R) = 1 (无穷等比级数，和等於 a/1-r )
E = R / N
所以期望值会跑的次数是R/N次，一般你在说R > N > 0的时候，
因为N还是不固定(尽管有上限)，所以不会将它当作O(R/R)=O(1)来看，
我的话我会回答average case为O(R/N)或期望值为R/N次就好。
※ 引述《wheels ()》之铭言：
: # Python3
: # rand() will return number from [0, R) with the same posibility
: # assume R > N > 0
: def getNum(N):
: num = rand()
: while num > N:
: num = rand()
: return num
: # How many times the while-loop may executed?
: 若要以 R 跟 N 表示 time complexity
: 想请问这题有什麽方法可以下手吗？
: 感谢各位大神们 :)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.168.164.196
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1542636719.A.E4E.html
1F：推 wheels: 很清楚的解答，非常感谢您的回覆！ 11/19 22:30
2F：推 x246libra: 期望值定义是什麽，忘光了，哈啊，要去google了 11/19 22:34
3F：推 ckp4131025: 期望值要google..... 11/19 22:52
4F：→ x246libra: 很久非接触高中数学，又是非本科，大学工科没接触离散 11/19 23:01
5F：→ x246libra: ，所以现在想走程式超弱 11/19 23:01
6F：推 cutekid: 推(Y)。事件成功机率的倒数就是期望值! 11/20 01:06
7F：→ cha122977: 记得是 平均进行一次所能得到的回报-进行一次的成本 11/20 01:19
8F：→ cha122977: 像赌博就负的… 11/20 01:21
9F：推 FRAXIS: 除了期望值之外 还可以计算 concentration 11/20 11:32
10F：推 eatpupu: 楼上大神 11/20 20:01
11F：推 Kazimir: 最近刚学机率 我也试试 把0到R分成两段 0到N机率是N/R 11/20 20:33
12F：→ Kazimir: 所以几何分布期望值就是R/N 应该吧 11/20 20:34