程序设计算法分析--1

1、主讲：张小红 授课班级：物联网13级授课时间：1-16周电话Q：447973560数据结构数据结构(C(C语言版语言版) )。严蔚敏，吴伟民。严蔚敏，吴伟民 编编 著。清华大学出版著。清华大学出版社。社。参考文献参考文献 1.1.张小艳张小艳. .数据结构与算法数据结构与算法. .中国矿业大学出版社。中国矿业大学出版社。 2. 2.数据结构习题与解析数据结构习题与解析(C(C语实言版语实言版) )。李春葆。李春葆。 清华大学出版社。清华大学出版社。成绩成绩：平时成绩：平时成绩+ +上机成绩上机成绩+ + 期中成绩期中成绩+ +期末成绩期末成绩 上课：迟到上课：迟到-诗

2、歌朗诵、第一排诗歌朗诵、第一排交一次作业交一次作业 1.算法2.线性结构 2.1线性表 2.2栈 2.3队列 2.4数组 2.5串3.非线性结构 3.1树 3.2图4.查找5.排序 目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于于科学计算科学计算，而更多的是用于控制，管理及数据处理等，而更多的是用于控制，管理及数据处理等非数值计算非数值计算领域。计领域。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的题：信息的表示表示，信息

3、的，信息的处理处理。 信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题数据结构这门课所要研究的问题。编写解决实际问题的程序的一般过程编写解决实际问题的程序的一般过程：

4、如何用数据形式描述问题如何用数据形式描述问题? ?即由问题抽象出一个适当的数学即由问题抽象出一个适当的数学模型模型; ; 问题所涉及的问题所涉及的数据量大小及数据之间的关系数据量大小及数据之间的关系; ; 如何在计算机中存储数据及如何在计算机中存储数据及体现数据之间的关系体现数据之间的关系? ? 处理问题时需要对数据作何种处理问题时需要对数据作何种运算运算? ? 所编写的程序的所编写的程序的性能性能是否良好是否良好? ?上面所列举的问题基本上由数据结构这门课程来回答。上面所列举的问题基本上由数据结构这门课程来回答。计算机求解问题的一般步骤计算机求解问题的一般步骤 数据结构数据结构是计算机科学中

5、的一门综合性专业基是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。统程序和大型应用程序的重要基础。姓名姓名电话号码电话号码陈海陈四锋李四例例1 1：电话号码查询系统：电话号码查询系统 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N

6、N个人的名字和其个人的名字和其相应的电话号码，假定按如下形式安排：相应的电话号码，假定按如下形式安排：(a(a1 1, b, b1 1) )，(a(a2 2, , b b2 2) )，(a(an n, b, bn n) )，其中其中a ai i, b, bi i(i=1(i=1，2n)2n) 分别表示某人分别表示某人的名字和电话号码。的名字和电话号码。 本问题是一种典型的表格问题本问题是一种典型的表格问题。如表如表1-11-1，数据与数据成简单的一对一的，数据与数据成简单的一对一的线性关系线性关系。表表1-11-1线性表结线性表结构构例例2 2：磁盘目录文件系统：磁盘目录文件系统 磁盘根目录下

7、有很多子目录磁盘根目录下有很多子目录及文件，每个子目录里又可以包及文件，每个子目录里又可以包含多个子目录及文件，但每个子含多个子目录及文件，但每个子目录只有一个父目录，依此类推目录只有一个父目录，依此类推： 本问题是一种典型的树型本问题是一种典型的树型结构问题，如图结构问题，如图1-11-1 ，数据与数，数据与数据成一对多的关系，是一种典型据成一对多的关系，是一种典型的非线性关系结构的非线性关系结构树形结构树形结构。树形树形例例3 3：交通网络图：交通网络图 从一个地方到另外一个地方可以有多条路径。本问从一个地方到另外一个地方可以有多条路径。本问题是一种典型的题是一种典型的网状结构网状结构问题

8、，数据与数据成多对多的问题，数据与数据成多对多的关系，是一种非线性关系结构。关系，是一种非线性关系结构。佛山惠州广州中山东莞深圳珠海图图1-21-2 网状结构网状结构 数据数据(Data) (Data) ：是客观事物的符号表示。在计算机科：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。的符号的总称。 数据元素数据元素(Data Element) (Data Element) ：是数据的基本单位，：是数据的基本单位，在程序中通常在程序中通常作为一个整体作为一个整体来进行考虑和处理。来进行考虑和处理。

