01.复杂度分析

1.why

数据结构与算法本质是"快"与“省”，即运行更快，存储空间更省。

2.What

时间复杂度

image.png

n:表示数据规模

T(n):代码的执行时间；

f(n):每行代码执行的次数总和；

O:表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

大O时间复杂度表示法:并不具体表示代码真正执行的时间，而是表示代码执行时间随数据规模增长的变化趋势；

---

空间复杂度

表示数据规模的增长与存储空间的关系，常见的有O(1),O(n),O(n²)

3.How

时间复杂度分析：

• 只关注循环执行次数最多的代码；
• 加法原则:总复杂度等于量级最高的那段代码的复杂度；
• 乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；

时间复杂度实例：

image.png

复杂度量级分为多项式量级和非多项式量级。

非多项式量级为指数阶和阶乘阶，复杂度会随着数据规模的增加而急剧增加，一般不考虑。

image.png

时间复杂度细分:

• 最好情况时间复杂度
• 最坏情况时间复杂度
• 平均情况时间复杂度，又称加权平均时间复杂度或者期望时间复杂度
• 均摊时间复杂度，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。