时间复杂度分析--技巧

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系

• 只关注循环执行次数最多的一段代码

  ​ 我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了

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

  ​ 这里我要再强调一下，即便这段代码循环 10000 次、100000 次，==只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间==。当 n 无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。

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

  • 忽略掉f的cal 是O(n),f是O(n)
  • 加上f的cal是O(n^2^)=O(n*n)

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

常见复杂度

• 非多项式阶
  • 随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n)（指数阶）、O(n!)（阶乘阶）

• O(1)
  • 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)

 int i = 8;
 int j = 6;
 int sum = i + j;

• O(logn)
  • 
  • 所以说，共执行了log~2~n次
  • 时间复杂度为O(log~2~n)，即O(logn)

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

• O(nlogn)

  • 如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了
  • 而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

• O(m+n)

  • 事前不知道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;
  }
  

最好、最坏、平均、均摊

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

• 最好情况

  • 当在数组的第一个位置时，时间复杂度为O(1)

• 最坏情况

  • 当在数组的最后一个位置或者不存在时，时间复杂度为O(n)

• 平均情况

  ​ 我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便你理解，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)

  

  ​ 这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。引入概率之后，前面那段代码的加权平均值为 (3n+1)/4。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。

• 均摊情况

  • 当数组有空闲时，插入一个数据——O(1)
  • 当数组满时，对数组进行求和，将sum放入a[0],继续插入数据---O(n)

  
   // array表示一个长度为n的数组
   // 代码中的array.length就等于n
   int[] array = new int[n];
   int count = 0;
   
   void insert(int val) {
      if (count == array.length) {
         int sum = 0;
         for (int i = 0; i < array.length; ++i) {
            sum = sum + array[i];
         }
         array[0] = sum;
         count = 1;
      }
  
      array[count] = val;
      ++count;
   }
  

  ​ 对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

  我们引入了一种更加简单的分析方法：==摊还分析法==，通过摊还分析得到的时间复杂度我们起了一个名字，叫==均摊时间复杂度==。

  ​ 每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。

  对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

空间复杂度分析

• 第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)

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