人工智能:怎样进行算法的复杂度分析?

复杂度分析是估算算法执行效率的方法,公式O(f(n))表示算法的复杂度,此方法即为大O复杂度表示法O(f(n))中n表示数据规模,f(n)表示运行算法所需要执行的指令数。

大O复杂度表示法

下面的代码非常简单,求 1,2,3…n 的累加和,我们要做的是估算它的执行效率。

def calc(n): sum_ = 0 for i in range(1,n+1): sum_ = sum_ + i return sum_

假设每行代码执行的时间都一样为t,执行第2行代码需要时间t,第3,4行代码运行了n遍,需要的时间为2n*t,这段代码总执行时间为(2n+1)* t

结论:代码执行的总时间T(n)与每行代码的执行次数成正比

看下面的代码,估算该段代码的执行时间:

def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_

同样假设每行代码执行的时间都一样为t:执行第2行代码需要时间t,第3行代码运行了n遍,需要时间为n*t,第4、5行代码运行了n2次,需要时间为2n2 * t,执行所有代码的总时间为 (2n2 + n + 1)* t。

结论:代码执行的总时间T(n)与每行代码的执行次数成正比。

用O(f(n))来表示算法复杂度:

def calc(n): sum_ = 0 for i in range(1,n+1): sum_ = sum_ + i return sum_def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_

T(n) = O(f(n)) , O表示代码的执行时间T(n) 与 f(n)表达式成比例。

大O复杂度表示法:上面例子中的T(n) = O(2n+1), 另一个 T(n) = O(2n² + n + 1)。大O时间复杂度并不表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

当数据量特别大, 也就是n的取值很大的时候,大O表示法中低阶、常量、系数三部分并不会左右增长趋势,可以忽略。

def calc(n): sum_ = 0 for i in range(1,n+1): sum_ = sum_ + i return sum_def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_

上面例子中的T(n) = O(2n+1), 另一个 T(n) = O(2n² + n + 1),用大O表示法表示上面两段代码的时间复杂度,可以记为O(n),O(n²)。

算法A: O(n) 执行指令,10000*n

def calc(n): sum_ = 0 for i in range(1,n+1): sum_ = sum_ + I “”” 此处省略n行… … “”” return sum_

算法B: O(n²) 执行指令数,10*n2

对比上面两个算法,当 n = 10, n=100 时, 算法B执行的速度更快,n = 1000 时两者速度相当

n = 104 , n = 105, n = 106 ,算法A执行的速度更快的

随着数据规模的进一步增大, 这个差距会越来越大

时间复杂度分析

如何分析一段代码的时间复杂度?

在分析一个算法、一段代码的时间复杂度时,只关注循环执行次数最多的那一段代码就可以了。

def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_

上面的代码中,我们只需要关注内层for循环的时间复杂度就可以了,内层for循环的两行代码被执行了n2次,所以总的时间复杂度就是O(n²)

总复杂度等于量级最大的那段代码的复杂度

def calc(n): sum_ = 0 for i in range(1,n+1): sum_ = sum_ + i sum_1 = 0 for i in range(1,n+1): for j in range(n): sum_1 = sum_1 + i*j return sum_+sum_1

上面的代码分为两部分,分别是求 sum_、sum_1,计算sum_部分的代码段时间复杂度O(n),计算sum_1部分的代码段时间复杂度为O(n²) ,总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(n²)。

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

def fn(n): sum_ = 0 for i in range(n+1): sum_ = sum_ + i return sum_ def calc(n): sum_ = 0 for i in range(n+1): sum_ = sum_ + fn(i) return sum_

上面的代码中第二个函数调用了第一个函数, 如果把fn函数调用当作一个普通操作, 那么第二个函数的时间复杂度为O(n) Fn函数的时间复杂度为O(n),那么函数整体的时间复杂度为O(n*n) = O(n²)。

当两段代码的数据规模不同时,不能省略复杂度低的部分

def calc(n): sum_ = 0 for i in range(1,n+1): sum_ = sum_ + i sum_1 = 0 for i in range(1,m+1): for j in range(m): sum_1 = sum_1 + i*j return sum_+sum_1

上面的代码分为两部分,分别是求 sum_、sum_1,计算sum_部分的代码段时间复杂度O(n),计算sum_1部分的代码段时间复杂度为O(m2) ,总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(m²+n)

免责声明:文章内容来自互联网,本站仅作为分享,不对其真实性负责,如有侵权等情况,请与本站联系删除。
转载请注明出处:人工智能:怎样进行算法的复杂度分析? https://www.dachanpin.com/a/cyfx/11019.html

赞 (0)
人工智能:Django中提供的常用列表页选项
上一篇 2023-05-12 02:42:28
下一篇 2023-05-12 02:43:34

相关推荐

  • 青创+筑梦千里巡来乐 创业导师现场为企业把脉

      四川在线乐山讯 (记者 杨文彬) 今(15)日上午,由四川省大学生创新创业中心和乐山市人力资源和社会保障局主办,乐山市就业服务管理局承办的“青创+”筑梦千里巡之乐山巡诊暨第一届“天府杯”创业大赛乐山赛区动员会在乐山举行。来自省大学生创新创业中心的导师代表会带着丰富的创业经验和案例,为乐山的创业者拨开创业迷雾,指点发展迷津。   近年来,乐山市委、市政府把…

    创业分享 2023-05-22
  • 张其昌代表:加大创业创新力度助经济高质量发展

    张其昌代表:加大创业创新力度助经济高质量发展 “高质量发展如何推进、如何落实,备受关注。新经济形势下,创业者们面临着前所未有的机遇,也肩负着前所未有的使命。”张其昌代表认为,创业的质量,创新的速度,创客的格局,都将深刻影响着高质量发展的进程。“高质量发展要求高水平的创业创新,而高水平的创业创新,也意味着必须摆脱单纯的资本导向,更多关注需求、更多对接产业。”张…

    2023-05-13
  • 推动返乡创业高质量发展

    原标题:推动返乡创业高质量发展 本报北京2月7日讯 记者熊丽报道:近日,国家发展改革委、教育部、科技部等19个部门和单位印发《关于推动返乡入乡创业高质量发展的意见》。《意见》提出,进一步完善体制机制、创新政策举措、强化服务保障,不断优化创业环境、降低创业成本、提升创业带动就业能力,推动返乡入乡创业高质量发展。 《意见》提出,坚持市场主导、政府引导,统筹推进、…

    创业分享 2023-05-12
  • 恩施州就业创业政策解读新闻发布会实录

      肖  军 州公共就业和人才服务局副局长   一、当前就业形势   大家下午好。   谢谢大家。   发布单位:恩施州公共就业和人才服务局   答:创业贷款限制性行业主要有:房地产业、广告业、桑拿、按摩、网吧以及国家产业政策不予鼓励的其他企业   二是贷款额度提高。个体经营者贷款额度,从5万元提高到不超过10万元;组织起来合伙经营创业的,提高到按…

    创业分享 2023-05-31
  • 故乡小城的创业之光

        2016年春节期间,中宣部机关组织党员干部利用回乡探亲之机参加调研活动。春节回乡探亲的党员干部积极主动参加调研,通过多种方式了解体验基层,深入群众特别是农村、农民群众中,撰写了一批调研体会文章。中国文明网《新春走基层》专栏受权刊发。   我的故乡长治位于山西省东南部,古称“上党”“潞州”,历史悠久,今日是山西省第三大地级…

    创业分享 2023-06-04

发表回复

登录后才能评论

联系我们

在线咨询: QQ交谈

邮件:362039258@qq.com

工作时间:周一至周五,9:30-16:30,节假日休息