9、一个数据元素可由若干个一个数据元素可由若干个数据项数据项(Data Item)(Data Item)组成。组成。数据项是数据的不可分割的最小单位。数据项是对客观数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。事物某一方面特性的数据描述。 数据对象数据对象(Data Object)(Data Object)：是性质相同的数据元素的：是性质相同的数据元素的集合，是数据的一个子集。如字符集合集合，是数据的一个子集。如字符集合C=C=A A, ,B B, ,C,C, 。 数据结构数据结构(Data Structure)(Data Structure)：是：是指相互之间具有指

10、相互之间具有( (存存在在) )一定一定联系联系( (关系关系) )的的数据元素数据元素的集合。元素之间的相互的集合。元素之间的相互联系联系( (关系关系) )称为称为逻辑结构逻辑结构。数据元素之间的逻辑结构有。数据元素之间的逻辑结构有四种基本类型，如图四种基本类型，如图1-31-3所示。所示。 集合集合：结构中的数据元素除了：结构中的数据元素除了“同属于一个集合同属于一个集合”外，没有其它关系。外，没有其它关系。 线性结构：线性结构：结构中的数据元素之间存在一对一的结构中的数据元素之间存在一对一的关系。关系。 树型结构树型结构：结构中的数据元素之间存在一对多的：结构中的数据元素之间存在一对多

11、的关系。关系。 图状结构或网状结构：图状结构或网状结构：结构中的数据元素之间存结构中的数据元素之间存在多对多的关系。在多对多的关系。 数据结构的形式定义是一个二元组：数据结构的形式定义是一个二元组： Data-Structure=(DData-Structure=(D，S)S)其中：其中：D D是数据是数据元素元素的有限集，的有限集，S S是是D D上上关系关系的有限集。的有限集。例例2 2：设数据逻辑结构：设数据逻辑结构B=B=（K K，R R） K=kK=k1 1, k, k2 2, , , k, k9 9 R= k R= ，k ，k ，k ，k ，k ，k ，k ，k ，k ，k 出出这

12、逻辑结构的图示，并确定那些是起点，那些是终点这逻辑结构的图示，并确定那些是起点，那些是终点图图1-31-3四类基本四类基本 数据结构在计算机内存中的存储包括数据结构在计算机内存中的存储包括数据元素的数据元素的存储存储和和元素之间的关系的表示元素之间的关系的表示。 元素之间的关系在计算机中有两种不同的表示方元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储法：顺序表示和非顺序表示。由此得出两种不同的存储结构：结构：顺序存储结构顺序存储结构和和链式存储结构链式存储结构。 顺序存储结构顺序存储结构：用数据元素在存储器中的相对位置来表示数：用数据元素在存储器中的

13、相对位置来表示数据元素之间的逻辑结构据元素之间的逻辑结构( (关系关系) )。 数据元素之间的关系可以是元素之间代表某种含数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义义的自然关系，也可以是为处理问题方便而人为定义的关系，这种的关系，这种自然或人为定义的自然或人为定义的 “关系关系”称为数据元称为数据元素之间的素之间的逻辑关系逻辑关系，相应的，相应的结构结构称为称为逻辑结构逻辑结构。 链式存储结构：链式存储结构：在每一个数据元素中增加一个存放另一个元在每一个数据元素中增加一个存放另一个元素地址的指针素地址的指针(pointer )(pointer )，

14、用该指针来表示数据元素之间的逻辑，用该指针来表示数据元素之间的逻辑结构结构( (关系关系) )。例：例：设有数据集合设有数据集合A=3.0,2.3,5.0,-8.5,11.0 A=3.0,2.3,5.0,-8.5,11.0 ，两种，两种不同的存储结构。不同的存储结构。 顺序结构：数据元素存放的地址是连续的顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续没有要求。链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面，数据的逻辑结构和物理结构是密不可分的两个方面，一个一个算法的设计取决于算法的设计取决于所选定的所选定的逻辑结构逻辑

