当前位置:鱼C工作室 >数据结构和算法 > 查看文章

时间复杂度和空间复杂度2 – 数据结构和算法04

时间复杂度和空间复杂度2

 

让编程改变世界

Change the world by program


 

算法时间复杂度

 

我们说好的时间复杂度和空间复杂度呢?

历来大学老师在讲解这两个概念,都是直接登堂入室,导致八成学生对概念理解不深刻,或者说只是硬背起来而已。

 

为了让大家能够更好地接受这两个比较重要的概念,我们有了上一讲的准备环节。

这一讲我们直接切入正题,介绍计算复杂度的攻略,然后通过一系列例子和大家一起分析总结规律。

 

算法时间复杂度的定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。

 

算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。

它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

 

好长好长,没想到定义这个概念的老家伙比小甲鱼还罗嗦。(关键需要知道执行次数==时间)

这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。

 

一般情况下,随着输入规模n的增大,T(n)增长最慢的算法为最优算法。

显然,由此算法时间复杂度的定义可知,我们的三个求和算法的时间复杂度分别为O(1),O(n),O(n^2)。

 

三个求和算法?哪有?忘了?

好吧,看看以下这张图能不能勾起点回忆?

算法时间复杂度

 

推导大O阶方法

 

那么如何分析一个算法的时间复杂度呢?即如何推导大O阶呢?

 

我们给大家整理了以下攻略:

用常数1取代运行时间中的所有加法常数。

在修改后的运行次数函数中,只保留最高阶项。

如果最高阶项存在且不是1,则去除与这个项相乘的常数。

得到的最后结果就是大O阶。

 

世界上的东西就是这么简单,老头儿们把它讲复杂,那么它就复杂了,举几个例子:

 

常数阶

 

int sum = 0, n = 100;
 
printf(“I love fishc.comn);
printf(“I love Fishc.comn);
printf(“I love fishC.comn);
printf(“I love fIshc.comn);
printf(“I love FishC.comn);
printf(“I love fishc.comn);
 
sum = (1+n)*n/2;

 

大家觉得这段代码的大O是多少?

 

分页阅读: 1 2 下一页
为您推荐

报歉!评论已关闭.