作者:
fp60403 (雨蕭)
2018-11-19 22:11:57算一下期望值看看,有錯請鞭小力一點。
因為你的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
: 想請問這題有什麼方法可以下手嗎?
: 感謝各位大神們 :)
作者:
wheels 2018-11-19 22:30:00很清楚的解答,非常感謝您的回覆!
期望值定義是什麼,忘光了,哈啊,要去google了
很久非接觸高中數學,又是非本科,大學工科沒接觸離散,所以現在想走程式超弱
作者:
cutekid (可愛小孩子)
2018-11-20 01:06:00推(Y)。事件成功機率的倒數就是期望值!
記得是 平均進行一次所能得到的回報-進行一次的成本像賭博就負的…
作者:
FRAXIS (喔喔)
2018-11-20 11:32:00除了期望值之外 還可以計算 concentration
作者: eatpupu (吃大便) 2018-11-20 20:01:00
樓上大神
作者: Kazimir (Kazimir) 2018-11-20 20:33:00
最近剛學機率 我也試試 把0到R分成兩段 0到N機率是N/R所以幾何分佈期望值就是R/N 應該吧