15、结构，而，而算法的实算法的实现依赖于现依赖于所采用的所采用的存储结构存储结构。 在在C C语言中，用语言中，用一维数组一维数组表示顺序存储结构表示顺序存储结构；用用结结构体类型构体类型表示链式存储结构。表示链式存储结构。数据结构的三个组成部分：数据结构的三个组成部分：逻辑结构逻辑结构： 数据元素之间逻辑关系的描述数据元素之间逻辑关系的描述 D_S=D_S=（D D，S S）存储结构存储结构： 数据元素在计算机中的存储及其逻辑数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。关系的表现称为数据的存储结构或物理结构。数据操作数据操作： 对数据要进行的运算。对数据要进行的运算。

16、 本课程中将要讨论的三种逻辑结构及其采用的存本课程中将要讨论的三种逻辑结构及其采用的存储结构如图储结构如图1-41-4所示。所示。数据的逻辑结构数据的逻辑结构非线性结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5数据逻辑结构层次关系数据逻辑结构层次关系图图图图1-41-4 逻辑结构与所采用的存储结逻辑结构与所采用的存储结构构线性表线性表树树图图顺序存储结构顺序存储结构链式存储结构链式存储结构复合存储结构复合存储结构逻辑结构逻辑结构物理结构物理结构 数据类型数据类型(Data Type)(Data Type)：指

17、的是：指的是一个值的集合一个值的集合和和定义在定义在该值集上的一组操作该值集上的一组操作的总称。的总称。 数据类型是和数据结构密切相关的一个概念。数据类型是和数据结构密切相关的一个概念。 在在C C语言中数据类型有：语言中数据类型有：基本类型和构造类型基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象，数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。象各元素之间的相互关系。 数据结构的主要运算包括：数据结构的主要运算包括： 建立建立(Create)(Create)一个数

18、据结构；一个数据结构； 消除消除(Destroy)(Destroy)一个数据结构；一个数据结构； 从一个数据结构中删除从一个数据结构中删除(Delete)(Delete)一个数据元素；一个数据元素； 把一个数据元素插入把一个数据元素插入(Insert)(Insert)到一个数据结构中；到一个数据结构中； 对一个数据结构进行访问对一个数据结构进行访问(Access)(Access)； 对一个数据结构对一个数据结构( (中的数据元素中的数据元素) )进行修改进行修改(Modify)(Modify)； 对一个数据结构进行排序对一个数据结构进行排序(Sort)(Sort)； 对一个数据结构进行查找对一

19、个数据结构进行查找(Search)(Search)。 抽象数据类型抽象数据类型( (Abstract Data TypeAbstract Data Type ，简称，简称ADTADT) )：是指一个数学模型以及定义在该模型上的一组操作。是指一个数学模型以及定义在该模型上的一组操作。 ADTADT的定义仅是一组逻辑特性描述，的定义仅是一组逻辑特性描述， 与其在计与其在计算机内的表示和实现无关。因此，不论算机内的表示和实现无关。因此，不论ADTADT的内部结构的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。如何变化，只要其数学特性不变，都不影响其外部使用。 ADTADT的形式化定义是三

20、元组：的形式化定义是三元组：ADT=(DADT=(D，S S，P)P)其中：其中：D D是是数据对象数据对象，S S是是D D上的上的关系集关系集，P P是对是对D D的的基基本操作集本操作集。ADTADT的一般定义形式是：的一般定义形式是：ADT ADT 数据对象：数据对象： 数据关系：数据关系： 基本操作：基本操作： ADT ADT 其中数据对象和数据关系的定义用伪码描述。其中数据对象和数据关系的定义用伪码描述。 基本操作的定义是：基本操作的定义是： ()初始条件：初始条件： 操作结果：操作结果： 初始条件：描述操作执行之前数据结构和参数应初始条件：描述操作执行之前数据结构和参数应满足的条

21、件满足的条件; ;若不满足，则操作失败，返回相应的出若不满足，则操作失败，返回相应的出错信息。错信息。 操作结果：描述操作正常完成之后，数据结构的操作结果：描述操作正常完成之后，数据结构的变化状况和变化状况和 应返回的结果。应返回的结果。1.3.11.3.1 算法算法算法算法(Algorithm)(Algorithm)：是对特定问题求解方法：是对特定问题求解方法( (步骤步骤) )的一种的一种描述，是指令的有限序列，其中每一条指令表示一个或描述，是指令的有限序列，其中每一条指令表示一个或多个操作。多个操作。算法具有以下五个特性算法具有以下五个特性 有穷性有穷性： 一个算法必须总是在执行有穷步之

