重新整理一下
1. 有爭議,最tight是3,但是因為是多選題,也沒有說最tight,所以45不知道該不該選
2. 有爭議,沒有給最小的min(n,m)導致這題唯一可能的解是3,也可能是none
3. none,是小o,sorting有機會等於nlgn
4. 1245
5. 1245,3一樣是tight不tight不知道該不該選= =
6. 345,感謝版友提供,clrs有類似題
7. 13
8. 12吧, 4應該是常數,從小到大進去就不一定會是i了,5太緊
9. 145, 2會太緊,skewed的狀況會變O(n),3也是
10. 45
11. merge sort變形,O(1.5n)
12. 題目 total revenue = l_i+l_j這一段看不懂
13. a) 版友提供,測是否連通無cycle
14. 我自己的圖是長這樣啦,拜託錯了告訴我QQ
感謝版友
a是TRUE
b是False
https://i.imgur.com/gBqcmPz.jpg
證明用矛盾證法
15. vertex cover reduce to set cover
前三題最簡單卻也最像猜猜樂QQ