怎样计算一个算法的复杂度?

分析一个算法主要看这个算法的执行需要多少机器资源。在各种机器资源中,时间和空间是两个最主要的方面。因此,在进行算法分析时,人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据所占用的空间资源。算法所花费的时间通常称为时间复杂度,使用的空间资源称为空间复杂度。接下来学习如何计算一个算法的时间复杂度和空间复杂度。

1.时间复杂度

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,然后分析T(n)随n的变化。

怎样计算一个算法的复杂度?

这样用大写的O来标记算法的时间复杂度,称之为大O(Order的简写)标记法。一般随着n的增长,T(n)也会随之增长,其中T(n)增长最慢者就是时间性能最优的算法。

在计算时间复杂度的时候,根据T(n)与n的最高阶数关系,我们给这些算法的复杂度进行了归类,如表1所示。

怎样计算一个算法的复杂度?

当然还会有一些其他阶数关系,这里只是列出了几种较常见的关系。算法的执行次数可能会与规模n呈现出这些关系,那么这些关系又是如何推导出来的呢?下面给出大O阶的推导方法:

(1)用常数1取代运行中的所有加法常数。

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

(3)如果最高阶项存在,且不是1,则除去其常系数,得到的结果就是大O阶。

接下来通过分析几段程序的执行过程来推导出其时间复杂度,程序段1代码如下所示:

int a=100;              //执行一次int b=200;              //执行一次int sum=a+b;            //执行一次printf("&d\\n",sum);      //执行一次

上述程序段有4行代码,每一行执行1次,加起来一共执行了4次,f(n)=4,即T(n)=O(4)。根据推导方法中的第一条,将常数项以1代替。在保留其最高阶项时,发现其没有最高阶项,因此该算法的时间复杂度为O(1),为常数阶。程序段2代码如下所示:

void func(){    int i,sum=0;                         //执行一次    for (i=0;i<=100;i++)    {    sum +=i;                              //执行n次    }    printf("sd\\n",sum);               //执行一次}

该程序段的执行次数为1+n+1,则f(n)=n+2,即T(n)=O(n+2)。然后将常数项以1替换,且只保留最高阶项,则得出T(n)=O(n),因此该算法的时间复杂度为O(n),为线性阶。

程序段3代码如下所示:

void func(){    int i=l;    do    {    i*=2;    }    while (i<n);}

在这个程序段中,当i<n时,循环结束。如果循环了f(n)次,则2(fn)=n,即f(n)=log2n,T(n)=O(log2n)。然后消除常系数,保留最高阶项,最后得出T(n)=O(logn),为对数阶。

用大O阶来推导算法的复杂度并不难,读者在以后的学习中设计算法,就可以用此法来估测算法的优劣。

2.空间复杂度

空间复杂度是对一个算法在运行过程中所占存储空间大小的度量,一般也作为问题规模n的函数,以数量级形式给出,格式如下所示:

怎样计算一个算法的复杂度?

一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。在对算法进行分析时,只考虑辅助变量所占空间。若所需辅助空间相对于输入数据量来说是常数,则称此算法为原地工作。若所用空间量依赖于特定的输入,则除了有特殊说明外,均按最坏情况考虑。

有时候,在写代码时可以用空间来换取时间,例如,写一个算法来判断某年是否是闰年,这样每输入一个年份都要调用算法去判断一下,在时间上就有点复杂。为了提高效率,可以用空间来换取时间,即建立一个大小合适的数据,编号从0到n,如果是闰年,则存入数据1,否则存入数据0。这样只要通过判断年份编号上存储的是0还是1就知道该年份是否是闰年了。

用空间换取时间可以将运算最小化,但这两种情况哪种更好,要结合具体情况而定。一般情况下,都是用时间复杂度来度量算法,当不加限定地使用“复杂度”这一术语时,都是指时间复杂度。

本文来自投稿,不代表重蔚自留地立场,如若转载,请注明出处https://www.cwhello.com/367018.html

如有侵犯您的合法权益请发邮件951076433@qq.com联系删除

(0)
黑马程序员黑马程序员订阅用户
上一篇 2023年8月29日 16:02
下一篇 2023年8月29日 16:13

相关推荐

  • 教你SEO网站优化之2022年12月百度新算法分析。

     seo网站优化之2022年12月百度最新算法分析 大家好,我是杭州网站制作小编SEO网站优化-李栋,今天就和大家一起分享一下2022年最新的百度算法走势。百度总是在变化中逐步完善自身,更加有利于用户体验,为用户提供最…

    2023年6月18日
    01
  • 百度算法不断更新我们SEO如何去做。

    最近很多的新手seo咨询百度算法不断更新我们SEO如何去做,那么,下面就由小编为大家介绍一下。 百度算法不断更新我们SEO如何去做,小编为大家介绍以下几点: 第一:这是最近新推出的,大家可以不妨现在试试登录百度…

    2022年10月30日
    015
  • 分享直通车省油宝算法是什么。

    直通车省油宝推荐算法首先的就是相关性,关键词和商品的相关性越高,被搜索到的概率越大;其次是基础分,消费者给店铺的动态评分评价越好,基础分越高,关键词越好。 如今网店之间的竞争是非常激烈的,很多网店店主…

    2023年10月21日
    04
  • ORB算法在opencv中实现方法

    在OPenCV中实现ORB算法,使用的是: 1.实例化ORB orb = cv.xfeatures2d.orb_create(nfeatures) 参数: ·nfeatures: 特征点的最大数量 2.利用orb.detectAndCompute()检测关键点并计算 kp,des = orb.detectAndCompute…

    2023年8月29日
    06
  • 分享网站SEO优化如何应对频繁的算法更新。

    面对算法的不断变化,有些站长们一方面显得有些沮丧气馁,另一方面还沉浸在失败的阴影中,当然辛辛苦苦做的排名没有了难免会有点难以接受,但是事实就是事实,既然都已经大势所趋了,就应该好好的方调整好自己的思…

    2023年6月27日
    00
  • 我来分享了解搜索引擎算法规则,让SEO事半功倍。

    随着搜索引擎智能化水平的增长,我们可以看到很多基于关键词的搜索对于用户而言,命中率变得更高,很多在网站的首页就基本上能够被充分的展示,并且轻松的帮助用户解决相应的问题。事实上根据权威数据的统计,很多…

    2023年6月24日
    01
  • AES加解密算法怎么实现。

    AES加解密算法是一种对称加密算法,广泛应用于数据加密和保护领域,它被广泛用于许多安全协议中,如SSL/TLS、IPsec等,下面将详细介绍AES加解密算法的实现过程。 1. 密钥生成: 需要生成一个密钥,AES算法支持128位…

    2024年6月14日
    00
  • 分享怎样应对SEO算法的变化。

    随着seo算法的不断更新我们在做优化时也得随着而变化,但是SEO算法的更新随时阻碍我们的工作,所以想要不受大的影响我们就要了解算法的变化和应对方法,下文将这个问题重点分析。 一、搜索引擎的算法经历了以下四大…

    2023年6月20日
    01

联系我们

QQ:951076433

在线咨询:点击这里给我发消息邮件:951076433@qq.com工作时间:周一至周五,9:30-18:30,节假日休息