两种插入排序的实现方式有性能的差异吗?

来源:2-6 换个角度实现插入排序法,作业分析

阿阳2017

2023-02-04 21:10:17

老师你好,本章讲的两种插入排序实现方式,从前往后,从后往前,它们之间有什么性能上的差异吗?如果有,和JVM实现有关系吗?

写回答

1回答

liuyubobobo

2023-02-05

没有差异。即使你在某一组数据中可以看到差异,这种差异也不是算法研究的重点,甚至是和算法一点关系都没有。


一个不管实现的有多好的插入排序算法,面对大规模的随机数据,都无法和一个尽管实现地很“烂”的快速排序或者归并排序抗衡,为什么,这就是复杂度的力量。算法领域首要关注的是“复杂度的变化”。


==========


如果你一定要关注这种“细微的实现差别”带来的性能变化:


首先,你应该学习的是各个语言相关的细节。如果一个实现比另一个实现更优,很有可能是语言背后的执行机制带来的,比如你说的 JVM 的优化的不同(JVM 的不同版本处理方式还会有区别);比如脚本语言对于某些调用会转入执行更快的被 C 优化的底层库,而对于另外一些调用这不会;比如编译器对一些 pattern 的识别(如 Java 或者 C++ 等语言都有对尾递归的优化,而 go 没有,但不排除更后续的版本就会添加这一特性,等等。)


其次,你应该学习的是和 CPU 乃至和 微指令相关的内容。因为即便是同样的代码,在不同的硬件环境下,性能也会不同。受影响的因素可能包含是否是多核环境,当前环境是否允许并发。(即便允许,你所使用的语言环境是否会自动做并发优化,也受影响。)包括 CPU 是 RISC 还是 CISC,还是某类特制芯片 ASIC(比如专门针对神经网络优化的 FPGA),全都在影响一个具体实现实际运行的性能。


所有的这些,都不是“算法”探讨的范围。


继续加油!:)

2

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2584 学习 · 1063 问题

查看课程