Algo Notes: Something Notes

leetcode push front数据结构与算法之美笔记

时间复杂度分析

什么是复杂度分析？数据结构和算法解决的是“如何让计算机更快时间，更省空间的解决问题”。因此需要从执行时间和占用空间两个概念来描述性能问题，二者统称为“复杂度”。分别用时间复杂度和空间复杂度两个概念来描述性能问题。

复杂度描述的是算法执行时间（或者用空间）与数据规模之间的增长关系。

为什么要进行复杂度分析？与性能测试相比，复杂度分析具有：

• 不依赖执行环境

• 成本低

• 效率高

• 易操作

• 指导性强

如何进行复杂度分析？

使用大O表示法，算法执行时间与每行代码执行的次数成正比，形式为T(n) = O(f(n))，其中T(n)表示算法执行总时间，f(n)表示每行代码执行的总次数，n表示数据规模。

特点

以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，常量阶、低阶以及系数实际上对这种增长趋势影响较小，所以在时间复杂度分析时可忽略这些项。

复杂度分析法则

• 单段代码看高频：循环多段