作者handofn0xus (你真是糟糕的小焰)
看板graduate
标题[讨论] 台大电机丙资结
时间Sun Feb 17 16:57:47 2019
sort那题是selection,merge跟radix吧
还是题目是问not insensitive?
出来听到有人把insensitive解释成完全相反的意思 快笑死
如果是我错就尴尬惹QQ
难度适中 还行
不过OS跟数学都爆炸了 好像也没差(ˊ;ω;`)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.10.141.210
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/graduate/M.1550393871.A.DE2.html
1F：推 mage594088: 对 应该啦XD 是说身为一个桃园人 偶39.9.38.192 02/17 17:00
2F：→ mage594088: 尔还是会提藻礁的@@39.9.38.192 02/17 17:00
※ 编辑: handofn0xus (39.10.141.210), 02/17/2019 17:02:50
4F：→ skyHuan: intensive???42.73.129.225 02/17 17:03
5F：推 q79236: 可拨223.136.40.238 02/17 17:04
6F：推 jahfone: 资结好佛223.137.156.176 02/17 17:04
7F：嘘 q79236: 可拨223.136.40.238 02/17 17:04
8F：嘘 q79236: 可怜223.136.40.238 02/17 17:05
9F：嘘 q79236: 可悲223.136.40.238 02/17 17:05
10F：嘘 q79236: 洗洗睡223.136.40.238 02/17 17:06
11F：嘘 q79236: 砍掉重练吧 223.136.40.238 02/17 17:06
12F：嘘 q79236: 好累哦223.136.40.238 02/17 17:06
13F：推 yu76: 楼上的宪兵车到了？223.136.130.158 02/17 17:08
14F：推 eric21489: 楼上上就是解释错的那位吗101.137.17.201 02/17 17:09
没 是一对男女
嘘嘘人本尊在我旁边
※ 编辑: handofn0xus (39.10.141.210), 02/17/2019 17:10:44
15F：推 TS28: 我没写radix QQ 39.10.126.184 02/17 17:13
16F：推 BroccolYee: 大家觉得最後一题C range(1,8)有没有223.137.153.252 02/17 17:15
17F：推 chieya: 没写radix+1 223.136.36.97 02/17 17:15
18F：→ BroccolYee: 含尾啊223.137.153.252 02/17 17:15
19F：推 TS28: while j 最後j*2会直接跳出还好有看到== 39.10.126.184 02/17 17:16
20F：推 aa83090202: 数学是非的扣法是会扣其他题的分数吗q 27.246.109.87 02/17 17:21
21F：推 nielhorng: 最後一题只有A吗 223.137.165.95 02/17 17:23
22F：推 ekids1234: insensitive = 对於 input 没感觉 = 39.8.72.2 02/17 17:26
23F：→ ekids1234: select + merge, radix 我没选(？) 39.8.72.2 02/17 17:26
24F：推 wu0h96: 我也选select跟merge 不是用洪逸那个表格114.136.181.116 02/17 17:47
25F：→ wu0h96: 想吗@@114.136.181.116 02/17 17:47
26F：推 meokay: 很多陷阱ㄟ 好可怕 223.136.210.18 02/17 17:48
27F：推 alen0303: 有选radix 101.13.240.22 02/17 17:54
28F：推 qazsedcft402: 最後一题A+ 42.75.149.124 02/17 18:00
29F：推 hank1321: 楼上说while直接跳出是三小 我怎麽不记 114.137.92.113 02/17 18:01
30F：→ hank1321: 得 114.137.92.113 02/17 18:01
31F：推 nielhorng: 楼上大大您最後一题选哪些选项呢？ 114.137.46.180 02/17 18:02
32F：推 hank1321: 我也只选A QQ 有写radix 114.137.92.113 02/17 18:06
33F：→ magic83v: 最後一题选eㄟ 囧 a我第一个删掉 27.242.65.133 02/17 18:06
34F：推 Dora5566: 最後一题全false吧… 101.8.128.219 02/17 18:09
35F：推 sdfg014025xx: 为啥是A180.217.140.177 02/17 18:09
36F：推 busman214: 都没人写BD QQ 223.140.90.140 02/17 18:10
37F：推 nielhorng: 我记得三段程式码 一个算出来 n^3logn 114.137.46.180 02/17 18:10
38F：→ nielhorng: 一个 n(logn)^2 一个n^(1/2) 114.137.46.180 02/17 18:10
39F：→ magic83v: 最後一个1+2+3+.....到<=n 不就加 logn 27.242.65.133 02/17 18:11
40F：推 hank1321: 我也觉得是全false 只好选A 114.137.92.113 02/17 18:11
41F：→ nielhorng: B是说多项式计算那个吗 我觉得是O(n) Q 114.137.46.180 02/17 18:11
42F：→ magic83v: ...== 我喷了吗 27.242.65.133 02/17 18:11
43F：→ hank1321: 嗯我算的跟n大一样 可是楼上有人说会跳 114.137.92.113 02/17 18:12
44F：→ nielhorng: 我也不记得什麽东西有跳… 114.137.46.180 02/17 18:12
45F：推 a3230127: 没选radix+1 39.12.171.176 02/17 18:13
46F：推 mage594088: 最後一题AE+1 39.9.38.192 02/17 18:13
47F：→ nielhorng: A有点忘记题目了,印象中他问某个东西是 114.137.46.180 02/17 18:14
48F：→ nielhorng: 不是O(n),实际上是lgn就行, 但是选O(n) 114.137.46.180 02/17 18:14
49F：→ nielhorng: 也没错就是了 114.137.46.180 02/17 18:14
50F：→ mage594088: 有选Radix 就算已排好 三位数还是要 39.9.38.192 02/17 18:14
51F：→ mage594088: run三次 不是吗@@ 39.9.38.192 02/17 18:14
52F：→ sdfg014025xx: 觉得还是要run有选radix+1180.217.140.177 02/17 18:16
53F：推 jimmy1999: 最後一题我也选ae 42.75.126.16 02/17 18:16
54F：推 TS28: while 从1+n/2到n 但最後有j*=2後必>n跳开还 39.10.126.184 02/17 18:16
55F：→ TS28: 是我理解错了QQ 39.10.126.184 02/17 18:16
56F：→ jimmy1999: j不是j+n/2小於n吗 42.75.126.16 02/17 18:18
57F：→ nielhorng: radix我也有选 想不出什麽情况不是O(d* 114.137.46.180 02/17 18:18
58F：推 sdfg014025xx: 没记错的话j不是一开始是1吗 然後wh180.217.140.177 02/17 18:18
59F：→ sdfg014025xx: ile(j+n/2 <n)180.217.140.177 02/17 18:18
60F：→ nielhorng: (n+r)) 114.137.46.180 02/17 18:18
61F：→ nielhorng: j从1开始哦 114.137.46.180 02/17 18:19
62F：→ nielhorng: 干我突然想通什麽了 O(d(n+r))就不是只 114.137.46.180 02/17 18:23
63F：推 jack1202: 我算全错不过可能像n大说的 自己太直觉 223.140.66.88 02/17 18:23
64F：→ nielhorng: 跟input size有关啊干 114.137.46.180 02/17 18:23
65F：→ jack1202: 想选tight... 223.140.66.88 02/17 18:23
66F：→ jack1202: quadratic 到底要用+-还+@@ 223.140.66.88 02/17 18:27
67F：推 TS28: 噢对 j=1 然後wh ile(j+n/2 <n) 最後有个 39.10.126.184 02/17 18:28
68F：→ TS28: j*=2 2j+n不就一定>n离开while还是我看错j*= 39.10.126.184 02/17 18:28
69F：→ TS28: 2位置了QQ 39.10.126.184 02/17 18:28
70F：推 mage594088: qu那个应该是+- 选项是错的 39.9.38.192 02/17 18:30
71F：推 Dora5566: 最後一题E选项是根号n 我选false 101.8.128.219 02/17 18:30
72F：→ nielhorng: 还是radix sort是说d r固定的情况下tim 114.137.46.180 02/17 18:31
73F：→ nielhorng: e complexity只跟input size有关…跟 114.137.46.180 02/17 18:31
74F：→ nielhorng: 排序无关…妈的好像又是一题看教授心 114.137.46.180 02/17 18:31
75F：→ nielhorng: 情来决定答案的题目 114.137.46.180 02/17 18:32
76F：→ gaowei16: 最後E也false 42.73.40.84 02/17 18:32
77F：推 Dora5566: 最後一题A 我算T(n)=2T(n/2)+1 =O(n) 选 101.8.128.219 02/17 18:33
78F：→ Dora5566: false 101.8.128.219 02/17 18:33
79F：→ nielhorng: 楼上大大这怎麽会false? 114.137.46.180 02/17 18:35
80F：→ minicoke: 是logn 101.137.1.204 02/17 18:35
81F：推 Dora5566: 题目不是给logn吗 101.8.128.219 02/17 18:36
82F：→ jack1202: 欸我跟dora一样 所以真的没得选 223.140.66.88 02/17 18:36
83F：→ nielhorng: logn=O(n)是true啊 114.137.46.180 02/17 18:36
84F：推 chieya: A 若是 16T(n/2) 不会是 O(n)吧=.= 1.167.52.89 02/17 18:37
85F：→ gaowei16: 最後一题我有写A 42.73.40.84 02/17 18:37
86F：→ Dora5566: 题目不是问 会是O(logn)吗 101.8.128.219 02/17 18:37
87F：→ Dora5566: 不就超过了？ 101.8.128.219 02/17 18:37
88F：→ nielhorng: 那也对啊（？ 114.137.46.180 02/17 18:38
89F：→ nielhorng: 你那个式子是logn... 114.137.46.180 02/17 18:38
90F：推 mage594088: n大+1 那是logn 39.9.38.192 02/17 18:39
91F：→ minicoke: Log n 个1 101.137.1.204 02/17 18:40
92F：推 jimmy1999: 你们最後一题的e都算多少qq 42.75.126.16 02/17 18:41
93F：推 Dora5566: ？？？？？ 101.8.128.219 02/17 18:41
94F：推 Dora5566: 你们认真觉得是O(logn)……? 101.8.128.219 02/17 18:44
95F：推 jack1202: 那式子我一直觉得是O(n) 我问题大了 223.140.66.88 02/17 18:46
96F：→ nielhorng: 你把树画出来… 114.137.46.180 02/17 18:47
97F：→ nielhorng: 每曾多少 然後树高多少……… 114.137.46.180 02/17 18:47
99F：推 jack1202: 树高lg 但每层和不是1啊 223.140.66.88 02/17 18:49
100F：推 nielhorng: 干对也…对不起我笨 114.137.46.180 02/17 18:50
101F：推 mage594088: QQ 39.9.38.192 02/17 18:51
102F：推 eric21489: DS的倒扣真d刺激.... 101.137.17.201 02/17 18:52
103F：推 Leaving: A不用乘系数2 所以是logn没错 180.204.17.202 02/17 18:53
104F：→ Leaving: 他只说把problem size乘一个fraction而已 180.204.17.202 02/17 18:53
105F：推 Dora5566: 为什麽不用乘?！ 101.8.128.219 02/17 18:53
106F：推 chieya: 我怎麽记得他说是常数倍的 T的分数式=.= 1.167.52.89 02/17 18:54
107F：→ Leaving: 大概跟binary search的意思一样 180.204.17.202 02/17 18:54
108F：→ minicoke: 看一下林立宇蓝色那本 我也忘了 101.137.1.204 02/17 18:54
110F：→ ponponjerry: (b)对还错呢？还是看教授心情XD 42.73.89.74 02/17 18:54
111F：→ minicoke: 之前我也想过这个问题 101.137.1.204 02/17 18:54
112F：→ chieya: b不就是O(n)吗？题目n^2怎麽会对@@ 1.167.52.89 02/17 18:56
113F：→ nielhorng: 这题目看起来不像是不用乘2… 114.137.46.180 02/17 18:57
114F：推 jack1202: 嗯题目不记得了 当时我是乘个a如果a=1 223.140.66.88 02/17 18:58
115F：→ jack1202: 的确gg 223.140.66.88 02/17 18:59
116F：→ jack1202: b是给theta还O啊 223.140.66.88 02/17 19:00
117F：推 qazsedcft402: 他的fraction是不是只0<a<1然後 42.75.149.124 02/17 19:02
118F：→ qazsedcft402: T(n)=T(an)+T((1-a)n)+1？ 42.75.149.124 02/17 19:03
119F：→ Leaving: 我记得的题目是 在常数的时间内 将proble 180.204.17.202 02/17 19:06
120F：→ Leaving: m size乘上一个常数的fraction 180.204.17.202 02/17 19:06
121F：→ Leaving: 所以我觉得是T(n)=T(n/k)+c 180.204.17.202 02/17 19:06
122F：推 Dora5566: 不是cut the problem into fraction吗 101.8.128.219 02/17 19:07
123F：→ Leaving: 哦哦 好像是 不过这句话我是照我上面说的 180.204.17.202 02/17 19:08
124F：→ Leaving: 那样解读的 180.204.17.202 02/17 19:08
125F：推 Dora5566: 题目好像没说演算法的目的? 101.8.128.219 02/17 19:12
126F：→ Dora5566: 如果是sort 就标准的D&C 然後cut从O(n) 101.8.128.219 02/17 19:14
127F：→ Dora5566: 变常数 sort复杂度变O(n) 101.8.128.219 02/17 19:14
128F：→ Dora5566: 不过题目给O(logn) 感觉就是想考unsorte 101.8.128.219 02/17 19:17
129F：→ Dora5566: d array的binary search 把cut变常数 不 101.8.128.219 02/17 19:17
130F：→ Dora5566: 考虑input也是O(log) 而且也不太可能5个 101.8.128.219 02/17 19:17
131F：→ Dora5566: 全false 唉烂题目 101.8.128.219 02/17 19:17
132F：→ Dora5566: 算了我要去看史莱姆了 希望昨天考的会 101.8.128.219 02/17 19:18
133F：→ Dora5566: 正取 101.8.128.219 02/17 19:18
134F：→ qazsedcft402: 所以答案B？？？真的烂 42.75.149.124 02/17 19:18
135F：推 jack1202: 这样看答案比较像B O(n) =O(n平方) 223.140.66.88 02/17 19:19
136F：→ Dora5566: 答案"应该"是A , B是问theta(n^2)那题 101.8.128.219 02/17 19:20
137F：→ Dora5566: 最多O(n)可解 101.8.128.219 02/17 19:20
138F：推 qazsedcft402: 可是他不是写Big Oh（n^2)吗 42.75.149.124 02/17 19:22
139F：推 mage594088: 楼上说好有道理TAT 123.192.85.90 02/17 19:23
140F：推 chieya: 没人只选D吗？ 1.167.52.89 02/17 19:24
141F：推 we777: 可以空的化说不定交白卷还比我认真血糕= = 49.217.22.66 02/17 19:25
142F：推 hank1321: B是问theta(n^2)吧 114.137.92.113 02/17 19:41
143F：推 f101202: 我选ACD嘿118.160.173.203 02/17 19:54
144F：→ eatagary: 16题没有A啦 反例 D大都给你们了，可以114.136.154.167 02/17 19:59
145F：→ eatagary: 不用吵了看不下去了。114.136.154.167 02/17 19:59
146F：推 sdfg014025xx: 结论：垃圾考卷180.217.140.177 02/17 20:22
147F：推 acen2019: 考完台大後只觉得最高的智慧真的是直觉 223.140.66.77 02/17 20:30
148F：→ acen2019: ，运气很重要 223.140.66.77 02/17 20:31
149F：推 YOLOO: 没事 台大什麽的 让我们继续准备成大 36.227.135.236 02/17 22:32
150F：推 kcilao110779: 怎麽没用112ip发文 180.217.187.32 02/17 23:46
151F：推 ko330: range(1,8)发现只有7次,感觉是考你会不会py 122.116.51.188 02/17 23:55
152F：→ Dora5566: 1 2 3 4 5 6 7 8 101.8.128.219 02/18 00:03
153F：→ Dora5566: 还是range不是真的range? 没写过 101.8.128.219 02/18 00:04
154F：推 misaka0120: 他又没说是py 只是长得很像的pseudoco 101.9.33.80 02/18 00:39
155F：→ misaka0120: de 101.9.33.80 02/18 00:39
156F：推 ko330: 但他语法就是py阿，教授给py程式码，却说这 122.116.51.188 02/18 00:50
157F：→ ko330: 是因为psudocode所以是1~8喔，感觉不太合理 122.116.51.188 02/18 00:50
158F：推 hank1321: Pseudocode不是很常这样表示1~8吗... 114.137.92.113 02/18 01:36
159F：→ eatagary: 可能只是想表达常数O(1)的概念而已，别114.136.154.167 02/18 11:39
160F：→ eatagary: 想太多114.136.154.167 02/18 11:39
161F：→ ssd860505da: 资结为啥题目那麽少啊... 140.112.25.121 02/18 15:26