计算机算法 设计与分析 信息工程学院周经野 电话:8292350 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 计算机算法 设计与分析 信息工程学院周经野 电话：8292350
第一章 算法述 2021/2/21 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 第一章 算法概述
算法与过程 ■过程( Procedure)与算法( Algorithm)是解决问题 的一种方法的逐步描述,它 (1)是由若干条指令组成的有穷序列 ■(2)每条指令的意义都是确定的; (3)具有零个或多个输入; (4)产生若干个输出; 算法要求其(5)执行时间是有限的(终止性)。 ■过程的执行时间可能是无限的。 2021/221 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 算法与过程 ◼ 过程(Procedure)与算法(Algorithm)是解决问题 的一种方法的逐步描述，它 ◼ (1)是由若干条指令组成的有穷序列； ◼ (2)每条指令的意义都是确定的； ◼ (3)具有零个或多个输入； ◼ (4)产生若干个输出； ◼ 算法要求其(5)执行时间是有限的 (终止性) 。 ◼ 过程的执行时间可能是无限的
程序 ■程序是某个算法或过程的在计算机上的 个具体的实现 ■程序是依赖于程序设计语言的,甚至依 赖于计算机结构的 ■算法是脱离具体的计算机结构和程序设 计语言的。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 程序 ◼ 程序是某个算法或过程的在计算机上的 一个具体的实现。 ◼ 程序是依赖于程序设计语言的，甚至依 赖于计算机结构的。 ◼ 算法是脱离具体的计算机结构和程序设 计语言的
算法的复杂性 ■算法的复杂性是指算法运行时所需要的 计算机资源的量多少,所需资源量越多 则复杂性越髙,反之所需资源量越少则 复杂性越低。其中最为重要的是: ˉ时间复杂性:需要时间的资源量 ■空间复杂性:需要空间的资源量。 ■这里人们通常更为关注的是时间复杂性。 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 算法的复杂性 ◼ 算法的复杂性是指算法运行时所需要的 计算机资源的量多少，所需资源量越多 则复杂性越高，反之所需资源量越少则 复杂性越低。其中最为重要的是： ◼ 时间复杂性：需要时间的资源量。 ◼ 空间复杂性：需要空间的资源量。 ◼ 这里人们通常更为关注的是时间复杂性