22、后结束，且每一一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。步都在有穷时间内完成。 确定性确定性：算法中每一条指令必须有确切的含义。不存在二义：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。性。且算法只有一个入口和一个出口。 可行性可行性： 一个算法是能行的。即算法描述的操作都可以通过一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。已经实现的基本运算执行有限次来实现。 输入输入： 一个算法有零个或多个输入，这些输入取自于某个一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。特定的对象集合。 输出输出：

23、 一个算法有一个或多个输出，这些输出是同输入有一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。着某些特定关系的量。 一个算法可以用多种方法描述，主要有：使用自一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计然语言描述；使用形式语言描述；使用计算机程序设计语言描述。语言描述。 算法和程序是两个不同的概念算法和程序是两个不同的概念。一个计算机程序。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。必须可终止意味着不是所有的计算机程序都是

24、算法。 在本门课程的学习、作业练习、上机实践等环节，在本门课程的学习、作业练习、上机实践等环节，算法都用算法都用C C语言来描述。在上机实践时，为了检查算法语言来描述。在上机实践时，为了检查算法是否正确，应编写成完整的是否正确，应编写成完整的C C语言程序。语言程序。程序是指令步骤的集合。C语言程序。如： #include void main( ) printf (This is a C program.n); main-主函数名， void-函数类型每个C程序必须有一个主函数main 是函数开始和结束的标志,不可省每个C语句以分号结束使用标准库函数时应在程序开头一行写： #include #

25、include void main( ) /* 主函数*/ int max(int x,int y); / 对被调用函数max的声明 */ int a, b, c; /*定义变量a、b、c */ scanf(d,d,&a,&b); /*输入变量a和b的值*/ c=max(a,b); /*调用max函数,将得到的值赋给c */ printf(max=dn,c);int max(int x, int y) int max(int x, int y) int z; int z; if (xy) z=x; if (xy) z=x; else z=y; else z=y; return

26、(z); return (z); 本程序包括main和被调用函数max两个函数。max函数的作用是将x和y中较大者的值赋给变量z。return语句将z的值返回给主调函数main。C语言提供了以下一些数据类型。 评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准 正确性正确性( (CorrectnessCorrectness ) )： 算法应满足具体问题的需求。算法应满足具体问题的需求。 可读性可读性( (ReadabilityReadability) )： 算法应容易供人阅读和交流。可读性好的算算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。法有助于对算法的理解和修

27、改。 健壮性健壮性( (RobustnessRobustness) )： 算法应具有容错处理。当输入非法或错误数算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。出结果。 通用性通用性( (GeneralityGenerality) )： 算法应具有一般性算法应具有一般性 ，即算法的处理结果对于，即算法的处理结果对于一般的数据集合都成立一般的数据集合都成立。 效率与存储量需求效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算效率指的是算法执行的时间；存储量需求指算法

28、执行过程中所需要的最大存储空间。一般地，这两者与问题的规法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。模有关。 算法执行时间需通过依据该算法编制的程序在计算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：算机上运行所消耗的时间来度量。其方法通常有两种：事后统计事后统计：计算机内部进行执行时间和实际占用空间的：计算机内部进行执行时间和实际占用空间的统计。统计。 问题：必须先运行依据算法编制的程序；依赖软问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。硬件环境，容易掩盖算法本身的优劣；没有实际价值

29、。事前分析事前分析：求出该算法的一个时间界限函数。：求出该算法的一个时间界限函数。与此相关的因素有：与此相关的因素有： 依据算法选用何种依据算法选用何种策略策略； 问题的问题的规模规模； 程序设计的程序设计的语言语言； 编译程序所产生的编译程序所产生的机器代码机器代码的质量；的质量； 机器执行指令的机器执行指令的速度速度； 撇开软硬件等有关部门因素，可以认为一个特定算撇开软硬件等有关部门因素，可以认为一个特定算法法“运行工作量运行工作量”的大小，只依赖于问题的规模（通的大小，只依赖于问题的规模（通常用常用n n表示），或者说，它表示），或者说，它是问题规模的函数是问题规模的函数。 算法中算法中

