[討論] 台大電機丙資結

[handofn0xus (你真是糟糕的小焰)]

sort那題是selection,merge跟radix吧
還是題目是問not insensitive?
出來聽到有人把insensitive解釋成完全相反的意思 快笑死

如果是我錯就尷尬惹QQ


難度適中 還行
不過OS跟數學都爆炸了 好像也沒差(ˊ;ω;`)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.141.210
※ 文章網址: https://www.ptt.cc/bbs/graduate/M.1550393871.A.DE2.html
推 mage594088: 對 應該啦XD 是說身為一個桃園人 偶
→ mage594088: 爾還是會提藻礁的@@
※ 編輯: handofn0xus (39.10.141.210), 02/17/2019 17:02:50
噓 skyHuan: https://i.imgur.com/VyshSPl.jpg
→ skyHuan: intensive???
推 q79236: 可撥
推 jahfone: 資結好佛
噓 q79236: 可撥
噓 q79236: 可憐
噓 q79236: 可悲
噓 q79236: 洗洗睡
噓 q79236: 砍掉重練吧
噓 q79236: 好累哦
推 yu76: 樓上的憲兵車到了？
推 eric21489: 樓上上就是解釋錯的那位嗎
沒 是一對男女
噓噓人本尊在我旁邊
※ 編輯: handofn0xus (39.10.141.210), 02/17/2019 17:10:44
推 TS28: 我沒寫radix QQ
推 BroccolYee: 大家覺得最後一題C range(1,8)有沒有
推 chieya: 沒寫radix+1
→ BroccolYee: 含尾啊
推 TS28: while j 最後j*2會直接跳出還好有看到==
推 aa83090202: 數學是非的扣法是會扣其他題的分數嗎q
推 nielhorng: 最後一題只有A嗎
推 ekids1234: insensitive = 對於 input 沒感覺 =
→ ekids1234: select + merge, radix 我沒選(？)
推 wu0h96: 我也選select跟merge 不是用洪逸那個表格
→ wu0h96: 想嗎@@
推 meokay: 很多陷阱ㄟ 好可怕
推 alen0303: 有選radix
推 qazsedcft402: 最後一題A+
推 hank1321: 樓上說while直接跳出是三小 我怎麼不記
→ hank1321: 得
推 nielhorng: 樓上大大您最後一題選哪些選項呢？
推 hank1321: 我也只選A QQ 有寫radix
→ magic83v: 最後一題選eㄟ  囧 a我第一個刪掉
推 Dora5566: 最後一題全false吧…
推 sdfg014025xx: 為啥是A
推 busman214: 都沒人寫BD QQ
推 nielhorng: 我記得三段程式碼 一個算出來 n^3logn
→ nielhorng:  一個 n(logn)^2 一個n^(1/2)
→ magic83v: 最後一個1+2+3+.....到<=n  不就加 logn
推 hank1321: 我也覺得是全false 只好選A
→ nielhorng: B是說多項式計算那個嗎 我覺得是O(n) Q
→ magic83v: ...== 我噴了嗎
→ hank1321: 嗯我算的跟n大一樣 可是樓上有人說會跳
→ nielhorng: 我也不記得什麼東西有跳…
推 a3230127: 沒選radix+1
推 mage594088: 最後一題AE+1
→ nielhorng: A有點忘記題目了,印象中他問某個東西是
→ nielhorng: 不是O(n),實際上是lgn就行, 但是選O(n)
→ nielhorng: 也沒錯就是了
→ mage594088: 有選Radix 就算已排好 三位數還是要
→ mage594088: run三次 不是嗎@@
→ sdfg014025xx: 覺得還是要run有選radix+1
推 jimmy1999: 最後一題我也選ae
推 TS28: while 從1+n/2到n 但最後有j*=2後必>n跳開還
→ TS28: 是我理解錯了QQ
→ jimmy1999: j不是j+n/2小於n嗎
→ nielhorng: radix我也有選 想不出什麼情況不是O(d*
推 sdfg014025xx: 沒記錯的話j不是一開始是1嗎 然後wh
→ sdfg014025xx: ile(j+n/2 <n)
→ nielhorng: (n+r))
→ nielhorng: j從1開始哦
→ nielhorng: 幹我突然想通什麼了 O(d(n+r))就不是只
推 jack1202: 我算全錯不過可能像n大說的 自己太直覺
→ nielhorng: 跟input size有關啊幹
→ jack1202: 想選tight...
→ jack1202: quadratic 到底要用+-還+@@
推 TS28: 噢對 j=1 然後wh    ile(j+n/2 <n) 最後有個
→ TS28: j*=2 2j+n不就一定>n離開while還是我看錯j*=
→ TS28: 2位置了QQ
推 mage594088: qu那個應該是+- 選項是錯的
推 Dora5566: 最後一題E選項是根號n  我選false
→ nielhorng: 還是radix sort是說d r固定的情況下tim
→ nielhorng: e complexity只跟input size有關…跟
→ nielhorng: 排序無關…媽的好像又是一題看教授心
→ nielhorng: 情來決定答案的題目
→ gaowei16: 最後E也false
推 Dora5566: 最後一題A 我算T(n)=2T(n/2)+1 =O(n) 選
→ Dora5566: false
→ nielhorng: 樓上大大這怎麼會false?
→ minicoke: 是logn
推 Dora5566: 題目不是給logn嗎
→ jack1202: 欸我跟dora一樣 所以真的沒得選
→ nielhorng: logn=O(n)是true啊
推 chieya: A 若是 16T(n/2) 不會是 O(n)吧=.=
→ gaowei16: 最後一題我有寫A
→ Dora5566: 題目不是問 會是O(logn)嗎
→ Dora5566: 不就超過了？
→ nielhorng: 那也對啊（？
→ nielhorng: 你那個式子是logn...
推 mage594088: n大+1 那是logn
→ minicoke: Log n 個1
推 jimmy1999: 你們最後一題的e都算多少qq
推 Dora5566: ？？？？？
推 Dora5566: 你們認真覺得是O(logn)……?
推 jack1202: 那式子我一直覺得是O(n)  我問題大了
→ nielhorng: 你把樹畫出來…
→ nielhorng: 每曾多少 然後樹高多少………
推 Dora5566: http://i.imgur.com/rCxDk1h.jpg
推 jack1202: 樹高lg 但每層和不是1啊
推 nielhorng: 幹對也…對不起我笨
推 mage594088: QQ
推 eric21489: DS的倒扣真d刺激....
推 Leaving: A不用乘係數2 所以是logn沒錯
→ Leaving: 他只說把problem size乘一個fraction而已
推 Dora5566: 為什麼不用乘?！
推 chieya: 我怎麼記得他說是常數倍的 T的分數式=.=
→ Leaving: 大概跟binary search的意思一樣
→ minicoke: 看一下林立宇藍色那本 我也忘了
推 ponponjerry: https://i.imgur.com/Z5n03c8.jpg
→ ponponjerry: (b)對還錯呢？還是看教授心情XD
→ minicoke: 之前我也想過這個問題
→ chieya: b不就是O(n)嗎？題目n^2怎麼會對@@
→ nielhorng: 這題目看起來不像是不用乘2…
推 jack1202: 嗯題目不記得了 當時我是乘個a如果a=1
→ jack1202: 的確gg
→ jack1202: b是給theta還O啊
推 qazsedcft402: 他的fraction是不是只0<a<1然後
→ qazsedcft402: T(n)=T(an)+T((1-a)n)+1？
→ Leaving: 我記得的題目是 在常數的時間內 將proble
→ Leaving: m size乘上一個常數的fraction
→ Leaving: 所以我覺得是T(n)=T(n/k)+c
推 Dora5566: 不是cut the problem into fraction嗎
→ Leaving: 哦哦 好像是 不過這句話我是照我上面說的
→ Leaving: 那樣解讀的
推 Dora5566: 題目好像沒說演算法的目的?
→ Dora5566: 如果是sort 就標準的D&C 然後cut從O(n)
→ Dora5566: 變常數 sort複雜度變O(n)
→ Dora5566: 不過題目給O(logn) 感覺就是想考unsorte
→ Dora5566: d array的binary search 把cut變常數 不
→ Dora5566: 考慮input也是O(log) 而且也不太可能5個
→ Dora5566: 全false 唉爛題目
→ Dora5566: 算了我要去看史萊姆了  希望昨天考的會
→ Dora5566: 正取
→ qazsedcft402: 所以答案B？？？真的爛
推 jack1202: 這樣看答案比較像B O(n) =O(n平方)
→ Dora5566: 答案"應該"是A ,  B是問theta(n^2)那題
→ Dora5566: 最多O(n)可解
推 qazsedcft402: 可是他不是寫Big Oh（n^2)嗎
推 mage594088: 樓上說好有道理TAT
推 chieya: 沒人只選D嗎？
推 we777: 可以空的化說不定交白卷還比我認真血糕= =
推 hank1321: B是問theta(n^2)吧
推 f101202: 我選ACD嘿
→ eatagary: 16題沒有A啦 反例 D大都給你們了，可以
→ eatagary: 不用吵了看不下去了。
推 sdfg014025xx: 結論：垃圾考卷
推 acen2019: 考完台大後只覺得最高的智慧真的是直覺
→ acen2019: ，運氣很重要
推 YOLOO: 沒事 台大什麼的 讓我們繼續準備成大
推 kcilao110779: 怎麼沒用112ip發文
推 ko330: range(1,8)發現只有7次,感覺是考你會不會py
→ Dora5566: 1 2 3 4 5 6 7 8
→ Dora5566: 還是range不是真的range? 沒寫過
推 misaka0120: 他又沒說是py 只是長得很像的pseudoco
→ misaka0120: de
推 ko330: 但他語法就是py阿，教授給py程式碼，卻說這
→ ko330: 是因為psudocode所以是1~8喔，感覺不太合理
推 hank1321: Pseudocode不是很常這樣表示1~8嗎...
→ eatagary: 可能只是想表達常數O(1)的概念而已，別
→ eatagary: 想太多
→ ssd860505da: 資結為啥題目那麼少啊...