如果你之前对此有过一面之缘,那么这里可以帮你加深你的印象。如果你是初学,那么这里可以帮助你理解。在想要理解时间复杂度之前,我们先来了解一下算法。
算法是什么?
算法(algorithm),在数学(算学)和计算机科学之中,一个被定义好的、计算机可施行之指示的有限步骤或次序 ,常用于计算、数据处理(英语:Data processing)和自动推理。作为一个有效方法(英语:Effective method),算法被用于计算函数 ,它包含了一系列定义清晰的指令 ,并可于有限的时间及空间内清楚的表述出来 。(参考:维基百科)
简单来说,算法通常是指用计算机按照一定规则解决一类问题的明确和有限的步骤。
在了解算法之后,由于一个算法的优劣可以用时间复杂度与空间复杂度来衡量,所以理解算法时间复杂度对于理解算法也好,写好算法也好都有一定的益处。接下来我们先来了解一下算法的时间复杂度,之后结合计算理解。
时间复杂度又是什么呢?
在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。(参考:百度百科)
在了解了时间复杂度这一概念后,咱们先看一个图,加深一下对其理解。
图为个人绘制,上图以部分常见时间复杂度函数图像为基准绘制。
附:一些常见的算法时间复杂度由小到大依次为:
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n^2) < Ο(n^3)…<Ο(n!)
最后我们再结合几个简单的时间复杂度题来增进对时间复杂度的认识。
答案放在了文末,建议先做题后对照答案
1. (单选题)一个算法应该是( )。
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A 和C
2. (单选题)某算法的时间复杂度为O(n2) ,表明该算法的()。
A. 问题规模是n2
B. 执行时间等于n2
C. 执行时间与n2 成正比
D. 问题规模与n2 成正比
3. 下列叙述中正确的是( )
A. 一个算法的空间复杂度大,则其时间复杂度也必定大。
B. 一个算法的空间复杂度大,则其时间复杂度必定小。
C. 一个算法的时间复杂度大,则其空间复杂度必定小。
D. 上述三种说法都不对。
4. 有以下算法,其时间复杂度为()
void fun (int n) {
int i=0 ;
while (iii <=n)
i++ ;
A. O(logn )
B. O(nlogn)
C. O(³√n)
D. O(n)
看到这里,就进入了对答案时间
1.B 2.C 3.D 4.C 你全对了吗?无论是与否,都要恭喜你对时间复杂度又多理解一点!如果有疑问,欢迎评论区提出!
作者:code_流苏
如有错误,希望大家多多指正!
希望大家多多点赞支持!