时间复杂度

#时间复杂度

##整个算法学习的精髓

##为什么需要复杂度分析

###大O复杂度表示法

- 所有代码的执行时间 T(n) 与每行代码的执行次数成正比


	- T(n) = f(n)

		-  n表示数据的规模
		- f(n)每行代码执行的次数总和

###  事后统计法

-  测试结果非常依赖测试环境

	- 处理器不同

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

	- 对于同一个排序算法，待排序数据的有序度不一样，排序执行时间就会有很大的差别，还有极端情况，数据的规模也会造成影响

## 大O复杂度表示法

### n 表示数据规模的大小

### f(n) 表示每行代码执行的次数总和

##  最好，最坏情况复杂度分析

###  例子：在一个无序数组中找到变量x的位置，并返回

-  数组的长度是n，时间复杂度是O（n）
- 改进：找到就可以退出循环了

## 均摊时间复杂度分析

###  记住往数组里插入数据的例子

## 时间复杂度分析

###  只关注循环次数最多的一段代码

### 加法法则：总复杂度等于量级最大的那段代码的复杂度

### 乘法法则：嵌套代码的时间复杂度，等于嵌套内外代码复杂度的乘积

## 几种常见的时间复杂度实例分析

###  常量

-  代码中不存在循环和递归

### 对数

-  比较难的

	-  忽略对数的底，统一的记作O（logn）

### 线性

- O（m+n）和O（m*n）

	- 代码的复杂度由两个数据的规模来决定

###  线性对数

### 平方阶（k阶）

###  指数阶

### 阶乘

##  空间复杂度

###  算法的存储空间和数据规模之间的增长关系