时间复杂度分析

2019-04-20 本文已影响0人觥筹啊觥筹

思维导图

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

本文为个人思想，难以理解的可以看原版——总结自极客时间教程
 大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

$T(n) ：所有代码执行总时间;$

$f(n) : 代码执行次数的总和$

$时间复杂度： O= \frac{T(n)}{(f(n))}$

$O表示代码的实行时间T(n)和总执行次数f(n)成正比$

$T(n)=O(f(n))$

$例一中的代码执行时间为: T(n)=O(2n+2)$

$第二个例子就是 T(n)=O(2n^2+2n+3)$

$（n 表示数据规模的大小）$

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

二. 时间复杂度分析法则

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

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

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

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

所以以上两个例子中的 $T(n)$ 分别为： $O(n)$ 和 $O(n^2)$

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

时间复杂度:
$T(n)=O(n^2+2n) = O(n^2+n)=O(n^2)$

3. 嵌套代码求乘积

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

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

时间复杂度：
$T(n)=O(n^2)$

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

三. 常见复杂度

多项式量级	非多项式量级
常数阶 $O(1)$	指数阶 $O(2^n)$
对数阶 $O(logn)$	阶乘阶 $O(n^n)$
线性阶 $O(n)$
线性对数阶 $O(nlogn)$
k次方阶 $O(n^k)$

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

1. $O(1)$

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

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

2. $O(n)$

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

每行要运行的次数，复杂度为 $O(n)$ 满足法则1

3. $O(logn)$

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

复习 $: 2要乘自己3次能等于8，也就是2^3=8$

推导过程

$i为一个常数，这的第三行代码一直在做2*2*2*2*2..的动作，一直乘到积>=n为止$

$这里第三行假设2要乘自己x次才能和n相等，得出公式为2^x=n$

$循环在2^x=n的时候结束，$

$x为执行次数，所以代码的执行次数f(n) = x$

$根据高中数学，和公式2^x=n，算出x=log2^n$

高中对数学习
$T(n)=O(log2^n) 去掉底数，常数，保留最大量阶 T(n)=O(logn)$

4. $O(nlogn)$

根据乘法法则，如果一个时间复杂度为 $O(logn)$ 的代码中嵌套了另一段 $O(logn)$ 的代码，那么这一整段的代码时间复杂度为
$O(nlogn)=O(log{n^2})=O(logn)*O(logn)$

四.复杂度分析

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

结果：

最好时间复杂度为: $T(n)=O(1)$

最坏时间复杂度为 $T(n)=O(n)$

2 平均复杂度计算

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

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

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

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

等差数列：
$Sn=n*(a1+an)/2$

$套入公式，得出结果：在n+1中情况下，f(n)=\frac{(n+n^2)}{2}+n$

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

算出结果为：
$avg(T(n))=\frac{1+2+3+...n+n}{n+1}=\frac{\frac{(1+n)n}{2}+n}{n+1}=\frac{(1+n)n+2n}{2(n+1)}=\frac{(1+2+n)n}{2(n+1)}=\frac{n(n+3)}{2(n+1)}$
$去掉系数，低阶，常数*：avg(T(n))=O(n)$

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

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

如果有涉及到概论,则平均时间复杂度的算法为:
$1\frac{1}{2n}+2\frac{1}{2n}+3\frac{1}{2n}+4\frac{1}{2n}+...+n\frac{1}{2n}+n\frac{1}{2}=\frac{3n+1}{4}$

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

总结:

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

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