Dotcpp  >  编程教程  >  数据结构入门  >  时间复杂度的度量方法

时间复杂度的度量方法

点击打开在线编译器,边学边练

接上文,在理解了时间复杂度的概念后,就可以根据实际的代码进行度量了,以下举例了几个常用的时间复杂度的表示,对于如何度量其最重要的是观察程序中的循环结构,每一个循环结构代表执行循环中的指令n次,而其余指令一般而言一行代码代表执行一次,对于一个程序而言,执行的次数相差较小其实没有什么区别,都是一瞬间执行完毕。

1. 度量时间复杂度

a)O(1)  /  O(C)  C代表常数

#include<stdio.h>
int main(){
    printf("Hello World");  //执行一次
    return 0;       //执行一次
}

对于如上代码,执行了两次,即O(2)=O(1),我们可以称其时间复杂度为O(1),或者常数级时间复杂度

b)O(n)

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次
        ans+=i;     //执行一次
    }
    return 0;       //执行一次
}

对于如上代码,我们一共执行了n*1+2次,即O(n*1+2),由上文我们的公式得到其复杂度为O(n),或称之为线性阶时间复杂度。

c)O(n^2)

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次
        for(int j=0;j<n;j++){   //执行n次
            ans+=j;
        }
    }
    return 0;       //执行一次
}

对于如上代码,我们一共执行了n*n*1+2次,即O(n*n*1+2),由上文我们的公式得到其复杂度为O(n^2),或称之为平方阶时间复杂度,此外还有三层循环结构嵌套组成的O(n^3)级别的时间复杂度,称之为立方阶时间复杂度,随着嵌套的增多,甚至还有O(n!)级,称之为阶层级时间复杂度,但是这种级别复杂度极高,程序运行极其缓慢。

d)O(logn)

#include<stdio.h>
int main(){
    int i=1,n=10000;    //执行一次
    while(i<=n){    //执行logn次
        i*=2;
    }
    return 0;       //执行一次
}

对于如下代码,与上文的线性增长不同,其i的增长是倍增的形式,也就是说i会随着运行次数的增加变大的趋势变更大,这样会比那些简单的用加法上涨的变量更快到达循环结构的边界,这样的代码时间复杂度一般为log级别,对于本样例,有O(logn+2)=O(logn),称之为对数阶时间复杂度

e)O(n*logn)

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次
        int j=0;        //执行1次
        while(j<=n){    //执行log(n)次
            j*=2;
        }
    }
    return 0;       //执行一次
}

对于上文的对数级别的时间复杂度,一样可以实用别的循环进行嵌套,比如本样例O(n*(logn+1)+2)=O(n*logn)级别

除此之外还有很多种时间复杂度的组合,比如说O(2^n)这样的指数阶时间复杂度,有时甚至需要引入多个变量乃进行表示,不过最核心的还是要观察循环结构的处理。


2.各个复杂度的比较

如图,我们以x轴为n的规模,y轴为整体的计算次数,可以发现其明显的计算区别,立方级别似乎很小的数就变得需要很多得计算了,而相对得logn级别得复杂度似乎无论怎么增加n,其涨幅都不是很明显。

时间复杂度1

然而事实上,计算机的计算次数何止60次啊,计算机真实的计算速度是论千论万论亿级别的计算,所以我们的n会变得非常之大,让我们把坐标进行变化,以10000为界进行理解。

时间复杂度2


可以见到,平方以及立方级别的复杂度几乎已经是平贴着y轴的一条直线了,而O(n*log(n))与O(n)还保持着一定的速率进行增长,log(n)又是另一个极端,它变成了一个几乎贴着x轴的直线,这样算法的效率就轻易看得出了。

综上可以直观的得出:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

在设计程序的时候一定要注意,高计算需求的地方一定不要使用太高的时间复杂度的计算方式!



本文固定URL:https://www.dotcpp.com/course/92

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数据结构教程
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 C++STL库教程(附带题库)
第六章 串、数组、矩阵和广义表
第七章 树
第八章 图
第九章 查找算法
第十章 排序算法
第十一章 算法和竞赛
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)