大O表示法

◼ 一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度
◼ 大O表示法指出了最糟情况下的运行时间

◼ 忽略常数、系数、低阶
9 >> O(1)
2n + 3 >> O(n)
n2 + 2n + 6 >> O(n2)
4n3 + 3n2 + 22n + 100 >> O(n3)
写法上，n3 等价于 n^3

◼ 注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率

对数阶的细节

◼ 对数阶一般省略底数
log2n = log29 ∗ log9n
◼ 所以 log2n 、log9n 统称为 logn

常见的复杂度

◼ O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
◼ 可以借助函数生成工具对比复杂度的大小
https://zh.numberempire.com/graphingcalculator.php

数据规模较小时

数据规模较大时