Re: [請益] 想請問這個 time complexity 估法？

[fp60403 (雨蕭)]

算一下期望值看看，有錯請鞭小力一點。

因為你的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://www.ptt.cc/bbs/Soft_Job/M.1542636719.A.E4E.html
推 wheels: 很清楚的解答，非常感謝您的回覆！
推 x246libra: 期望值定義是什麼，忘光了，哈啊，要去google了
推 ckp4131025: 期望值要google.....
→ x246libra: 很久非接觸高中數學，又是非本科，大學工科沒接觸離散
→ x246libra: ，所以現在想走程式超弱
推 cutekid: 推(Y)。事件成功機率的倒數就是期望值!
→ cha122977: 記得是 平均進行一次所能得到的回報-進行一次的成本
→ cha122977: 像賭博就負的…
推 FRAXIS: 除了期望值之外 還可以計算 concentration
推 eatpupu: 樓上大神
推 Kazimir: 最近剛學機率 我也試試 把0到R分成兩段 0到N機率是N/R
→ Kazimir: 所以幾何分佈期望值就是R/N 應該吧