本篇博客是学习过程中的笔记总结和个人思考,学习原文见引用
- 引用
- 03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
- 为什么需要复杂度分析
- 大 O 复杂度表示法
引用
- 点击跳转 → 《极客时间:数据结构与算法之美》
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
数据结构和算法解决的是:如果在计算机内存更快时间、更省空间的解决问题。
从执行时间和占用空间两个维度来评估数据结构和算法的性能。
用时间复杂度和空间复杂度来描述性能,二者统称为复杂度。
复杂度描述的是算法执行时间(或占用内存空间)与数据规模的的增长关系。
复杂度分析不依赖于执行环境,成本低,效率高,易操作,指导性强。
掌握复杂度分析,编写出性能更优的代码。
算法的执行时间与每行代码的执行次数成正比,T(n) = O(f(n)),T(n)表示算法执行总时间,f(n) 表示每行代码的执行总次数,n表示数据规模。
时间复杂度(空间复杂度)描述算法的执行时间(额外占用空间)随数据规模增长变化的趋势。常量阶、低阶、系数对增长趋势不产生决定性影响,分析是可以忽略。
时间复杂度:单段代码看高频率(循环),多段代码取最大(单循环和多重循环取多重循环),嵌套代码求乘积(递归,多重新循环等),多个规模求加法(两个参数控制两个循环次数,取二者时间复杂度相加)。
复杂度级别:
多项式比例增长:O(1),O(logn),O(n),O(nlogn),O(n ^ 2),O(n ^ 3)。
非多项式暴增:O(2^n),O(n!)。
多练习分析时间复杂度。
遇到一个新的思路:数据结构横向解决运算时间快和空间省的问题,纵向解决架构和抽象的问题(数据结构和算法的泛型)。
所有数据结构和算法都会涉及时间复杂度和空间复杂度的问题。
为什么需要复杂度分析
先进行良好的设计,然后根据设计进行分析改进,最后再去执行。
事后统计法存在局限性:
- 测试结果依赖环境。
- 测试结果受数据规模影响很大。
举例:计算乘法。测试环境其中影响非常大的就是硬件,对于不同的指令集系统就会对结果有影响,乘法
通过时间复杂度、空间复杂度分析,进行粗略计算算法的执行效率。
很多算法都是适配固定的数据结构和应用场景,没有任何场景都是适用的完美算法。
大 O 复杂度表示法
算法的执行效率:算法代码执行时间越短,效率越高。
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
从CPU的角度看,每一个语句都执行着类似的操作:读数据-运算-写数据。
假设每个语句的执行时间都是一样的为unit_time。
第2行执行 1 次。
第3行执行 1 次。
第4行 i <= n 执行 n + 1次,++i 执行 n 次。
第5行执行了 n 次。
第7行执行 1 次。
这段代码总的执行时间:(3n + 4) * unit_time。
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
第2行执行 1 次。
第3行执行 1 次。
第4行执行 1 次。
第5行 i <= n 执行 n + 1次,++i 执行 n 次。
第6行执行 n 次。
第7行 j <= n 执行 n ^ 2 + 1次,++j 执行 n ^ 2 次。
第8行 n ^ 2 次。
这段代码总的执行时间:(3n ^ 2 + 3n + 5) * unit_time。
所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。