复杂度分析

时间复杂度

定义

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用$T(n)$表示，若有某个辅助函数$f(n)$,使得当n趋近于无穷大时，$T(n)/f(n)$的极限值为不等于零的常数，则称$f(n)$是$T(n)$的同数量级函数。记作$T(n)=O(f(n))$,称$O(f(n))$为算法的渐进时间复杂度，简称时间复杂度；

计算方法

找出算法的基本操作，然后根据响应的语句确定执行次数，再找出对应的$f(n)$，则$T(n) = O(f(n))$；

常型

类型	f(n)	说明	示例
常数阶	$O(1)$	与问题规模n无关的常数	$temp=i; i=j; j=temp$
线性阶	$O(n)$	与n正相关	$for(i=0;i<n;i++){}$
K次方阶	$O(n^k)$	由嵌套最深的最内层的语句的频度决定
指数阶	$O(2^n)$
对数阶	$\log_2^n$	二分
线性对数阶	$n\log_2^n$	n个for循环的二分

空间复杂度

$S(n)=O(f(n))$