思维导图

脑图上有个人对时间复杂度的全部理论理解，野路子，不喜勿喷；

本文为个人思想，难以理解的可以看原版——总结自极客时间教程
大O符号
本文为作者原创，转载请注明出处:https://www.jianshu.com/p/39454c3e398f

一. 大O复杂度表示法

每一行代码在CPU中都有类似的操作 读数据-运算-写数据，每个指令的CPU执行时间忽略不计

例一

//运算: 值加载到CPU寄存器->CPU执行: CPU每次执行的时间都是1

int cal(int n) {      
   int sum = 0;          //给sum赋值            1
   int i = 1;            //给i赋值              1
   for (; i <= n; ++i) { //会遍历n次           n
     sum = sum + i;      //执行n次            n
   }
   return sum;
 }


执行次数 ： 2n+2
    

例二

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


执行次数 ： 2n*n+2n+3

这就是 大O时间复杂度表示法。 大O时间复杂度实际上并不是具体
表示代码的真正执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，
也叫做 渐进时间复杂度

二. 时间复杂度分析法则

代码执行时间，加上就代表一种随变化的趋势：

1.单段代码看高频，多段代码取最大

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

大O复杂度表示法只是表示出一种变化的趋势，一般忽略掉公式中的 常量，低阶，系数，只需记录最大阶的量级即可（）；

所以以上两个例子中的分别为： 和

2. 多个规模求加法

最终的结果还是要满足单段代码看高频总复杂度等于量级最大的那段代码的复杂度

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

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

忽略常数，只拿最大量，f(n)= n*n+2n

时间复杂度:

3. 嵌套代码求乘积

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

  for (; i <= n; ++i) { //n
     j = 1; 
     for (; j <= n; ++j) { //如果不考虑外层for循环，单独这里的执行次数也是n
       sum_3 = sum_3 +  i * j;
     }
   }
所以执行次数为 f(n)=n*n

时间复杂度：

1. 总结：

2. 1. 单段代码看高频：比如循环
   2. 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
   3. 嵌套代码求乘积：比如递归、多重循环等
   4. 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

​

三. 常见复杂度

多项式量级	非多项式量级
常数阶	指数阶
对数阶	阶乘阶
线性阶
线性对数阶
k次方阶

学过数学的都知道，非多项式量级的变化趋势会随着的变大而急速增大

1.

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

即便有3行，他的复杂度也是而不是，满足法则1：只关注循环执行次数中最多的一段代码

2.

     for (; j <= n; ++j) { //n*n
       sum_3 = sum_3 +  i * j;//n*n
     }

每行要运行的次数，复杂度为 满足法则1

3.

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

复习

---

​ 推导过程

---

​ 高中对数学习

4.

根据乘法法则，如果一个时间复杂度为的代码中嵌套了另一段的代码，那么这一整段的代码时间复杂度为

四.复杂度分析

1. 最好，最坏时间复杂度

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

最好时间复杂度 ： i=0时  array[i]=x,f(n)=1
最坏时间复杂度 ： i无限接近n时，array[i]=x f(n)=n

结果：

最好时间复杂度为:

最坏时间复杂度为

2 平均复杂度计算

平均复杂度 = 每种情况下要遍历的次数之和/要发生情况总数

上面的例子，要查找x在数组array中的位置，有n+1种情况（x在数组中有n种情况，还有一种是不在数组中），也就是说程序要执行n+1次；

每种情况需要需要遍历n次，如，i=1就只有一种情况， i=2就是两种，以此类推，得出公式：

一共需要次(多处来的那个n次，因为如果x不再数组中，也需要遍历n次)，然后运用等差数列求出和；

等差数列：

f(n)表示该段程序的执行次数,

算出结果为：

---

同时，x在数组中和不在数组中的概率都是，x出现在现在 0~n-1 中任何一个位置的概率也都是

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

如果有涉及到概论,则平均时间复杂度的算法为:

这个值就是概论论中的加权平均值

总结:

均摊时间复杂度:代码块的执行存在两种截然相反的时间复杂度情况，且这两种情况的出现频率是有规律的，一般取出现频率多的情况作为时间复杂度

若对您有帮助，可以点个喜欢吗 U•ェ•*U