博客

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

从cpu的角度来看，每一行代码都做着相同的工作，读数据-计算-写数据，尽管每行代码对应的cpu的执行个数，执行时间都不一样，但是我们还是粗略的估算，所以假设每一行代码都执行了base_time的时间，在这个假设基础上，这段代码执行了多少时间呢

第2和3行分别执行了一次，共用了2

base_time的时间，4和5行分别执行了n次，用了2n

base_time的时间，我么可以计算出，代码运行的总时间是（2n+2）*base_time,

可以看出所有代码的执行总时间T(n)和每行代码的执行的次数成正比。


按照这个思路，我们来分析一下，下面的代码

1 int cal(int n) {
2  int sum = 0;
3   int i = 1;
4   int j = 1;
5  for (; i <= n; ++i) {
6    j = 1;
7   for (; j <= n; ++j) {
8     sum = sum +  i * j;
9     }
10   }
11 }

我们看出，2，3，4行分别运行一次，5，6行分别运行n次，7，8行分别运行n

²

次，这段代码一共运行 3+2n+2n

²

次,所以总代码的运行时间T(n)=（3+2n+2n

²

）*base_time;

我们虽然不知道base_time的具体数值，但是通过这俩段代码的推断过程，我们知道了一个规律，

所有代码的总执行时间T(n)与每行代码执行次数n成正比


我们可以把规律总结成一个公式

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

T(n):表示执行的总时间

n ：表示数据规模的大小

f(n) ：表示代码执行的总次数

O：表示T(n)和f(n)成正比

所以第一段代码我们可以表为 T(n)=O(2n+2)，第二段代码可以表示为T(n)=O(2

²

+2n+2)这就是

大O复杂度表示法

，大O时间复杂度并不代表代码的真正执行时间，而是

代码执行时间随数据规模增长的变化趋势

所以也叫

渐进时间复杂度

，简称

时间复杂度


当n很大时，我们当做1000，10000甚至更大，这个是时候低阶，常量，系数并不左右增长趋势，都可以忽略，只需要记一个最大量级就可以了，所以上面两端代码复杂度可以改为 T(n)=O(n),T(n)=O(n

²

)

时间复杂度分析

上面介绍了大O表示法，下面我们来看一下如何分析时间复杂度

1 只关注循环次数最多的那段代码

我刚才说了，大 O 这种复杂度表示方法只是表示一种变化趋势。低阶，常量，系数并不左右增长趋势，都可以忽略，只需要记一个最大量级就可以了，所以

我们在分析一段代码，或一个算法的复杂度的时候，只需要关注循环次数最多的那一段代码就可以了

。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度

我们来看一个例子

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

我们可以看到2，3行常量级的执行时间，和n的趋势无关可以忽略，循环最多的是4，5行代码，这块我们要重点分析，这两行代码被执行了n次，所以时间复杂度就是O(n)

2 加法法则，总复杂度等于量级最大的那段代码的复杂度

我们来看一段代码

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

这段代码有三个部分 分别是 sum_1 ,sum_2,sum_3,我们分析一下这三部分的时间复杂度，第一部分循环了100次，是一个常量级的，这里需要强调一下，只要是一个确定的数，不管是100还是1000000，都认为是一个常量级的数字，当n无限大的时候都可以忽略，第二段和第三段的时间复杂度是O（n）和O(n

²

),综合这三段复杂度，我们只取最大量级的，所以整段复杂度就是O(n

²

),也就是说，

总的时间复杂度就是最大量级的时间复杂度

3 乘法法则，嵌套代码的复杂度，等于嵌套内外代码复杂度的乘积

例如上方sum_3 就是内外的乘积 n*n=n

²

几种常见复杂度的案例分析

1 常量阶O(1)

常量阶并不是指的是一行代码,只要代码的执行时间不随n的增大而增大，这样的代码时间，我们就称作O(1)，

一般情况下只要代码中不存在，循环，递归语句，即使是成千上万行代码也是O(1)；

2 对数阶O(logn)和O(nlogn)

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

我们来算一下这个的时间复杂度

我们按照上面的方法去分析，我们可以看出第三行是循环次数最多的地方，所以我们计算出第三行的执行次数就可以算出时间复杂度

从代码上可以看出i从1开始，每次乘以2，当大于n时循环结束，其实i的取值是一个等比数列，如下



所以我么只要知道x是多少，就知道了执行的次数，那么求解2

^x

=n,x=㏒❷n，时间复杂度就是O(log2n)；



实际上不管以2为底，害死以3为底，以10为底，都统一计作logn

3 O(m+n)，O(m*n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

我们可以看到上方分为2个规模，m和n，由于不能判断出m和n的规模大小，所以我们在计算的时候就不能简单利用加法法则，忽略掉一个，所以上方的复杂度就是O（m+n）

最好时间复杂度和最坏时间复杂度

/**
     * @param arr
     * @param n   表示array的长度
     * @param x   表示查找的数字
     * @return x 的下标
     */
    private int find(int[] arr, int n, int x) {
        int postion = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] == x) {
                postion = i;
                break;
            }
        }
        return postion;
    }

上面这段代码的时间复杂度是多少呢，是O(n)吗？

我们分析一下，当x在数组第一个的时候，我们就不需要遍历剩下的（n-1）个，那么时间复杂度就是O(1)，假如x不存在数组中，那么就需要遍历n次，那么时间复杂度就是O(n)，在不同的情况下时间复杂度不同，所以我们要引入，

最好时间复杂度和最坏时间复杂度

最好时间复杂度

：指的是，在最理想的情况下，这段代码执行的时间复杂度，例如上面x存在数组第一个位置

最坏时间复杂度

：指的是，在最糟糕的情况下，这段代码执行的时间，例如上面x不存在数组中

空间复杂度

空间复杂度全称，渐进空间复杂度，

表示算法的储存空间和数据规模之间的关系

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

我们看下这段代码

第二行申请了一个空间储存i，是常量级的可以忽略，第三行申请了n个空间，除此之外，其他代码并没有占用太多空间，所以这段代码的空间复杂度是O(n)

我们常见的空间复杂度是O(1)，O(n)，O(n

²

),空间复杂度比较简单，掌握这些就可以了