作者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/m.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