事后统计法
事后统计法是指把需要的统计代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小。这种统计方法非常有局限性。
事后统计法局限性
- 测试结果非常依赖测试环境
- 测试结果受数据规模的影响很大
大O复杂度表示法
所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
T(n) = O(f(n))
- T(n) 它表示代码执行的时间;
- n 表示数据规模的大小;
- f(n) 表示每行代码执行的次数总和。因为这是一个公式,所以用 f(n) 来表示。
- 公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
时间复杂度分析
在分析时间复杂度的时候比较实用的方法有下面几个:
只关注循环执行次数最多的一段代码
加法法则:总复杂度等于量级最大的那段代码的复杂度
乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几种常见的时间复杂度
常见的时间复杂度从低阶到高阶分别为:
- 常量阶:O(1)
- 对数阶:O(logn)
- 线性阶:O(n)
- 线性对数阶:O(nlogn)
- 平方阶:O($n^2$)
- 指数阶:O($2^n$)
- 阶乘阶:O(n!)
最好、最坏情况时间复杂度
下面看如下代码:
1 |
|
- 最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度,即上面循环只遍历一次就得到结果。
- 最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度,即上面循环把整个数组都遍历一遍
平均情况时间复杂度
- 平均情况时间复杂度分析,可以先算出该段代码的加权平均值之后再来分析。
均摊时间复杂度
- 出现O(1)的次数远大于出现O(n)出现的次数,那么平均平摊时间复杂度就是O(1)
空间复杂度
空间复杂度分析可以参考时间复杂度分析。