代码写出来就是交由机器去执行的,不同的人,可能会写出不同的代码。评价一个人的代码,不仅要从代码的可读性。还得从代码的扩展性,封装性等去看待。当然,还有一点,那就是代码执行的效率。
那么,如何去评估一段代码的执行效率呢?今天的这篇文章,将会是一个开端。
事后统计法
通过统计、监控,就能得到算法执行的时间和占用的内存大小。
缺点:
- 测试结果非常依赖测试环境
- 测试结果受数据规模的影响很大
大 O 复杂度表示法
算法的执行效率,粗略地讲,就是算法代码执行的时间。
1 | T(n)=O(f(n)) |
T(n) = O(2n 2 +2n+3) , 我们只需要记录一个最大量级就可以 了,如果用大 O 表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n) = O(n 2 ) 。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则:总复杂度等于量级最大的那段代码的复杂度
- 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
1 | int cal(int n) { |
我们单独看 cal() 函数。假设 f() 只是一个普通的操作,那第 4 ~ 6 行的时间复杂度就是, T1(n) = O(n) 。但 f() 函数本身不是一个简单的操作,它的时间复杂度是 T2(n) = O(n),所以,整个cal()函数的时间复杂度就是,T(n) = T1(n) * T2(n) = O(n*n) = O(n 2 )。
常见时间复杂度

- O(logn)、O(nlogn)
1 | i=1; |
- O(m+n)、O(m*n)
参考链接