第1章 算法概述

本文格式为Word版，下载可任意编辑——第1章算法概述

算法分析与设计课件

算法分析与设计DesignandAnalysisofComputerAlgorithm

教材：计算机算法设计与分析(教材：计算机算法设计与分析(第3版)算法设计与分析王晓东编著

算法分析与设计课件

课程简介算法分析与设计是计算机的核心课程之一，算法分析与设计是计算机的核心课程之一，在众多的计算机系统软件和应用软件中都要用到本课程的内容。算机系统软件和应用软件中都要用到本课程的内容。它是操作系统、编译原理等课程的先行课程，作系统、编译原理等课程的先行课程，在计算机的理论体系中占有极其重要的位置。中占有极其重要的位置。通过本课程的学习，通过本课程的学习，使学生把握算法分析与设计的基本理论，使学生学会算法分析与设计的基本方法,把握把握计算机科理论，使学生学会算法分析与设计的基本方法把握计算机科学及应用领域常见的有代表性的非数值算法及算法设计的若干重要方法，并学会用这些算法解决实际问题。干重要方法，并学会用这些算法解决实际问题。本课程以算法设策略略为知识单元，本课程以算法设策略略为知识单元，介绍算法设计方法和分析技巧，这些策略包括递归技术、分治、动态规划、贪和分析技巧，这些策略包括递归技术、分治、动态规划、心算法、回溯法、分支限界法等策略，它们的内容相对独立。心算法、回溯法、分支限界法等策略，它们的内容相对独立。其先修课为高等数学、程序设计、数据结构。其先修课为高等数学、程序设计、数据结构。

算法分析与设计课件

本课程主要内容第1章算法概述第2章第3章第4章第5章第6章递归与分治策略动态规划贪心算法回朔法分支限界法

算法分析与设计课件

第1章算法概述学习要点:学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。把握算法的计算繁杂性概念。把握算法渐近繁杂性的数学表述。

算法分析与设计课件

软件(software):程序及其各种文档资料的总称程序(algorithm)=算法+数据结构算法(procedure):解的描述(程序的灵魂)数据结构(datastructure):现实世界的数据模型语言(language):实现的工具

算法分析与设计课件

算法(Algorithm)算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入输入：有外部提供的量作为算法的输入。输入(2)输出输出：算法产生至少一个量作为输出。输出(3)确定性确定性：组成算法的每条指令是明了，无歧义的。确定性(4)有限性有限性：算法中每条指令的执行次数是有限的，执有限性行每条指令的时间也是有限的。

算法分析与设计课件

程序(Program)程序(Program)程序是算法

用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性有限性。有限性例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

算法分析与设计课件

算法的描述方法自然语言––––优点：简单理解缺点：冗长、二义性使用方法：粗线条描述算法思想本卷须知：避免写成自然段

欧几里德算法：①输入m和n;②求m除以n的余数r;③若r等于0,则n为最大公约数，算法终止；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。

算法分析与设计课件

流程图––––优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法本卷须知：注意抽象层次开始输入m和nr=m%nr=0Nm=n;n=r输出n终止Y

欧几里德算法：

算法分析与设计课件

程序设计语言––––优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证本卷须知：将算法写成子函数intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}

欧几里德算法：#includeiostream.h

算法分析与设计课件

伪代码介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。–优点：表达能力强、抽象性强、简单理解

欧几里德算法：1.r=m%n;2.循环直到r=0;2.1m=n;2.2n=r;2.3r=m%n;3.输出n;

算法分析与设计课件

问题的求解(ProblemSolving):问题的求解(ProblemSolving):1)问题的陈述用科学规范的语言,对所求解的问题做确凿的描述.用科学规范的语言,对所求解的问题做确凿的描述.

2)建立数学模型通过对问题的分析,通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述.的关系并用数学语言加以描述.

3)算法设计根据数学模型设计问题的计算机求解算法.根据数学模型设计问题的计算机求解算法.

4)算法的正确性证明证明算法对一切合法输入均能在有限次计算后产生正确输出.证明算法对一切合法输入均能在有限次计算后产生正确输出.

5)算法的程序实现将算法正确地编写成机器语言程序.将算法正确地编写成机器语言程序.

6)算法分析对执行该算法所消耗的计算机资源进行估算.对执行该算法所消耗的计算机资源进行估算.

算法分析与设计课件

算法设计的要求寻常设计一个“好〞的算法应考虑达到以下目标：正确性：4个层次可读性：有助于对算法的理解(结构化、模块化、加解释等)顽强性：输入数据非法，作出适

当反应或进行处理高效率与低存储要求：效率是指算法执行的时间

算法分析与设计课件

