集团官网
  • 国家级全民数字素养与技能培训基地
  • 河南省第一批产教融合型企业建设培育单位
  • 郑州市数字技能人才(码农)培养评价联盟

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

编辑:云和数据 日期:2023-03-09 18:23

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

相关内容

抢先一步 鸿蒙(HarmonyOS)应用开发者高级认证 免费考! 适合人群计算机相关专业在校生(技师、中职、高职、本科、研究生)对鸿蒙(HarmonyOS)有兴趣的非计算机相关专业在校生目前正在从事移动应用的开发者目前正在从事计算机行业相关的人计算机专业高校老师所有对鸿蒙(HarmonyOS)有兴趣的人 培训方案掌握鸿蒙的核心概念和端云一体化开发、... 什么是Java的多态性(polymorphism)?它有哪些不同的形式? 多态性是Java面向对象编程的一个重要概念,它允许不同的对象以一致的方式响应同一个方法调用,具体表现为对象在运行时可以表现出多个不同的形态。多态性主要有两种不同的形式:编译时多态性(静态多态性)和运行时多态性(动态多态性)。1. 编译时多态性(静态多态性):   ... 如何学习和搭建Hadoop开发环境? Hadoop是大数据处理领域的重要平台,能够处理和分析大量数据。为了有效地利用Hadoop,我们需要学习其基础知识,并正确搭建开发环境。下面是详细的学习和搭建指南。一、学习Hadoop基础掌握基础概念和原理Hadoop主要由HDFS和MapReduce两部分组成。HDFS是分布式文件系统,Ma... UI 设计学习如何进阶成为高手 我总结了六种方法,帮助你走出舒适区,提高技能,成长为自信且经验丰富的UI设计高手一位经验丰富的 UI 设计师,往往十分看中应用程序界面的吸引力和视觉刺激,确保满足用户期望和需求。但是,如果你已经在 UI 设计圈摸爬滚打多年,仍然没有出色的作品,那你极有可能是因为陷入了一个舒适圈,UI技能一直原... 在Java中Executor和Executors的区别? 在Java中,Executor和Executors都与线程池和并发执行有关,但它们是不同的概念和类。1.ExecutorExecutor是一个接口,位于java.util.concurrent包中,用于表示一个执行任务的执行器。它只定义了一个方法:void execute(Runnable c... String类型的常见命令有哪些? String类型,也就是字符串类型,是Redis中最简单的存储类型。其value是字符串,不过根据字符串的格式不同,又可以分为3类:string是普通字符串,int整数类型,可以做自增、自减操作,float浮点类型,可以做自增、自减操作。String的常见命令有:SET:添加或者修改已经存在的...