算一下期望值看看,有错请鞭小力一点。
因为你的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
: 想请问这题有什么方法可以下手吗?
: 感谢各位大神们 :)