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

作者: wheels   2018-11-19 17:43:28
# 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
想請問這題有什麼方法可以下手嗎?
感謝各位大神們 :)
作者: BangSaint (真的不想嘴)   2018-11-21 09:48:00
while loop的次數也是一個random variavle吧 可以算平均
作者: AnifalaKeiko (Yukinari)   2018-11-19 17:50:00
R/(R-N)次?
作者: wheels   2018-11-19 17:51:00
答案我也不知道,只想知道有什麼辦法可以切入分析 @@
作者: motherboard (媽的Ball)   2018-11-19 17:54:00
最多就跑R-2次阿
作者: wheels   2018-11-19 17:55:00
為什麼是 R-2 呢?還是有機率一直骰不到 < N 的數吧?
作者: motherboard (媽的Ball)   2018-11-19 17:56:00
我的錯 XD
作者: wheels   2018-11-19 17:57:00
話說應該是問 big O notation,但無從下手起 orz
作者: dnabossking (少狂)   2018-11-19 17:58:00
直覺1
作者: motherboard (媽的Ball)   2018-11-19 17:58:00
我看成N只會產生0~R...
作者: ripple0129 (perry tsai)   2018-11-19 18:01:00
實務上我會cProfile下去查就對了
作者: Domos (沒事發發廢文)   2018-11-19 18:03:00
O( )O(無限)omega(1)
作者: ohohoh   2018-11-19 18:10:00
迴圈執行次數是無窮等比級數,每次離開機率是N/R題目是在問次數不是時間複雜度吧
作者: wheels   2018-11-19 18:14:00
其實是在問怎麼估 time complexity啦,寫的不太好真是抱歉@@請多多包涵
作者: sherees (ShaunTheSheep)   2018-11-19 18:16:00
O(R/(R-N))?
作者: gofigure (平行世界)   2018-11-19 18:52:00
不是O(1)嗎? 和跑幾次沒關 跑1次也是 跑100次也是 N/R?
作者: kokacal   2018-11-19 19:55:00
如果是big O的話應該是worst case?
作者: ernieyang09 (亂入)   2018-11-19 20:06:00
帕斯卡三角形?
作者: Muscovy (三分熟的鬧鐘)   2018-11-19 20:19:00
把 random() 換成 [0, R) 的均勻分布再往下算就好了啊.
作者: creativity8 (王元龍)   2018-11-19 22:39:00
高雄又美又好 http://bit.ly/2ToBZUc
作者: itoni (每天都過得很混)   2018-11-20 01:59:00
大O的話應該是無限 這演算法不保證會結束
作者: gofigure (平行世界)   2018-11-20 09:30:00
樓上的結論怎麼得出的?題目說[0,R)產生的數字機率一樣所以大數法則保證一定會結束如果是PRNG 那更不是probabilistic的範圍因為任何的PRNG都是deterministic換句話說 確定的原因跟大數法則沒關係 因為它不是真隨機這也是為什麼有的樂透可以被破解 因為規則被找到
作者: youtuuube000 (小孩)   2018-11-20 12:12:00
big O不是upper bound嗎? 沒有結束上限當然是無限大吧?
作者: cha122977 (CHA)   2018-11-20 17:58:00
big O可以算average case或worst case
作者: DrTech (竹科管理處網軍研發人員)   2018-11-21 19:08:00
N越大(或越小),執行時間越久。與N的值是線性關係。所以是O(n)
作者: reymk619 (千鳥流風)   2018-11-21 23:53:00
O(N)
作者: iq1000x (台串彭于晏)   2018-11-22 02:47:00
大數法則有保證會結束嗎? 趨近而已吧 趨近還是不等於啊
作者: CJacky (西傑)   2018-11-22 12:59:00
O(R)
作者: pig2014 (Rocking Man)   2018-11-24 08:13:00
平攤是O(n)但我覺得這是在rand有暫存R大小的狀況下

Links booklink

Contact Us: admin [ a t ] ucptt.com