深圳html5网站建设价格,网站建设最高管理权限,浦东新区专业做网站,网站内部链接的作用有哪些目录
1. 算法效率
2. 时间复杂度
2.1 时间复杂度的概念
2.2 大O的渐进表示法
2.3 举例说明#xff1a;
写在最后#xff1a; 1. 算法效率
我们该如何判断一个算法的好坏#xff1f;
衡量一个算法的好坏#xff0c;是从时间和空间两个维度比较的#xff0c;
而今天…目录
1. 算法效率
2. 时间复杂度
2.1 时间复杂度的概念
2.2 大O的渐进表示法
2.3 举例说明
写在最后 1. 算法效率
我们该如何判断一个算法的好坏
衡量一个算法的好坏是从时间和空间两个维度比较的
而今天我就来详细探讨一下时间复杂度。
2. 时间复杂度
2.1 时间复杂度的概念
时间复杂度是一个函数
而
算法中的基本操作的执行次数为算法的时间复杂度。
我们当然不能只用运行一段程序的速度来解释时间复杂度
毕竟每个人电脑的CPU运行速度不同。
例
#include stdio.hint main()
{int n 10;while (n 0){n--;}return 0;
}这一段代码走了10次
他的时间复杂度是O(1)。
例2
#include stdio.hint main()
{int n;scanf(%d, n);while (n 0){n--;}return 0;
}这段代码走了n次
他的时间复杂度是O(N)。
那么问题来了时间复杂度究竟是怎么求的
2.2 大O的渐进表示法
规则
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中只保留最高阶项。
3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
2.3 举例说明
void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
这段代码前面是2*N次后面是10次
加起来是2*N10
而他的时间复杂度是O(N)
例2
冒泡排序的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i) {if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if(exchange 0)break;}
}
冒泡排序最好的情况是O(N)
而最坏的情况是要和每一个数比较交换是O(N^2)。
所以他的时间复杂度是O(N^2)。
例3
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}
斐波那契递归的时间复杂度是O(2^N)。
通过上述的例子我们可以知道的是
计算时间复杂度计算的是该算法最坏的情况。
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
