社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
排序是将一组数据,依指定的顺序进行排列的过程
内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序.常见的内部排序有:直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。
外部排序:数据量过大,无法全部加载到内存中,需要借助外部存储进行排序。
度量一个程序(算法)执行时间的两种方法:
事后统计方法这种方法可行,但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较哪个算法速度更快.
事前估计方法通过分析算法的时间复杂度来判断哪个算法更优.
一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行的次数多,它花费时间就多.一个算法中语句执行次数称为语句频度或时间频度.记为T(n).
比如计算1-100所有数字之和,有两种算法
- int total=0;
- int end=100;
- //for循环计算
- for(int i=1;i<=end;i++){
- total+=i;
- }
执行次数取决于end长度.它的T(n)=n+1.
- //直接计算
- total = (1+end)*end/2;
直接计算只需执行一次即可,它的T(n) = 1.
估算时间频度时注意事项:
无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的复杂度就是O(1)
- int i = 1;
- int j = 2;
- ++i;
- j++;
- int m = i+j;
上述代码在执行的时候,它消耗的时间并不是随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示它的时间复杂度.
- int i = 1;
- while(i<n){
- i = i*2;
- }
在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了.假设循环x次之后,i就大于n了,此时循环就结束了,也就是说2的x次方等于n,那么x= log2n也就是说当循环log2n次以后,这个代码就结束了.因此这个时间复杂度为O(log2n).
- for(i=1;i<=n;i++){
- j = i;
- j++;
- }
for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以使用O(n)来表示它的时间复杂度.
- for(int m=1;m<n;m++){
- i = 1;
- while(i<n){
- i = i*2;
- }
- }
这个线性对数阶O(log2n)就是将时间复杂度为O(logn)的代码循环N遍.
即双层for循环,n*m
3层循环
k次循环
常见的算法时间复杂度由小到大依次为:O(1)
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!