如何评判一个算法的好坏？
- 时间复杂度：估算程序指令的执行次数（执行时间）
- 空间复杂度：估算所需占用的存储空间
大O表示法（Big O）
一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度
-
一般忽略常数、系数、低阶
- 9 >> O(1)
- 2n+3 >> O(n)
- n^2 + 2n + 6 >> O(n^2)
- 4n^3 + 3n^2 + 22n + 100 >> O(n^3)
-
对数阶一般省略底数
已知：log2(n) = log2(9) * log9(n)
因此：log2(n) 、log9(n) 统称为 logn -
大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
常见的复杂度
Snip20200912_1.png
-
复杂度排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) -
复杂度大小对比工具
可以借助函数生成工具对比复杂度的大小
https://zh.numberempire.com/graphingcalculator.php
复杂度的其他概念
- 最好、最坏复杂度
- 平均复杂度
- 均摊复杂度
- 复杂度震荡
网友评论