分析算法的复杂度

本文目录

算法的时间复杂度O( )

语句总的执行次数T(n)是关于问题规模的n的函数
T(n) = O(f(n))
表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
随着输入规模n的增大,T(n)增长越慢的算法,算法越优
判断一个算法的效率时,仅关注函数的最高项的阶数即可

推导O()的方法

用常数1代替所有与问题规模n无关的执行语句
在修改后的运行次数函数中,只保留最高阶项
若最高阶项存在且系数不为1,去掉该最高阶项的常系数

常数阶O(1)
代码中的所有语句与问题规模n无关

int n = 1;
System.out.print("* ");
System.out.print("* ");
System.out.print("* ");

线性阶O(n)
一层循环

int sum = 0;
for(int i = 0;i < n;i++){ 
	sum += i;
}	

平方阶O(n2)
双层循环
执行次数:n+(n-1)+(n-2)+…+1=(1/2)n2+(1/2)n
O(n2)


for(int i = 0;i < n;i++){ 

	for(int j = i;j <= n;j++){ 
		System.out.print("* ");		
	}
	System.out.println();	
}

对数阶O(logn)
x个2最后得到n
2x=n
x=log2n

int i =1,n = 100;
while(i<n)
{ 
	i = i*2;
}

nlogn阶O(nlogn)

立方阶O(n3)

指数阶O(2n)

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数

一般来说,时间复杂度从小排列到大的顺序
O(1) < O(logn) < O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

总结

判断一个算法的效率时,仅关注函数的最高项的阶数即可
O(1) < O(logn) < O(n)<O(nlogn)<O(n2)
空间换时间

    原文作者:R$refresh
    原文地址: https://blog.csdn.net/weixin_43815873/article/details/104418928
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