《算法设计与分析ch1.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析ch1.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、l ll70707070年代前年代前年代前年代前计算机科学基础的主题没有被清楚地认清计算机科学基础的主题没有被清楚地认清计算机科学基础的主题没有被清楚地认清计算机科学基础的主题没有被清楚地认清计算机科学基础的主题没有被清楚地认清计算机科学基础的主题没有被清楚地认清。l ll70707070年代年代年代年代KnuthKnuthKnuthKnuthKnuthKnuth出版了出版了出版了出版了出版了出版了The Art of Computer ProgrammingThe Art of Computer ProgrammingThe Art of Computer ProgrammingThe Ar
2、t of Computer ProgrammingThe Art of Computer ProgrammingThe Art of Computer Programming以算法研究为主线以算法研究为主线以算法研究为主线以算法研究为主线以算法研究为主线以算法研究为主线确立了算法为计算机科学基础的重要主题确立了算法为计算机科学基础的重要主题确立了算法为计算机科学基础的重要主题确立了算法为计算机科学基础的重要主题确立了算法为计算机科学基础的重要主题确立了算法为计算机科学基础的重要主题197419741974197419741974年获得图灵奖。年获得图灵奖。年获得图灵奖。年获得图灵奖。年获得图灵
3、奖。年获得图灵奖。l ll70707070年代后年代后年代后年代后算算算算算算法法法法法法作作作作作作为为为为为为计计计计计计算算算算算算机机机机机机科科科科科科学学学学学学核核核核核核心心心心心心推推推推推推动动动动动动了了了了了了计计计计计计算算算算算算机机机机机机科科科科科科学学学学学学技技技技技技术术术术术术飞飞飞飞飞飞速速速速速速发发发发发发展展展展展展l解决一个计算问题的过程解决一个计算问题的过程可计算否可计算否能行可计算否能行可计算否软件系统软件系统用计算机语言实现算法用计算机语言实现算法算法设计与分析算法设计与分析l可计算理论可计算理论计算模型计算模型计算模型计算模型可计算问题
4、可计算问题可计算问题可计算问题/不可计算问题不可计算问题不可计算问题不可计算问题计算模型的等价性计算模型的等价性计算模型的等价性计算模型的等价性-图灵图灵图灵图灵/ChurchChurchChurchChurch命题命题命题命题l计算复杂性理论计算复杂性理论在给定的计算模型下研究问题的复杂性在给定的计算模型下研究问题的复杂性l l固有复杂性固有复杂性固有复杂性固有复杂性l l上界上界上界上界l l下界下界下界下界l l平均平均平均平均l l复杂性问题的分类复杂性问题的分类复杂性问题的分类复杂性问题的分类:P=NP?P=NP?P=NP?P=NP?l l抽象复杂性研究抽象复杂性研究抽象复杂性研究抽
5、象复杂性研究l算法设计和分析算法设计和分析可计算问题的算法的设计与分析可计算问题的算法的设计与分析设计算法的理论、方法和技术设计算法的理论、方法和技术分析算法的理论、方法和技术分析算法的理论、方法和技术l计算机软件计算机软件系统软件系统软件工具软件工具软件应用软件应用软件l定义定义1.2.1(1.2.1(计算计算)可由一个给定计算模型机械地执行的规则或计可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算算步骤序列称为该计算模型的一个计算注意注意l l一个计算机程序是一个计算（计算模型是计算机）一个计算机程序是一个计算（计算模型是计算机）一个计算机程序是一个计算（计算模型
6、是计算机）一个计算机程序是一个计算（计算模型是计算机）l l计算可能永远不停止计算可能永远不停止计算可能永远不停止计算可能永远不停止不是算法不是算法不是算法不是算法l定义定义1.2.2(1.2.2(算法算法)算法是一个满足下列条件的计算：算法是一个满足下列条件的计算：l l有穷性有穷性有穷性有穷性/终止性：有限步内必须停止，终止性：有限步内必须停止，终止性：有限步内必须停止，终止性：有限步内必须停止，l l确定性：每一步都是严格定义和确定的动作，确定性：每一步都是严格定义和确定的动作，确定性：每一步都是严格定义和确定的动作，确定性：每一步都是严格定义和确定的动作，l l能行性：每一个动作都能够
7、被精确地机械执行，能行性：每一个动作都能够被精确地机械执行，能行性：每一个动作都能够被精确地机械执行，能行性：每一个动作都能够被精确地机械执行，l l输入：有一个满足给定约束条件的输入，输入：有一个满足给定约束条件的输入，输入：有一个满足给定约束条件的输入，输入：有一个满足给定约束条件的输入，l l输出：满足给定约束条件的结果。输出：满足给定约束条件的结果。输出：满足给定约束条件的结果。输出：满足给定约束条件的结果。最早的算法是欧几里德的最早的算法是欧几里德的最早的算法是欧几里德的最早的算法是欧几里德的“求最大公因子算法求最大公因子算法求最大公因子算法求最大公因子算法”直观地说，算法如下图所示
8、：直观地说，算法如下图所示：直观地说，算法如下图所示：直观地说，算法如下图所示：算法的目的是求解问题。什么是问题？算法的目的是求解问题。什么是问题？算法的目的是求解问题。什么是问题？算法的目的是求解问题。什么是问题？l定义定义1.2.3(1.2.3(问题问题)设设InputInput和和OutputOutput是是两两个个集集合合。一一个个问问题题是是一一个个关关系系R R InputInput OutputOutput，InputInput称称为为问问题题R R的的输输入入集集合合，InputInput的的每每个个元元素素称称为为R R的的一一个个输输入入，OutputOutput称称为为问
9、问题题R R的的输输出出或或结结果果集集合合，OutputOutput的每个元素称为的每个元素称为R R的一个结果的一个结果。注意注意l l问题定义了输入和输出的关系。问题定义了输入和输出的关系。问题定义了输入和输出的关系。问题定义了输入和输出的关系。例：例：SORTSORT问题定义如下：问题定义如下：l l输入集合输入集合输入集合输入集合Input=aInput=aInput=aInput=|a a a ai i i i是整数是整数是整数是整数 l l输出集合输出集合输出集合输出集合Output=bOutput=bOutput=bOutput=|b|b|b|bi i i i是整数是整数是整数
10、是整数,b b b b1 1 1 1 .b b b bn n n n l l问题问题问题问题SORT=(aSORT=(aSORT=(aSORT=(,)|)|)|)|Input,Input,Input,Input,bbb Output,aOutput,aOutput,aOutput,a1 1 1 1,a,a,a,an n n n=b=b=b=b1 1 1 1,b b b bn n n nl定义定义1.2.4(1.2.4(问题实例问题实例)问题问题P P的一个实例是的一个实例是P P的一个二元组。的一个二元组。注意注意l l一一一一个个个个算算算算法法法法面面面面向向向向一一一一个个个个问问问问题
11、题题题，而而而而不不不不是是是是仅仅仅仅求求求求解解解解一一一一个个个个问问问问题题题题的的的的一一一一个或几个实例。个或几个实例。个或几个实例。个或几个实例。l问题定义问题定义Input=Input=a a ai i是整数是整数 output=output=b b bi i是整数是整数,且且b b1 1.b bn n R=R=(a(,)a Input,bInput,output,output,a a1 1,.,a,.,an n=b b1 1,.,.,b bn n l算法的思想算法的思想扑克牌游戏扑克牌游戏A A 1,.,n1,.,n =5,2,4,6,1,35,2,4,6,1,3A A 1,
12、.,n1,.,n =5 5,2 2,4,6,1,3,4,6,1,3A A 1,.,n1,.,n =2,52,5,4 4,6,1,3,6,1,3A A 1,.,n1,.,n =2,4,5,2,4,5,6 6,1,3,1,3A A 1,.,n1,.,n =2,4,5,6,2,4,5,6,1 1,3,3A A 1,.,n1,.,n =1,2,4,5,6,1,2,4,5,6,3 3A A 1,.,n1,.,n =1,2,3,4,5,61,2,3,4,5,6l算法描述算法描述Insertion-Insertion-sort(Asort(A)Input:AInput:A 1,.,n1,.,n=n=n个数个
13、数output:Aoutput:A 1,.,n1,.,n=n=n个个sortedsorted数数FOR j=2 To n DoFOR j=2 To n Do keykeyA A j j;i ij-1j-1 WHILE i0 AND WHILE i0 AND A A i i key Dokey Do A A i+1i+1A A i i;i ii-1;i-1;A A i+1i+1key;key;l实例：实例：A A 1,.,n1,.,n=5,2,4,6,1,3=5,2,4,6,1,3 l定义定义1.3.1(1.3.1(算法正确性算法正确性)一一个个算算法法是是正正确确的的，如如果果它它对对于于每每
14、一一个个输输入入都都最终停止最终停止,而且产生正确的输出。而且产生正确的输出。不正确算法不正确算法不正确算法不正确算法：l l不停止不停止不停止不停止(在某个输入上在某个输入上在某个输入上在某个输入上)l l对所有输入都停止，但对某输入产生不正确结果对所有输入都停止，但对某输入产生不正确结果对所有输入都停止，但对某输入产生不正确结果对所有输入都停止，但对某输入产生不正确结果近似算法近似算法近似算法近似算法l l对所有输入都停止对所有输入都停止对所有输入都停止对所有输入都停止l l产生近似正确的解或产生不多的不正确解产生近似正确的解或产生不多的不正确解产生近似正确的解或产生不多的不正确解产生近似
15、正确的解或产生不多的不正确解l算法正确性证明算法正确性证明证明算法对所有输入都停止证明算法对所有输入都停止证明对每个输入都产生正确结果证明对每个输入都产生正确结果调试程序调试程序 程序正确性证明程序正确性证明:程序调试只能证明程序有错，程序调试只能证明程序有错，不能证明程序无错误不能证明程序无错误!l l目的：目的：预测算法对不同输入所需资源量预测算法对不同输入所需资源量预测算法对不同输入所需资源量预测算法对不同输入所需资源量l l复杂性测度：复杂性测度：时间，空间，时间，空间，时间，空间，时间，空间，I/OI/OI/OI/O等等等等,是输入大小的函数是输入大小的函数是输入大小的函数是输入大小
16、的函数l l用途：用途：为求解一个问题选择最佳算法、最佳设备为求解一个问题选择最佳算法、最佳设备为求解一个问题选择最佳算法、最佳设备为求解一个问题选择最佳算法、最佳设备l l需要的数学基础需要的数学基础离散数学，组合数学，概率论，代数等离散数学，组合数学，概率论，代数等离散数学，组合数学，概率论，代数等离散数学，组合数学，概率论，代数等l l需要的数学能力需要的数学能力建立算法复杂性的数学模型建立算法复杂性的数学模型建立算法复杂性的数学模型建立算法复杂性的数学模型数学模型化简数学模型化简数学模型化简数学模型化简l 定义定义1.3.2(1.3.2(输入的大小输入的大小)设设InputInput是
17、是问问题题R R的的输输入入集集合合，R R的的输输入入大大小小是是一个函数一个函数 F F：InputInputN N，N N是正整数集合。是正整数集合。示例：示例：l l矩阵问题的输入大小矩阵问题的输入大小矩阵问题的输入大小矩阵问题的输入大小=矩阵的维数矩阵的维数矩阵的维数矩阵的维数l l图论问题的输入大小图论问题的输入大小图论问题的输入大小图论问题的输入大小=图的边数图的边数图的边数图的边数/结点数结点数结点数结点数l定义定义1.3.31.3.3（时间复杂性）（时间复杂性）一个算法对特定输入的时间复杂性是该算一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的原子操作或法对该输入
18、产生结果需要的原子操作或“步步”数数注意注意l l时间复杂性是输入大小的函数时间复杂性是输入大小的函数l l我们假设每一步的执行需要常数时间，实我们假设每一步的执行需要常数时间，实际上每步需要的时间量可能不同。际上每步需要的时间量可能不同。l定义定义1.3.41.3.4（空间复杂性）（空间复杂性）一一个个算算法法对对特特定定输输入入的的空空间间复复杂杂性性是是该该算算法对该输入产生结果所需要的存储空间大小。法对该输入产生结果所需要的存储空间大小。l l定义定义1.3.51.3.5（最坏复杂性）（最坏复杂性）设设设设InputInputInputInput是是是是问问问问题题题题R R R R的
19、的的的输输输输入入入入集集集集合合合合，Complexity(XComplexity(XComplexity(XComplexity(X)是是是是求求求求解解解解R R R R的的的的算算算算法法法法A A A A的的的的复复复复杂杂杂杂性性性性函函函函数数数数，Size(ySize(ySize(ySize(y)是是是是确确确确定定定定R R R R中中中中输输输输入入入入大大大大小小小小的的的的函函函函数数数数，A A A A的最坏复杂性是的最坏复杂性是的最坏复杂性是的最坏复杂性是MaxMaxMaxMax Complexity(size(y)Complexity(size(y)Complex
20、ity(size(y)Complexity(size(y)y y y y InputInputInputInput l l定义定义1.3.51.3.5（最小复杂性）（最小复杂性）MinMin Complexity(size(y)Complexity(size(y)y y InputInput l l定义定义1.3.6 1.3.6（平均复杂性）（平均复杂性）设设设设yInput,yyInput,yyInput,yyInput,y作作作作为为为为算算算算法法法法A A A A的的的的输输输输入入入入出出出出现现现现的的的的概概概概率率率率是是是是p p p py y y y，A A A A的的的的平平平平均复杂性为均复杂性为均复杂性为均复杂性为