推 naive131: 2我選3，他只是算AB兩個sorted list合併會比較幾次，wor01/21 14:44
→ naive131: st case就是一下A大一下B大01/21 14:44
我一題一題慢慢回
二應該是要選3沒錯，但認真寫的話好像應該是omega(min(n,m))，發生在其中一邊最大的
比另一邊最小的小
→ naive131: 4我選1245，2的話對吧？如果最大key還有child代表那孩子01/21 14:44
→ naive131: 比它大，5的話第三小的值高度不會大於2（root height =01/21 14:44
→ naive131: 0）01/21 14:44
→ naive131: 5我選1245，3的話他的分析不夠tight應該O(n)就可以01/21 15:02
其實這樣我會不知道3要不要選欸
他沒有說要做到最tight，所以單論敘述的話我覺得3沒有錯
→ naive131: 6我覺得1錯，既然我已經隨機挑pivot了那我原本array有沒01/21 15:02
→ naive131: 有sorted就不影響我比較次數了吧？01/21 15:02
我以為1是說input是sort過的，所以就是worst case的quick sort,所以這邊的意思是指
因為sort過所以不用再比較的意思嗎@@
推 naive131: 8-5 theta應該是錯的？如果我隨機從大挑到小只需要n就可01/21 15:14
→ naive131: 可了01/21 15:14
對
這個我大意了= =theta太緊了
→ naive131: 9-2 BST高度是O(n)吧01/21 15:19
對哦，skewed tree對ㄅ
→ naive131: 13-a 就check是否連通無cycle這樣就好了唄01/21 15:27
→ naive131: 然後12題他說選si, sj然後我的收入是li+lj 可是l是dista 01/21 15:29
→ naive131: nce我覺得怪怪的01/21 15:29
對我也看不懂這在寫啥
推 try66889: 想請問n大5的1為什麼會對呢? 我的想法是當選到最小的數01/21 21:19
→ try66889: (ROOT)時可以O(1)比較出來~01/21 21:19
→ try66889: 1我覺得應該要改成O(n)，不知道有沒有沒考慮到的地方01/21 21:20
→ naive131: 回樓上，最少比較次數就是他本來就已經是min-heap，可是01/22 08:33
→ naive131: 不會因為他是從最後一個父點check發現說我root比兩個子01/22 08:33
→ naive131: 點小就認定它是min-heap，還是要從最後一個父點檢查，每01/22 08:33
→ naive131: 次檢查（best case）只比兩次（一次看兩個孩子誰小一次01/22 08:33
→ naive131: 看root跟這個孩子誰小） 所以全部差不多是n次01/22 08:33
→ try66889: 感謝n大~ 沒考慮要從最後一個父點開始比較> < 了解惹OWO01/22 09:46
推 summit: 1. O(n^3)應該同時屬於4、5吧01/22 16:21
...那第一題變成要選345第二題要變選12了，這樣選不下手了
推 summit: 2.是問 min 比較次數欸01/22 16:33
他給的演算法
如果A是[1,2,3],B是[4,5,6,7]，則A中三個全部拿出去後A變空，然後直接放入B，這樣就
變成只要比三次就好
這樣是最min了吧？但這樣問題就是你不知道是A比較小還是B比較小@@
有夠模糊
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 17:42:55
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 17:59:31
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 18:01:05
→ naive131: 我回6就好 其它就比較有爭議哈哈哈01/22 19:30
→ naive131: 我的理解是它的input原本就排好了沒錯，可是我是隨機挑p01/22 19:30
→ naive131: ivot呀我也有可能挑到可以切成兩塊相等大小的所以他說al01/22 19:30
→ naive131: ways be maximized是錯的，我的想法啦 01/22 19:30
我的想法是
今天input = [1,2,3,4,5,6,7]
pivot = 4
那兩邊[1,2,3]還是要比n(n-1)/2次這樣
所以怎麼切都還是有一邊要比到O(n^2)
怎麼感覺這份考卷這麼多極端
唉...
※ 編輯: joywilliamjo (114.136.197.106 臺灣), 01/22/2021 20:19:35
→ naive131: 沒呀Quick sort的best case怎麼會比到n^2次，他是每一輪01/22 22:39
→ naive131: pivot去跟剩下n-1個數比較再分成兩個集合 01/22 22:39
那n大你第六題選哪個啊
4、5我不太會算不知道對不對@@
上面
至於第5題的3選項
我越看越像top down的寫法欸
因為是先從n/2到n先做完，再做剩下的，再組合起來
比較不像是bottom up，全部放完再排
所以是O(nlogn)吧
不知道你怎麼看
※ 編輯: joywilliamjo (223.136.28.84 臺灣), 01/23/2021 08:36:27
→ naive131: 6我後面兩個選項沒算 01/23 10:06
→ naive131: 5你看最後三行有說最後一個父點做完會往前做heapify 01/23 10:06
→ naive131: 另外7的4應該是錯的，我的first pointer points to top01/23 10:06
→ naive131: element of the stack所以你給我一個指向最下面的沒幫助01/23 10:06
推 booowei1203: 想問一下第9題的第5個選項哪裡錯了（想說4有選的話，01/23 15:00
→ booowei1203: 5應該也要選）01/23 15:00
我感覺當下寫的時候沒想仔細，事後想想兩個好像都得選...
9的5是說把y的左子樹接到y的parent,然後y取代z對吧
推 booowei1203: 還有第10題的第5個選項我有選，想問一下你的想法～01/23 15:11
※ 編輯: joywilliamjo (223.136.28.84 臺灣), 01/23/2021 19:00:45
推 jackycheny: 第二題沒給n,m誰小不知道怎選 01/23 21:13
推 jackycheny: 答案只能選3 01/23 21:17
推 aa871220: 第6題完全就是拿clrs randomized quick sort出來考啊 01/24 23:54
→ aa871220: 我寫cde 關於d e這兩個選項clrs裡面都有證哦 01/24 23:54
推 jordan1997: 這份不是有說沒有正確答案的話可以填none嗎，所以第三 01/25 10:44
→ jordan1997: 題我覺得是none 01/25 10:44
推 jordan1997: 6的4，5選項在這邊 ，但是5是錯的吧，ki不一定剛好等 01/25 11:47
→ aa871220: 回樓上 ki不會剛好等於i沒錯 01/25 11:51
→ aa871220: 但他是permutations of <1,2,...,n> 01/25 11:51
→ aa871220: 所以這樣加總起來所有條件都會被考慮到啊 01/25 11:51
推 jordan1997: 喔喔沒看到那句，那這樣5應該是對的 01/25 12:00
推 nyms: 我以為123題都是複選？題目沒特別要求tight不是對的就要選嗎 01/25 17:04
→ nyms: …？ 01/25 17:04
→ jordan1997: mgur.com/rIyNIRU.jpg 01/25 22:07
