[理工] 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没错

继续阅读