算法的时间复杂度 O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2^n) O(n! ) O(n^n)
目录
1.算法时间复杂度
第1种方法：
第2种方法：
第3种方法：
2.推导O阶方法
1.常数阶
2.线性阶
3.对数阶
4.平方阶
1.算法时间复杂度
算法的时间复杂度，也就是算法的时间量度，记作：T(n)＝O(f(n)).它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
这样用O[] 来体现时间复杂度，我们称为大 O 记法。
例如 三种求和方法：
第1种方法：
int sum= 0；int n =100;sum =(1+n) *n/2;printf("sum= %d\n",sum);
O[1]
第2种方法：
int i, sum=0,n=100;for(i=1;i<=n;i++)sum=sum+1;｝printf("%d",sum);
O[n]
第3种方法：
int i, j,x = 0,sum=0,n=100;／＊执行一次＊／for(i=l;i<=n;i++)｛for(j=l;j<=n;j++)｛x++;／＊执行nxn次＊／sum= sum +X;｝｝printf("sd",sum);O[n^2]
2.推导O阶方法
1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1, 则去除与这个项相乘的常数。
得到的结果就是大O阶。
1. 常数阶
求和的 第1种方法：
时间复杂度是 O[1] 而不是 O[3].
事实上 无论n是多少 假如有sum =(1+n) *n/2; 13句 ，这种问题与大小无关（n的多少） 执行时间恒定的算法 我们称之为具有 O[1]的时间复杂度的常数阶。
2.线性阶
分析算法的复杂度，主要分析算法的循环情况
求和的 第2种方法：
时间复杂度是O[n]，因为 for 里面要执行n次循环。
3.对数阶
下面的这段代码，时间复杂度又是多少呢？
int count=1;while(count中于每次 count 乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大干n, 则会退出循环。由2x=n 得到x=logzn.所以这个循环的时间复杂度为o(logn).
4.平方阶
下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为o(n).
int i,j;for(i=0;i而对于外层的循环，不过是内部这个时间复杂度为0(n)的语句，再循环n次。所
以这段代码的时间复杂度为0[n^2].
常用的时间复杂度所耗费的时间从小到大依次是：
O(1)
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！