罗汉松

注册

 

发新话题 回复该主题

时间复杂度的表示分析计算方法一文带你 [复制链接]

1#
北京哪个皮炎医院好 http://m.39.net/pf/a_8833134.html

作者

OverRedMaple

责编

Carol

来源

CSDN博客

封图

CSDN付费下载于东方IC

如果你还在发愁究竟怎么计算时间复杂度和空间复杂度,那你是来对地方了!

名词解释:

在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

时间复杂度的表示方法

其实就是算法(代码)的执行效率,算法代码的执行时间。我们来看下面一个简单的代码:

intsumFunc(intn){

intnum=0;//执行一次

for(inti=1;i=n;++i){//执行n次

num=num+i;//执行n次

}

returnnum;

}

假设,每行代码的执行时间为t,那么这块代码的时间就是(2n+2)*t

由此得出:代码执行时间T(n)与代码的执行次数是成正比的!

那么我们来看下一个例子:

intsumFunc(intn){

intnum=0;//执行一次

for(inti=1;i=n;++i){//执行n次

for(intj=1;j=n;++j){//执行n*n次

num=num+i*j;//执行n*n次

}

}

}

同理,该代码执行时间为(2n*n+n+1)*t,没意见吧?继续往后看!

注意:在数据结构/算法中,通常使用T(n)表示代码执行时间,n表示数据规模大小,f(n)表示代码执行次数综合,所以上面这个例子可以表示为f(n)=(2n*n+n+1)*t,其实就是一个求总和的式子,O(大写O)表示代码执行时间与f(n)成正比例。

根据上面两个例子得出结论:代码的执行时间T(n)与每行代码的执行次数n成正比,人们把这个规律总结成这么一个公式:T(n)=O(f(n))

所以呢,第一个例子中的T(n)=O(2n+1),第二个例子中的T(n)=O(2n*n+n+1),这就是时间复杂度表示法,也叫大O时间复杂度表示法。

但是,大O时间复杂度并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度,简称时间复杂度。

与泰勒公式相反的是,算了,扯哪去了…

当n变得越来越大时,公式中的低阶,常量,系数三部分影响不了其增长趋势,所以可以直接忽略他们,只记录一个最大的量级就可以了,所以上述两个例子实际他们的时间复杂度应该记为:T(n)=O(n),T(n)=O(n*n)

我想你应该明白大致是怎么回事了,那么我们来看看如何去计算它?

时间复杂度的分析与计算方法

(1)循环次数最多原则

我们上面说过了,当n变得越来越大时,公式中的低阶,常量,系数三部分影响不了其增长趋势,可以直接忽略他们,只记录一个最大的量级就可以了。因此我们在计算时间复杂度时,只需

分享 转发
TOP
发新话题 回复该主题