[理工] 107成大程設！ Aa841018 PTT批踢踢實業坊

作者: Aa841018 (andrew) 2019-01-16 11:56:00

和各位對一下答案，有幾題不是很確定……
https://i.imgur.com/ldo3ois.jpg
https://i.imgur.com/QWCMytJ.jpg
https://i.imgur.com/QCwYhGA.jpg
（7）假設前n-1已排好，只進行一次交換+從第一筆資料搜尋到第n筆

作者: ncdonalds123 (benben) 2019-01-16 12:38:00

我以為第七題是要寫nlogn

作者: rockieloser (友善大隊長) 2019-01-16 12:58:00

要nlogn吧

作者: Aa841018 (andrew) 2019-01-16 13:02:00

請問一下，為何要nlogn?

作者: dumpling1234 (dumpling) 2019-01-16 13:07:00

Comparison base 就是用 decision tree 所以最少 nlogn ?

作者: Aa841018 (andrew) 2019-01-16 13:11:00

哦！好像是欸…雖然有點無法理解（比如當真n-1被排好，怎麼會是nlogn)

作者: dumpling1234 (dumpling) 2019-01-16 13:21:00

一般都是問avg case 順帶一提 linear time sort 才是 O(n)

作者: school4303 (某爬蟲類) 2019-01-16 13:33:00

2) 為什麼不是38啊？

作者: Aa841018 (andrew) 2019-01-16 13:43:00

哦！我好像少算一個4，是38沒錯

繼續閱讀