算法时间复杂度计算
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法时间复杂度计算,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2741字,纯文字阅读大概需要4分钟。
内容图文
![算法时间复杂度计算](/upload/InfoBanner/zyjiaocheng/682/e9fbb205d8cb42908e818fdd6f6fa361.jpg)
首先假设计算机运行一次基础代码需要执行一次运算
int func(void){
printf();//需要执行1次
return 0;//1次
}
上面方法需要执行2次
int func(int n)
{
for(int i=0;i<n;i++)//n+1次
{
printf("");//n次
}
return 0;//1次
}
这个方法需要(n+1+n+1)=2n+2次运算
把算法需要执行的运算次数用输入大小n的函数表示,即T(n)
T表示运算次数
定义:存在常数c和函数f(N) 使得当N>=c时 T(N)<=f(N),表示T(N)=O(f(n))
算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述。
时间复杂度的计算
三个基础定理:
-
我们知道常数项对函数的增长速度影响并不大,所以当 T(n) = c,c 为一个常数的时候,我们说这个算法的时间复杂度为 O(1);如果 T(n) 不等于一个常数项时,直接将常数项省略。
-
我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的,同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高,所以我们直接忽略低此项。
-
因为函数的阶数对函数的增长速度的影响是最显著的,所以我们忽略与最高阶相乘的常数。
更进一步,四大法则
- 对于一个循环体,假设循环体的时间复杂度为On,循环次数为m,则这个循环的时间复杂度为O(m*n)
void aFunc(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}
}
此时时间复杂度为 O(n × 1),即 O(n)。
2.对于多个循环,假设循环体的时间复杂度为 O(n),各个循环的循环次数分别是a, b, c…,则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。
void aFunc(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
for(int j = 0; j < n; j++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}
}
}
此时时间复杂度为 O(n × n × 1),即 O(n^2)。
- 对于顺序执行的语句或者算法,总的时间复杂度等于其中最大的时间复杂度。
void aFunc(int n) {
// 第一部分时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
// 第二部分时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。
- 对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。
void aFunc(int n) {
if (n >= 0) {
// 第一条路径时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("输入数据大于等于零\n");
}
}
} else {
// 第二条路径时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("输入数据小于零\n");
}
}
}
此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。
时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。
有递归时的算法时间计算
此时要用到主定理的思想
主定理最早出现在《算法导论》中,提供了分治方法带来的递归表达式的渐近复杂度分析。
规模为n的问题通过分治,得到a个规模为n/b的问题,每次递归带来的额外计算为c(n^d)
T(n)<=aT(n/b)+c(n^b)
那么就可以得到问题的复杂度为:
T(n)=O(n^dlog(n)),if a=b^d
T(n)=O(n^d),if a<b^d
T(n)=O(n^logb(a)),if a>b^d
内容总结
以上是互联网集市为您收集整理的算法时间复杂度计算全部内容,希望文章能够帮你解决算法时间复杂度计算所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。