30、基本操作重复执行的次数基本操作重复执行的次数是问题规模是问题规模n n的某个函数，的某个函数，其时间量度记作其时间量度记作 T(n)=O(f(n)T(n)=O(f(n)，称作算法的渐近时间复杂度，称作算法的渐近时间复杂度( (Asymptotic Time complexityAsymptotic Time complexity) )，简称，简称时间复杂度时间复杂度。 一般地，常用一般地，常用最深层循环内最深层循环内的语句中的原操作的的语句中的原操作的执行频度执行频度( (重复执行的次数重复执行的次数) )来表示。来表示。 表示表示时间复杂度时间复杂度的阶有：的阶有： O(1) O(1) ：常

31、量时间阶：常量时间阶 O (n)O (n)：线性时间阶：线性时间阶 O(O(n)n) ：对数时间：对数时间阶阶 O(nO(nn) n) ：线性对数时间阶：线性对数时间阶 O (n O (nk k) )： k k2 2 ，k k次方时间阶次方时间阶 例例 两个两个n n阶方阵的乘法阶方阵的乘法 for(i=1for(i=1，i=n; +i)i=n; +i) for(j=1; j=n; +j) for(j=1; j=n; +j) cij=0 ; cij=0 ; for(k=1; k=n; +k) for(k=1; k=n; +k) cij+=aik cij+=aik* *bkj ; bkj ; 由

32、于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1 1到到n n，则总次数为：，则总次数为： n nn nn=nn=n3 3时间复杂度为时间复杂度为T(n)=O(nT(n)=O(n3 3) )例例 +x; s=0 ;+x; s=0 ; 将将x x自增看成是基本操作，则语句频度为，即时间复杂度自增看成是基本操作，则语句频度为，即时间复杂度为为(1) (1) 。如果将如果将s=0s=0也看成是基本操作，则语句频度为，其时也看成是基本操作，则语句频度为，其时间复杂度仍为间复杂度仍为(1)(1)，即常量阶。，即常量阶。例例 for(i=1; i=n; +i)for(i=1; i=n; +i)

33、 +x; s+=x ; +x; s+=x ; 语句频度为：语句频度为：2n2n，其时间复杂度为：，其时间复杂度为：O(n) O(n) ，即为线性，即为线性阶。阶。例例 for(i=1; i=n; +i)for(i=1; i=n; +i)for(j=1; j=n; +j)for(j=1; j=n; +j) +x; s+=x ; +x; s+=x ; 语句频度为：语句频度为：2n2n2 2 ，其时间复杂度为：，其时间复杂度为：O(nO(n2 2) ) ，即为，即为平方阶。平方阶。 定理定理：若若A(n)=a A(n)=a m m n n m m +a +a m-1m-1 n n m-1m-1 +

34、+a+a1 1n+an+a0 0是一是一个个mm次多项式，则次多项式，则A(n)=O(nA(n)=O(n m m) )例例 for(i=2;i=n;+i)for(i=2;i=n;+i) for(j=2;j=i-1;+j) for(j=2;j=i-1;+j) +x; ai,j=x; +x; ai,j=x; 语句频度为：语句频度为： 1+2+3+1+2+3+n-2=(1+n-2) +n-2=(1+n-2) (n-2)/2(n-2)/2 =(n-1)(n-2)/2 =(n-1)(n-2)/2 =n =n2 2-3n+2-3n+2 时间复杂度为时间复杂度为O(nO(n2 2) )，即此算法的时间复杂度

35、为平方，即此算法的时间复杂度为平方阶。阶。 一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的次数是固的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为而一个时间为O(nO(n2 2) )的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其以下六种计算算法时间的多项式是最常用的。其关系为：关系为： O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(nn)O(n2 2)O(n)O(n3 3) ) 指数

36、时间的关系为：指数时间的关系为： O(2O(2n n)O(n!)O(n)O(n!)O(nn n) ) 当当n n取得很大时，指数时间算法和多项式时间算取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随问题的输有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。入数据集不同而不同。例例1 1：素数的判断算法。素数的判断算法。Void prime( int n)Void prime( int n)/ /* * n n是一个正整数是一个正整数 * */ / int i=2 ; int i=2 ; while ( (n% i)!=0 & iwhile ( (n% i)!=0 & i* *1.0