算法复杂度分析如何进行？

本文共计2905个文字，预计阅读时间需要12分钟。

对算法做复杂度分析是学习算法必备的知识点。掌握如何对算法进行复杂度分析，有助于在优化算法时如虎添翼。简介如下：复杂度分析是对已知代码执行效率的方法分析，它帮助我们评估算法在不同输入规模下的性能。

对一个算法做复杂度分析是学习算法必备的知识点，当掌握了如何对一个算法做复杂度分析，在优化算法方面将会如虎添翼。 简介

复杂度分析法是对已知的代码进行效率分析的方法，与之相对的是使用实际数据运行代码的事后统计法。

复杂度分析法和事后统计法各有优劣，与复杂度分析法进行比较，事后统计法会有以下局限性：

• 测试结果非常依赖测试环境。硬件的不同会对测试结果有比较大的影响，比如不同处理器的执行时间会不一样
• 测试结果受数据的影响很大。对同一个排序算法，待排序数据的有序度会影响算法的执行时间；对于小规模的数据排序，插入排序的效率会比快速排序的效率更高

相比事后统计法，复杂度分析法更能表示一个算法在各个维度的综合性能。

复杂度

复杂度分为时间复杂度和空间复杂度，但是它们并不能准确地表示算法的执行时间和存储空间。

时间复杂度表示的是执行时间与数据规模之间的增长关系；空间复杂度表示的是存储空间与数据规模之间的增长关系。

复杂度表示法

常用的复杂度表示法就是大 O 复杂度表示法，时间复杂度和空间复杂度都能运用这个概念，在概念上可以进行类比。

在实际使用中，空间复杂度会比时间复杂度更简单些，下面只对时间复杂度做解析。