时间复杂度分析.ppt

文档介绍：时间复杂度分析
什么是时间复杂度?
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。
如何计算?
计算时间复杂度的过程,常常需要分析一个算法运行过程中需要的基本操作,计量所有操作的数量。
各种时间复杂度
O(1)<O(logn)<O(n1/2) <O(n) < < O(nlogn) <O(n×n1/2)< O(n2)<O(n3) < O(2n) < O(n!) < O(nn)
O(1)(常数时间)
不受数据规模的影响
例子:判断一个数的奇偶
O(logn)
数据规模不断减半
例子:二分查找
给定一个长度为n的有序序列A[0],A[1],A[2]...A[n],询问一个数num在序列中的位置
int L=0,R=n-1;
while(L<=R)
{
int mid=(L+R)/2;
if(a[mid]>=num) R=mid-1;
else L=mid+1;
}
printf("%d\n",L);
O(n1/2)
例子:判断一个数是否是素数
for i=2 to sqrt(n) 依次判断是否能够整除n即可
O(n)
又叫做线性时间复杂度
例子:给定一个长度为n的序列,求最大值
O(nlogn)
例子:对一个长度为n的无序序列A排序
归并排序大致框架
merge-sort(A,L,R)
if L<R
then MID=(L+R)/2
merge-sort(A,L,MID)
merge-sort(A,MID+1,R)
merge(A,L,MID,R)