# 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大小的状况下