算法分析 | From Zero to Hero

算法的复杂性体现在时间复杂性和空间复杂性上.一般使用渐进分析法来表达和计算一个算法的复杂性.

渐进分析法

一般表示输入规模与时间关系的函数比较复杂.渐进分析法计算时间时通常只考虑显著改变函数量级的部分,其余部分忽略.

渐进分析法是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。

渐进分析法包含三种表示方法:大O表示法,Ω(欧米伽)表示法,Θ(西塔)表示法

大O表示法

对于f(n)，存在正数n0、c，使得当 n>n0 时，始终存在 0 <= f(n) < =c*g(n)，则我们可以用 f(n)=o(g(n))表示。

算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2），它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

大O表示法表示时间复杂度的最小上限.

for(i=1;i<=n;i++)   //循环了n*n次，当然是O(n^2)
	 for(j=1;j<=n;j++)
	 	s++;

//循环了(n+n-1+n-2+...+1)=(n+1)*n/2≈(n^2)/2
//时间复杂度是O(n^2)
for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
		s++;