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

[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), 來自: 1.163.221.45
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1542620611.A.2B8.html
※ 編輯: wheels (1.163.221.45), 11/19/2018 17:49:52
→ AnifalaKeiko: R/(R-N)次？
→ wheels: 答案我也不知道，只想知道有什麼辦法可以切入分析 @@
推 motherboard: 最多就跑R-2次阿
→ wheels: 為什麼是 R-2 呢？還是有機率一直骰不到 < N 的數吧？
→ motherboard: 我的錯 XD
→ wheels: 話說應該是問 big O notation，但無從下手起 orz
→ dnabossking: 直覺1
→ motherboard: 我看成N只會產生0~R...
推 ripple0129: 實務上我會cProfile下去查就對了
→ Domos: O(  ）
→ Domos: O(無限）
推 Domos: omega(1)
推 ohohoh: 迴圈執行次數是無窮等比級數，每次離開機率是N/R
→ ohohoh: 題目是在問次數不是時間複雜度吧
→ wheels: 其實是在問怎麼估 time complexity啦，寫的不太好
→ wheels: 真是抱歉@@
→ wheels: 請多多包涵
→ sherees: O(R/(R-N))?
推 gofigure: 不是O(1)嗎? 和跑幾次沒關 跑1次也是 跑100次也是 N/R?
推 kokacal: 如果是big O的話應該是worst case?
推 ernieyang09: 帕斯卡三角形?
推 Muscovy: 把 random() 換成 [0, R) 的均勻分布再往下算就好了啊.
→ Muscovy: 變成 [0, 0.01, 0.02, ..., R) 這樣子, 沒必要跟他隨機
→ creativity8: 高雄又美又好 http://bit.ly/2ToBZUc
推 itoni: 大O的話應該是無限 這演算法不保證會結束
推 gofigure: 樓上的結論怎麼得出的?
→ gofigure: 題目說[0,R)產生的數字機率一樣
→ gofigure: 所以大數法則保證一定會結束
推 gofigure: 如果是PRNG 那更不是probabilistic的範圍
→ gofigure: 因為任何的PRNG都是deterministic
→ gofigure: 換句話說 確定的原因跟大數法則沒關係 因為它不是真隨機
→ gofigure: 這也是為什麼有的樂透可以被破解 因為規則被找到
推 youtuuube000: big O不是upper bound嗎？ 沒有結束上限當然是無限
→ youtuuube000: 大吧？
→ cha122977: big O可以算average case或worst case
推 BangSaint: while loop的次數也是一個random variavle吧 可以算平
→ BangSaint: 均
→ DrTech: N越大(或越小)，執行時間越久。與N的值是線性關係。所以是
→ DrTech: O(n)
推 reymk619: O(N)
推 iq1000x: 大數法則有保證會結束嗎？ 趨近而已吧 趨近還是不等於啊
推 CJacky: O(R)
推 pig2014: 平攤是O(n)
推 pig2014: 但我覺得這是在rand有暫存R大小的狀況下