复杂度分析

大O时间复杂度分析法

T(n) = O(f(n))
T(n):表示代码执行的时间
n:表示数据规模的大小
f(n):表示每段代码执行的总和
O：表示T(n）与f(n)成正比

如何分析一段代码的时间复杂度

• 只关注循环次数最多的代码
• 加法法则：总的时间复杂度 = 量级最大的那段代码的时间复杂度
• 乘法法则：嵌套代码的时间复杂度 = 内外代码的时间复杂度的乘积

复杂度量级

可以粗略的分为两类：

• 多项式量级：下图左侧一列、随着数据规模的增长，算法执行的时间和占用的空间按比例增长
• 非多项式量级：右侧一列、随数据规模的增长，算法执行的时间和占用的空间暴增

浅析最好、最坏、平均、均摊时间复杂度

最好、最坏时间复杂度

//这段代码要实现的功能是，在一个无序的数组中，查找变量x出现的位置，如果没有找到就返回-1
int find(int[]array , int n , int x){
		int pos;
		for(int i = 0;i<array.lenth;i++){
			if(array[i] == x){
			pos = i;
			System.out.println(pos);
			break;
		}
	}else{
	return -1;
	}
}

最好时间复杂度分析
在最理想的情况下，我们要找的变量x刚好是数组的第一个元素n那么此时的时间复杂度为O(1）
最坏时间复杂度分析
在最坏的情况下，变量x不在数组内，那么久需要把整个数组都遍历一遍，那么此时的时间复杂度为O(n)
平均时间复杂度分析
最好和最坏的时间复杂度都是对应的极端情况下的代码复杂度，发生的概率并不大，为了更好的表示平均情况下的复杂度，就要引入另一个概念：平均时间复杂度

查找变量x的位置一共有n+1中情况，把每种情况下，查找需要遍历的元素个数累加起来，再除以n+1，就可以得到需要遍历元素个数的平均值。

在时间复杂度的大O标记法中，可以省略掉常数、低阶、常量，所以简化后得到的平均时间复杂度为O（n）

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

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分

均摊时间复杂度
在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

如何分析平均、均摊时间复杂度？

• 平均时间复杂度：代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示
• 均摊时间复杂度：两个条件满足时使用：1.代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度。2.低级别和高级别复杂度出现具有时序规律，均摊结构IBA都等于低级别复杂度