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

看板Soft_Job作者時間5年前 (2018/11/19 17:43), 5年前編輯推噓18(18推 0噓 26→)
留言44則, 22人參與, 5年前最新討論串1/2 (看更多)
# 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
→
11/19 17:50, 5年前 , 1F
R/(R-N)次？
11/19 17:50, 1F
→
11/19 17:51, 5年前 , 2F
答案我也不知道，只想知道有什麼辦法可以切入分析 @@
11/19 17:51, 2F
推
11/19 17:54, 5年前 , 3F
最多就跑R-2次阿
11/19 17:54, 3F
→
11/19 17:55, 5年前 , 4F
為什麼是 R-2 呢？還是有機率一直骰不到 < N 的數吧？
11/19 17:55, 4F
→
11/19 17:56, 5年前 , 5F
我的錯 XD
11/19 17:56, 5F
→
11/19 17:57, 5年前 , 6F
話說應該是問 big O notation，但無從下手起 orz
11/19 17:57, 6F
→
11/19 17:58, 5年前 , 7F
直覺1
11/19 17:58, 7F
→
11/19 17:58, 5年前 , 8F
我看成N只會產生0~R...
11/19 17:58, 8F
推
11/19 18:01, 5年前 , 9F
實務上我會cProfile下去查就對了
11/19 18:01, 9F
→
11/19 18:03, 5年前 , 10F
O( ）
11/19 18:03, 10F
→
11/19 18:03, 5年前 , 11F
O(無限）
11/19 18:03, 11F
推
11/19 18:05, 5年前 , 12F
omega(1)
11/19 18:05, 12F
推
11/19 18:10, 5年前 , 13F
迴圈執行次數是無窮等比級數，每次離開機率是N/R
11/19 18:10, 13F
→
11/19 18:11, 5年前 , 14F
題目是在問次數不是時間複雜度吧
11/19 18:11, 14F
→
11/19 18:14, 5年前 , 15F
其實是在問怎麼估 time complexity啦，寫的不太好
11/19 18:14, 15F
→
11/19 18:15, 5年前 , 16F
真是抱歉@@
11/19 18:15, 16F
→
11/19 18:15, 5年前 , 17F
請多多包涵
11/19 18:15, 17F
→
11/19 18:16, 5年前 , 18F
O(R/(R-N))?
11/19 18:16, 18F
推
11/19 18:52, 5年前 , 19F
不是O(1)嗎? 和跑幾次沒關 跑1次也是 跑100次也是 N/R?
11/19 18:52, 19F
推
11/19 19:55, 5年前 , 20F
如果是big O的話應該是worst case?
11/19 19:55, 20F
推
11/19 20:06, 5年前 , 21F
帕斯卡三角形?
11/19 20:06, 21F
推
11/19 20:19, 5年前 , 22F
把 random() 換成 [0, R) 的均勻分布再往下算就好了啊.
11/19 20:19, 22F
→
11/19 20:19, 5年前 , 23F
變成 [0, 0.01, 0.02, ..., R) 這樣子, 沒必要跟他隨機
11/19 20:19, 23F
→
11/19 22:39, 5年前 , 24F
高雄又美又好 http://bit.ly/2ToBZUc
11/19 22:39, 24F
推
11/20 01:59, 5年前 , 25F
大O的話應該是無限 這演算法不保證會結束
11/20 01:59, 25F
推
11/20 09:30, 5年前 , 26F
樓上的結論怎麼得出的?
11/20 09:30, 26F
→
11/20 09:31, 5年前 , 27F
題目說[0,R)產生的數字機率一樣
11/20 09:31, 27F
→
11/20 09:32, 5年前 , 28F
所以大數法則保證一定會結束
11/20 09:32, 28F
推
11/20 09:41, 5年前 , 29F
如果是PRNG 那更不是probabilistic的範圍
11/20 09:41, 29F
→
11/20 09:41, 5年前 , 30F
因為任何的PRNG都是deterministic
11/20 09:41, 30F
→
11/20 09:42, 5年前 , 31F
換句話說 確定的原因跟大數法則沒關係 因為它不是真隨機
11/20 09:42, 31F
→
11/20 09:43, 5年前 , 32F
這也是為什麼有的樂透可以被破解 因為規則被找到
11/20 09:43, 32F
推
11/20 12:12, 5年前 , 33F
big O不是upper bound嗎？ 沒有結束上限當然是無限
11/20 12:12, 33F
→
11/20 12:12, 5年前 , 34F
大吧？
11/20 12:12, 34F
→
11/20 17:58, 5年前 , 35F
big O可以算average case或worst case
11/20 17:58, 35F
推
11/21 09:48, 5年前 , 36F
while loop的次數也是一個random variavle吧 可以算平
11/21 09:48, 36F
→
11/21 09:48, 5年前 , 37F
均
11/21 09:48, 37F
→
11/21 19:08, 5年前 , 38F
N越大(或越小)，執行時間越久。與N的值是線性關係。所以是
11/21 19:08, 38F
→
11/21 19:08, 5年前 , 39F
O(n)
11/21 19:08, 39F
推
11/21 23:53, 5年前 , 40F
O(N)
11/21 23:53, 40F
推
11/22 02:47, 5年前 , 41F
大數法則有保證會結束嗎？ 趨近而已吧 趨近還是不等於啊
11/22 02:47, 41F
推
11/22 12:59, 5年前 , 42F
O(R)
11/22 12:59, 42F
推
11/24 08:13, 5年前 , 43F
平攤是O(n)
11/24 08:13, 43F
推
11/24 08:17, 5年前 , 44F
但我覺得這是在rand有暫存R大小的狀況下
11/24 08:17, 44F
‣ 更多 wheels 的文章
文章代碼(AID): #1RyeN3Au (Soft_Job)
‣ 更多 wheels 的文章
文章代碼(AID): #1RyeN3Au (Soft_Job)