算法分析算法分析(Analysis):):对算法所需要的算法分析(AlgorithmAnalysis):对算法所需要的两种计算机资源————时间和空间进行估算两种计算机资源——时间和空间进行估算时间繁杂性(TimeComplexity)时间繁杂性(Complexity)空间繁杂性(Complexity)空间繁杂性(SpaceComplexity)算法分析的目的：算法分析的目的：设计算法————设计出繁杂性尽可能低的算法设计算法——设计出繁杂性尽可能低的算法选择算法————在多种算法中选择其中繁杂性最低者选择算法——在多种算法中选择其中繁杂性最低者

算法分析与设计课件

算法繁杂性分析算法繁杂性=算法所需要的计算机资源算法的时间繁杂性T(n);算法的空间繁杂性S(n)。是问题的规模(输入大小)。其中n是问题的规模(输入大小)。

算法分析与设计课件

算法的时间繁杂性(1)最坏状况(Worstcase)下的时间繁杂性最坏状况(最坏状况

Tmax(n)=max{T(I)|size(I)=n}

最好状况((2)最好状况(Bestcase)下的时间繁杂性最好状况

Tmin(n)=min{T(I)|size(I)=n}

(3)平均状况(Averagecase)下的时间繁杂性平均状况(平均状况

Tavg(n)=

size(I)=n

∑p(I)T(I)

其中I是问题的规模(inputsize)为n的实例，p(I)是实例I出现的概率。

算法分析与设计课件

例：顺序探寻算法在具有n个元素的数组a[1...n]中找出值等于的元素的位置。中找出值等于k的元素的位置在具有个元素的数组的数组中找出值等于的元素的位置。templateclassTypeintseqSearch(Type*a,intn,Typek){for(inti=0;in;i++)if(a[i]==k)returni;return-1;}

算法分析与设计课件

(1)Tmax(n)=max{T(I)|size(I)=n}=n(2)Tmin(n)=min{T(I)|size(I)=n}=1(3)在平均状况下，假设：(a)探寻成功的概率为p(0≤p≤1);(b)在数组的每个位置i(0≤in)探寻成功的概率一致，均为

p/n。

Tavg(n)=

size(I)=n

∑p(I)T(I)

pppp=1+2+3+L+n+n(1p)nnnn

pn(1p)=p(n+1)+n(1p)=∑i+nni=12

算法分析与设计课件

算法渐近繁杂性设T(n)为算法A的时间繁杂性函数,则它是n的单增函数,假使存在为算法A的时间繁杂性函数,的单增函数,一个函数(n)使得当n→∞,有T(n)-(n))/T(n)→0时的渐进性态或渐进繁杂性。称(n)是T(n)当n→∞时的或在数学上,有一致的最高阶项.为略去T(在数学上,T(n)与(n)有一致的最高阶项.可取(n)为略去T(n)的低阶项后剩余的主项.代替T(低阶项后剩余的主项.当n充分大时我们用(n)代替T(n)作为算法复杂性的度量,从而简化分析.杂性的度量,从而简化分析

.例如T(n)=3n2+4nlogn+7,则(n)可以是3n2.3n

若进一步假定算法中所有不同元运算的单位执行时间一致,则可不若进一步假定算法中所有不同元运算的单位执行时间一致,考虑(n)所包含的系数或常数因子。(所包含的系数或常数因子。渐进分析适用于n充分大的状况,当问题的规模很小时,渐进分析适用于n充分大的状况,当问题的规模很小时,或比较的两算法同阶时,则不能做这种简化.算法同阶时,则不能做这种简化.

算法分析与设计课件

Meaning:foralldatasetsbig渐近繁杂性分析的记号enough(i.e.,nn0),thealgorithmalwaysexecutesinlessthanC|g(n)|在下面的探讨中，对所有n,f(n)≥0,g(n)≥0。(1)渐近上界记号O(Big-O)渐近上界记号O渐近上界记号)若存在正常数c和自然数若存在正常数和自然数n0使得当和自然数n≥n0时，有0≤f(n)≤cg(n)≥充分大时有上则称函数f(n)在n充分大时有上在充分大时有界,且g(n)是它的一个上界,记为f(n)=O(g(n)),也称f(n)的阶不高于g(n)的阶。cg(n)RunningTime

f(n)

n0

InputSize

算法运行时间的上限算法运行时间的上限上界的阶越低，则评估就越确切，结果就越有价上界的阶越低，则评估就越确切，上界的阶越低T(n)=值。例：T(n)=3n2,T(n)=O(n2),而n2=取前者。O(n3),取前者。

算法分析与设计课件

举例：例1:f(n)=2n+3=O(n)当n≥3时，2n+3≤3n,所以，可选=3,n0=3。对于时，所以，可选c,。对于n≥n0,f(n),=2n+3≤3n,所以，f(n)=O(n),即2n+3∈O(n)。这意味着，,所以，,∈。这意味着，的程序步不会超过3n,当n≥3时，程序的程序步不会超过，2n+3=O(n)。时程序2-1的程序步不会超过。例2:f(n)=10n2+4n+2=O(n2)对于n≥2时，有10n2+4n+2≤10n2+5