2021河北大学暑期程序设计训练每日知识分享-day01
每日分享——复杂度分析
在刷算法题时，经常遇到超时或者内存超限的提示，这与算法本身的时间复杂度和空间复杂度有关，其中时间复杂度是评判程序运行效率的重要指标，也是我们重点关注的部分。那么如何进行复杂度分析呢？
1.复杂度分析：
数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。因此从执行时间和占用空间两个维度来评估数据结构和算法的性能。
复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有（大 O 复杂度表示法）：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。
2.复杂度分析法则
- 单段代码看高频：比如循环。
- 多段代码取最大（加法法则）：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
- 嵌套代码求乘积（乘法法则）：比如递归、多重循环等
- 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
3.常用的复杂度级别
- 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2^)（平方阶）、O(n^3^)（立方阶）
- 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n^)（指数阶）、O(n!)（阶乘阶）
4.补充
- 大多数oj 不开编译优化的话1000ms可以跑1e8～5e8的数据
