Tools

首页 / 算法返回列表

算法（二）复杂度分析

阅读：593 发布：2018-10-12 作者：lypeng

数据结构与算法（二）复杂度分析

补补知识，看了一下，现在对复杂度终于有个了解了~
内容中的示例和部分文字摘自原作者~

## 复杂度分析

时间（效率更快），空间（存储更省内存）

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

T(n)    代码总执行时间
O       每行代码执行的单位时间
f(n)    所有代码执行次数（每一行执行次数总和）

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

一个for循环总次数n次，f(n)=2n+2, T(n) = O(f(n)) = O(2n+2)

## 大 O 时间复杂度表示法。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n^2)

## 时间复杂度分析
### 1.只关注循环执行次数最多的一段代码
原因：低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，关注最大的即可
### 2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
O(常量级别+一阶运算+二阶运算) = O(二阶运算)
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
### 3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
举例：两个for循环

## 几种常见时间复杂度分析
常量阶 O(1) //没有循环，代码依次执行，不管5行6行，都是常量级别
对数阶 O(log n) //以2为底n的对数
线性阶 O(n)
线性对数阶 O(n log n)//n 乘以 以2为底n的对数
指数阶 O(2^n)
阶乘阶 O(n!)
平方阶 O(n^2) 立方阶 O(n^3)... k次方阶 O(n^k)

### 1. 对数阶分析
```
 i=1;
 while (i <= n)  {
   i = i * 2;
 }
```

执行次数设为x,
i的取值：1 2 4 8 16 ... n
        2^0 2^1 2^2 ... 2^x
2^x = n
x = log n //以2为底n的对数

如果改成 i = i * 3;则结果变为以3为底
因为以3为底的可以转化为以2为底的，所以同城用以2为底的表示复杂度
log（以3为底）n = log（以3为底）2 * log（以2为底）n

### 2. 线性对数阶
即把对数阶循环N次

### 3. O(m+n)、O(m*n)
无法确定m与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]
  }
}
```

int[n] //大小为n的int类型数组存放数据，空间复杂度：O(n)

我们常见的空间复杂度就是 O(1)、O(n)、O(n^2)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。

## 其他概念
最好情况时间复杂度，最坏情况，平均情况，均摊情况
大致理解，不做深究了~

------本文结束感谢阅读------

上一篇：算法（一）基础概念

下一篇：算法（三）冒泡排序、插入排序、选择排序、归并排序、快速排序