1.why
数据结构与算法本质是"快"与“省”，即运行更快，存储空间更省。
2.What
时间复杂度
image.png
n:表示数据规模
T(n):代码的执行时间；
f(n):每行代码执行的次数总和；
O:表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
大O时间复杂度表示法:并不具体表示代码真正执行的时间，而是表示代码执行时间随数据规模增长的变化趋势；
空间复杂度
表示数据规模的增长与存储空间的关系，常见的有O(1),O(n),O(n2)
3.How
时间复杂度分析：
- 只关注循环执行次数最多的代码；
- 加法原则:总复杂度等于量级最高的那段代码的复杂度；
- 乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；
时间复杂度实例：
image.png
复杂度量级分为多项式量级和非多项式量级。
非多项式量级为指数阶和阶乘阶，复杂度会随着数据规模的增加而急剧增加，一般不考虑。
image.png
时间复杂度细分:
- 最好情况时间复杂度
- 最坏情况时间复杂度
- 平均情况时间复杂度，又称加权平均时间复杂度或者期望时间复杂度
- 均摊时间复杂度，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
网友评论