简介

执行效率是算法一个非常重要的考量指标。衡量编算法代码的执行效率:时间、空间复杂度。

大 O 复杂度表示法

1 int cal(int n) {
2   int sum=0;
3   int i=1;
4   for(;i<=n;++i){
5      sum=sum+i; 
6   }
7   return sum; 
8 }

假设每行代码执行的时间都一样,为 unit_time。在这个假设的基础之上,这段代码的总执行时 间是多少呢? 第 2、3 行代码分别需要 1 个 unit_time 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2n*unit_time 的执行时间,所以这段代码总的执行时间就是 (2n+2)*unit_time。可以看出来, 所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

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
    }
  }
}

执行时间为T(n) = (2 *n * n + 2n + 3)*unit_time

但是通过这两段代码执行时间的推导过程,我们可以得到 一个非常重要的规律,那就是,所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

T(n) = O( f(n) )

T(n) 我们已经讲过了,它表示代码执行的时间;n 表示数 据规模的大小;f(n) 表示每行代码执行的次数总和。因为这是一个公式,所以用 f(n) 来表示。 公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

当 n 很大时,你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左 右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了,如果用大 O 表示法表 示刚讲的那两段代码的时间复杂度,就可以记为:T(n) = O(n); T(n) = O(n^2)。

时间复杂度分析

  1. 只关注循环次数最多的一次代码
  2. 加法法则: 总复杂度等于量级最大的那段代码的复杂度。(如顺序执行的代码,所以是一个常量的执行时间,跟 n 的规模无关。)
  3. 乘法法则: 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度实例分析

  1. 常量阶: O(1)
  2. 对数阶: O(logn)
  3. 线性阶: O(n)
  4. 线性对数阶: O(nlogn)
  5. 平方阶: O(n^2)O(n^3) ….
  6. 指数阶: O(2^n)
  7. 阶乘阶: O(n!)

其实就是统计执行次数

实际举例:

1). 常量阶: O(1) 顺序执行代码的复杂度就是O(1),

O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一 行代码。比如这段代码,即便有 3 行,它的时间复杂度也是 O(1),而不是 O(3)。

2). O(logn)、O(nlogn) 对数阶时间复杂度非常常见,同时也是最难分析的一种时间复杂度。

i=1; 
while(i <= n) { 
  i=i*2;
}

1*2*2*2*2..直到>n停止,因此需要 2^p > n , p为执行次数, 可得知p的值为以2为底n的对数, 即p = log2 n

实际上,不管是以 2 为底、以 3 为底,还是以 10 为底,我们可以把所有对数阶的时间复杂度 都记为 O(logn)。为什么呢?

如果你理解了我前面讲的 O(logn),那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则 吗?如果一段代码的时间复杂度是 O(logn),我们循环执行 n 遍,时间复杂度就是 O(nlogn) 了。而且,O(nlogn) 也是一种非常常见的算法时间复杂度。比如,归并排序、快速排序的时间 复杂度都是 O(nlogn)。