归并排序要快速排序快

来源:3-6 随机化快速排序法

慕虎9694855

2019-02-18

老师,为什么在我的机子上测试,完全随机的数组,归并排序比快速排序还快

写回答

1回答

liuyubobobo

2019-02-18

如果使用VS,请改用release进行测试?


相信即使快,也不会快太多,即使毫秒的区别,不用太计较。因为在现代计算机上,算法的运行速度不完全是逻辑相关的,和你当前的操作系统状态,编译器优化等等因素都相关。些许的测试差距是很正常的。我个人不是特别建议对于同复杂度的算法之间的性能过于纠结。关键在于,不论是归并排序,还是快速排序,都是O(nlogn)复杂度的算法,他们比我们之前所介绍的O(n^2)级别的算法都快,而且差距很大,这些不通复杂度算法之间“本质的差异”,是我们学习算法需要掌握的关键!:)


继续加油!:)

1
1
慕虎9694855
非常感谢,问题没有具体描述就得到这么耐心的回答,老师辛苦了了
2019-02-18
共1条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程