算法的复杂度分析

如果想要分析一个程序的性能，你可以尝试将程序运行，然后收集它的运行数据，就可以得到程序运行所需要的时间和内存。我们将这种分析方法称为事后统计法。
事后统计法是非常朴素的分析方法，但是也两点问题：

1. 程序的运行需要依赖硬件环境，比如同一个程序在两台性能不一的电脑上的表现是不同的。
2. 程序运行时间往往收到数据规模的影响，例如在排序算法中，快排是最优秀的算法，如果只使用几个数据进行排序，可能它的表现还不如冒泡排序，但是当使用上万个数据进行排序的时候，他们的性能差异就会显现。（这种差异可能不是十倍，而是百倍千倍）

由于这些问题，我们一般使用复杂度分析的方法分析一个算法的性能，这就是大O复杂度表示法

大O复杂度表示法：

大O时间复杂度表示法：

抛去计算机底层的影响，我们可以使用大O时间复杂度表示法来表示代码执行时间随数据规模增长的变化趋势，简称时间复杂度。
分析时间复杂度有三个比较使用的方法：

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

敲黑板：循环 和 最多
下面有一段代码：

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

上面的代码中，2、3行代码都是常量级的执行时间，和n无关，在复杂度分析中可以忽略。循环执行次数最多代码是 for 循环中的代码，它被执行了 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_2部分的代码的复杂度为O(n)，sum_3代码的复杂度为O(n²），根据加法法则，cal函数的复杂度为O(n²)

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

看下面的代码：

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

可以看到，在 cal 的 for 循环中嵌套了 f 函数。第一部分的 for 循环贡献了 n 的复杂度，而 f 函数也贡献了 n 的复杂度，根据乘法法则，cal的复杂度为 O(n²)。

大O空间复杂度表示法：

空间复杂度的定义和时间复杂度类似：表示算法需要的存储空间与数据规模之间的增长关系。
你只需要分析在算法中申请的存储空间即可，常见的空间复杂度有：O(1),O(n),O(n²)

最好、最坏、平均、均摊 时间复杂度

同一个算法在给定不同数据的情况下性能可能会出现很大的差异，例如：如果一个数组已经基本有序，那么使用快速排序则有O(n²)的时间复杂度，而最好的情况下复杂度为O(nlogn)。
基于上面的情况，我们引入了各种复杂度的度量：

• 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
• 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
• 平均时间复杂度：根据概率论的理论，平均时间复杂度的值为代码执行的加权平均值，也就是它的期望值。所以你也可以将之称为加权平均时间复杂度。
• 均摊时间复杂度：你可以将其理解为一种特殊的平均时间复杂度：
  先来看下面一段代码：

 // 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函数向数组array中添加数据，在没有到达n，只需要O(1)的时间复杂度，但是如果放入第n个数据，复杂度就会变为O(n)，这就出现了在执行过程中操作的复杂度不同的情况，针对这种情况，我摘取了下面一段话：

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

注意：只有在最好、最坏、平均时间复杂度在量级上存在差异的时候，区分它们才有意义。

以上就是对算法的复杂度分析的全部内容。