# 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
想請問這題有什麼方法可以下手嗎？
感謝各位大神們 :)

while loop的次數也是一個random variavle吧 可以算平均

R/(R-N)次？

答案我也不知道，只想知道有什麼辦法可以切入分析 @@

最多就跑R-2次阿

為什麼是 R-2 呢？還是有機率一直骰不到 < N 的數吧？

我的錯 XD

話說應該是問 big O notation，但無從下手起 orz

直覺1

我看成N只會產生0~R...

實務上我會cProfile下去查就對了

O( ）O(無限）omega(1)

迴圈執行次數是無窮等比級數，每次離開機率是N/R題目是在問次數不是時間複雜度吧

其實是在問怎麼估 time complexity啦，寫的不太好真是抱歉@@請多多包涵

O(R/(R-N))?

不是O(1)嗎? 和跑幾次沒關 跑1次也是 跑100次也是 N/R?

如果是big O的話應該是worst case?

帕斯卡三角形?

把 random() 換成 [0, R) 的均勻分布再往下算就好了啊.

高雄又美又好 http://bit.ly/2ToBZUc

大O的話應該是無限 這演算法不保證會結束

樓上的結論怎麼得出的?題目說[0,R)產生的數字機率一樣所以大數法則保證一定會結束如果是PRNG 那更不是probabilistic的範圍因為任何的PRNG都是deterministic換句話說 確定的原因跟大數法則沒關係 因為它不是真隨機這也是為什麼有的樂透可以被破解 因為規則被找到

big O不是upper bound嗎？ 沒有結束上限當然是無限大吧？

big O可以算average case或worst case

N越大(或越小)，執行時間越久。與N的值是線性關係。所以是O(n)

O(N)

大數法則有保證會結束嗎？ 趨近而已吧 趨近還是不等於啊

O(R)

平攤是O(n)但我覺得這是在rand有暫存R大小的狀況下