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

看板Soft_Job作者fp60403 (雨蕭)時間7年前 (2018/11/19 22:11)推噓7(7推 0噓 5→)

留言12則, 8人參與討論串2/2 (看更多)

算一下期望值看看，有錯請鞭小力一點。因為你的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 : 想請問這題有什麼方法可以下手嗎？ : 感謝各位大神們 :) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.164.196 ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1542636719.A.E4E.html

推

wheels

11/19 22:30, 7年前 , 1^F

11/19 22:30, 1^F

推

x246libra

11/19 22:34, 7年前 , 2^F

11/19 22:34, 2^F

推

ckp4131025

11/19 22:52, 7年前 , 3^F

11/19 22:52, 3^F