作者wheels ()
看板Soft_Job
标题[请益] 想请问这个 time complexity 估法？
时间Mon Nov 19 17:43:28 2018
# 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://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1542620611.A.2B8.html
※ 编辑: wheels (1.163.221.45), 11/19/2018 17:49:52
1F：→ AnifalaKeiko: R/(R-N)次？ 11/19 17:50
2F：→ wheels: 答案我也不知道，只想知道有什麽办法可以切入分析 @@ 11/19 17:51
3F：推 motherboard: 最多就跑R-2次阿 11/19 17:54
4F：→ wheels: 为什麽是 R-2 呢？还是有机率一直骰不到 < N 的数吧？ 11/19 17:55
5F：→ motherboard: 我的错 XD 11/19 17:56
6F：→ wheels: 话说应该是问 big O notation，但无从下手起 orz 11/19 17:57
7F：→ dnabossking: 直觉1 11/19 17:58
8F：→ motherboard: 我看成N只会产生0~R... 11/19 17:58
9F：推 ripple0129: 实务上我会cProfile下去查就对了 11/19 18:01
10F：→ Domos: O( ） 11/19 18:03
11F：→ Domos: O(无限） 11/19 18:03
12F：推 Domos: omega(1) 11/19 18:05
13F：推 ohohoh: 回圈执行次数是无穷等比级数，每次离开机率是N/R 11/19 18:10
14F：→ ohohoh: 题目是在问次数不是时间复杂度吧 11/19 18:11
15F：→ wheels: 其实是在问怎麽估 time complexity啦，写的不太好 11/19 18:14
16F：→ wheels: 真是抱歉@@ 11/19 18:15
17F：→ wheels: 请多多包涵 11/19 18:15
18F：→ sherees: O(R/(R-N))? 11/19 18:16
19F：推 gofigure: 不是O(1)吗? 和跑几次没关 跑1次也是 跑100次也是 N/R? 11/19 18:52
20F：推 kokacal: 如果是big O的话应该是worst case? 11/19 19:55
21F：推 ernieyang09: 帕斯卡三角形? 11/19 20:06
22F：推 Muscovy: 把 random() 换成 [0, R) 的均匀分布再往下算就好了啊. 11/19 20:19
23F：→ Muscovy: 变成 [0, 0.01, 0.02, ..., R) 这样子, 没必要跟他随机 11/19 20:19
25F：推 itoni: 大O的话应该是无限 这演算法不保证会结束 11/20 01:59
26F：推 gofigure: 楼上的结论怎麽得出的? 11/20 09:30
27F：→ gofigure: 题目说[0,R)产生的数字机率一样 11/20 09:31
28F：→ gofigure: 所以大数法则保证一定会结束 11/20 09:32
29F：推 gofigure: 如果是PRNG 那更不是probabilistic的范围 11/20 09:41
30F：→ gofigure: 因为任何的PRNG都是deterministic 11/20 09:41
31F：→ gofigure: 换句话说 确定的原因跟大数法则没关系 因为它不是真随机 11/20 09:42
32F：→ gofigure: 这也是为什麽有的乐透可以被破解 因为规则被找到 11/20 09:43
33F：推 youtuuube000: big O不是upper bound吗？ 没有结束上限当然是无限 11/20 12:12
34F：→ youtuuube000: 大吧？ 11/20 12:12
35F：→ cha122977: big O可以算average case或worst case 11/20 17:58
36F：推 BangSaint: while loop的次数也是一个random variavle吧 可以算平 11/21 09:48
37F：→ BangSaint: 均 11/21 09:48
38F：→ DrTech: N越大(或越小)，执行时间越久。与N的值是线性关系。所以是 11/21 19:08
39F：→ DrTech: O(n) 11/21 19:08
40F：推 reymk619: O(N) 11/21 23:53
41F：推 iq1000x: 大数法则有保证会结束吗？ 趋近而已吧 趋近还是不等於啊 11/22 02:47
42F：推 CJacky: O(R) 11/22 12:59
43F：推 pig2014: 平摊是O(n) 11/24 08:13
44F：推 pig2014: 但我觉得这是在rand有暂存R大小的状况下 11/24 08:17