首页 > 搜索 > 衡量算法效率的方法,衡量算法时间效率的方法

衡量算法效率的方法,衡量算法时间效率的方法

互联网 2020-10-24 23:09:29
在线算命,八字测算命理

以前对这方面是一知半解,终于在一次大众点评的笔试中受到刺激。

步入正题:什么样的算法才是高效的算法?想必所有的人都这么想过:用最少的钱,花做最短的时间,买到最多的东西。同样,用最少的内存空间,花最短的时间解决问题的算法就是。因此我们考虑用时间和空间来衡量一个算法的效率。

首先我们来考虑如何利用时间来衡量算法效率。比较容易想到的方法时,可以利用计算机计时的功能,来计算不同算法的效率。在此基础上衍生了几种方法:

事后统计方法:通过设计好的测试程序和数据,利用计算机的计时功能对实现不同的算法的程序运行,通过比较运行时间来确定算法效率的高低。

 咋眼一看,感觉好简单啊。但是问题来了:首先必须必须根据算法编写好程序,通常这会花掉很多时间。对于有些糟糕的算法,这无疑是中时间上的浪费。其次,这种方法受环境影响太大,主要是硬件环境和软件环境。我们很难模拟两种完全一样的运行环境。最后,测试算法的数据设计比较麻烦。尤其是在需要的测试据 的模很大的时候,显得非常麻烦。

总之,这种事后统计的方法太过于麻烦,因此不考虑。

事前分析估算法:在编制程序之前,依据统计方法进行估算。

统计发现用高级语言编写的程序运行时所消耗的时间主要受这几方面影响:

算法采用的策略,这是算法好坏的根本。编译产生的代码质量问题输入规模机器硬件环境,主要是执行指令速度。

抛开硬件和软件等因素,单纯的懂算法来考虑,我们发现,一个程序的好坏依赖于算法策略和输入规模。

程序运行所耗费的时间主要是用来执行指令,因此,测定运行时间最可靠的方法时计算对运行时间有消耗的基本操作执行的次数。当然,我们该想到运行的时间和执行的次数成正比。最终,我们将衡量程序运行的时间转换为计算基本操作的次数。

现在开始正式说说算法的时间复杂度:分析算法时,语句总的执行次数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(n2):平方阶

推导大O阶的方法

在分析一个算法时,如何分析器时间复杂度呢?也就是如何推导大O阶?

推导规则:

用常数1取代运行时间中所有加法常数。其次,只保留最高阶项。如果阶项系数存在且不为1,则去掉这个系数。

最终得到的就是大O阶。

常数阶:

下面我们来举例说明:

int sum=0,n=300;//执行一次

sum=(1+n)*n/2;//执行一次

printf("%d",sum);//执行一次

算法运行次数的函数f(n)=3.根据上面的推导规则,将常数项改为1。在保留最高项时发现没有最高项,因此这个算法时间复杂度为O(1)。

有人纳闷为什么不是O(3)?这里就是我们刚才提到的要注意的地方。我们只是用执行次数来衡量时间复杂度,但执行次数并不等于时间复杂度。事实上,无论输入规模n为多少,执行的时间总是恒定的,时间复杂度总为O(1),也成为常数阶。

线性阶:

要分析算法时间复杂度,关键是分析循环结构的运行情况。

int i;

for(i=0;i=n;i++){printf("%d",i);//时间复杂度为O(1)的程序步骤序列

}

因为循环体中的代码必须执行n次,因此时间复杂度为O(n)

对数阶:

int sum=i;

while(sum

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多