总结自：数据结构与算法之美

为什么需要复杂度分析

事后统计法有非常大的局限性。

1.测试结果非常依赖测试环境

硬件的不同对测试结果有很大的影响。

2.测试结果受数据规模的影响很大

排序算法依赖待排数据的有序度。此外，测试数据规模太小，测试结果可能无法真实地反映算法的性能。

大 O 复杂度表示法

【示例】求1，2，3……n的累加和。

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

解题思路：

假设每行代码执行时间都一样，为unit_time

第4 5行都运行了 n 遍，所以需要 2n*unit_time的执行时间。

所以复杂度为 O(n)。

结论：

尽管不知道unit_time的具体值，但通过推到，可以得到一个规律：所有代码的执行时间T(n)与每行代码的执行次数f(n)成正比

总结为一个公式：

具体解释：
T(n)表示代码执行的时间；
n表示数据规模的大小
f(n)表示每行代码执行的次数总和


所以，第一个例子中 T(n) = O(2n+2)。而时间复杂度实际上表示代码执行时间随数据规模增长的变化趋势。这里其实引用的是极限的思想，当n趋近于无限大时，常量、低阶、系数对数据的影响无限趋近于0，所以省略这部分。得到最终的时间复杂度。

时间复杂度分析

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

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

思路分析
代码分为3部分，分别是求 sum_1, sum_2, sum_3。分别分析三段的时间复杂度。再取一个量级最大的作为整个代码的时间复杂度。

• sum_1：代码总共执行100次，属于常量级，可以忽略。
• sum_2: O(n)
• sum_3: O(n^2)

那么整段代码的时间复杂度就是 O(n^2)

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

思路分析
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n)).
回到代码上，f()方法的时间复杂度为 O(n)；4~6行代码的时间复杂度为 O(n)。那么整个cal()的时间复杂度为 O(n^2)

几种常见的时间复杂度

基本概念：
粗略的将复杂度量级分为多项式量级和非多项式量级。非多项式量级只有两个：O(2^n)和O(n!)

1.O(1)

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

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

2.O(logn)、O(nlogn)

【示例】

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

思路分析
变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。
变量 i 的取值就是一个等比数列

如图，通过 2^x=n 求解 x。得出 x = log₂ⁿ

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。
比如，log₃ⁿ = log₃² * log₂ⁿ 而 log₃² 是一个常量，因此以几为底无所谓。

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

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

根据乘法法则，T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

【示例】

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

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

时间、空间复杂度分析

原文：https://www.cnblogs.com/zzfan/p/14490261.html