怎样进行算法的复杂度分析?

复杂度分析是估算算法执行效率的方法,公式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/11021.html

赞 (0)
上一篇 2023-05-12 02:42:54
苹果2024将推出无接口设计的iPhone?
下一篇 2023-05-12 02:43:59

相关推荐

  • 巨丰访谈:创业板指创近3年来新高 下周大盘将如何走?

    原标题:巨丰访谈:创业板指创近3年来新高 下周大盘将如何走?   鼠年开市首日逾三千只个股跌停后,随后几日大盘上演罕见“抗疫”行情,、恒大、保利发展、等房企上线在线售房小程序,开辟线上售房新市场,、、、、通讯以及数字农业概念构成利好,以上领域的龙头股有望冲锋。   2、在2019年也不例外,为什么?   答:传媒、医药、计算机行业近年来一直是9价格下调意在吸…

    创业分享 2023-05-12
  • 成功创业经验分享,硅藻泥创业必看

    二、选择顺应趋势,有发展潜力的品牌 天然居作为一个有持续发展能力的品牌绝不会跟在别人背后亦步亦趋。天然居走差异化道路与别的品牌形成市场区隔,让竞争对手无从跟随,最终拥有更强的生命力,更高的市场价值! 硅藻泥行业虽然发展了将近十年,但行业为消费者熟知的知名品牌才能称之为渠道品牌。天然居硅藻泥被评为硅藻泥行业十大品牌,品牌实力强势。为加盟商的支持力度会更大,会更…

    创业分享 2023-06-01
  • 陆旭总领事出席加中商会创新创业路演开幕式

          陆总领事表示,总领馆不仅大力支持路演,还积极联系浙江省科技厅、浙江清华长三角研究院、河南国际技术转移中心作为本次活动支持单位。这意味着参赛获奖选手将有机会与国内相关单位合作甚至获得投资。陆总领事鼓励参赛选手将本次路演当做一次真正商业“实战”机会,并从技术和商业转化角度不断完善创新设计,积极培养企业…

    创业分享 2023-05-18
  • 怎么加盟全屋整装?皇者集成墙饰手把手带你创业

    皇者集成墙饰是一个非常有核心竞争力的集成墙饰品牌,很多加盟商们对于以下两个问题是非常关心的。怎么加盟皇者集成墙饰?皇者集成墙饰加盟条件是什么?总的来说,加盟皇者墙饰是有非常多的途径的,而且皇者墙饰对于加盟商的一些条件要求并不算高,是一个比较不错的投资项目。959 加盟皇者集成墙饰有哪些条件呢?总的来说,皇者集成墙饰品牌对于各个加盟商的一些条件要求并不算非常的…

    创业分享 2023-06-06
  • 中原工学院信息商务学院创新创业大讲堂开讲

    12月8日,中原工学院信息商务学院创新创业大讲堂在该院主校区学术报告厅正式开讲。第一讲特邀河南省虚拟现实(VR)产业联盟成员单位、郑州好玩软件科技有限公司市场部总监丁龙高级工程师作了题为《VR技术的应用及发展前景》的专题报告。 丁龙通过现阶段国家提倡的“互联网+”及“VR+”的政策,围绕现代大学生高薪就业的理念,就目前VR的火爆,主要针对VR技术和VR在生活…

    2023-05-27

发表回复

登录后才能评论

联系我们

在线咨询: QQ交谈

邮件:362039258@qq.com

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