《数据结构》课程授课教案（讲稿）第一章 绪论

课程名称：数据结构第1周，第_1讲次摘要第一章绪论授课题目（章、节）【目的要求】介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法复杂度的分析方法。【重点】理解数据结构的逻辑结构、存储结构及数据的操作三方面的概念。【难点】算法时间复杂度的分析方法。内容【本讲课程的引入】数据结构课程主要讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及各种算法的设计问题。通过这门课程的学习可以是我们掌握如何组织数据、如何存储数据和如何处理数据的基本概念和软件设计的基本方法。这一次课我们要介绍数据结构课程相关的一些基本概念，了解学习数据结构的意义，以及分析算法的优劣的方法。【本讲课程的内容】第一章绪论1.1数据结构讨论的范畴瑞士的计算机专家在1976年出版了一本书，书名为《算法+数据结构=程序设计》，它说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组”指令”，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。很多问题求解最后都转化为求解数学方程或数学方程组，即使是不需要用计算机求解的简单问题也需要一个数学模型来描述，例如，大家都熟悉的”鸡免同笼”问题，可转化为对“二元一次方程组进行求解。而当计算机进入非数值计算领域、特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。1.2与数据结构相关的基本概念1.数据和数据元素（1）数据：是所有能被输入到计算机中，且能被计算机处理的符号（数字、字符等）的集合，它是计算机操作对象的总称。（2）数据元素：是数据（集合）中的一个”个体”，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位”。2.数据结构若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”。换句话说，数据结构是带”结构”的数据元素的集合。”结构"即指数据元素之间存在的关系。在客观世界中存在的各个事物之间存在着千丝万缕的”联系”，因此在计算机对它进行处理的时候必然也要将这种关系描述进去，如数学方程就是变量之间的约束关系的一种推述，在此称这种关系为结构，因此，数据结构是一堆数据元素和这些数据元素之间的关系的总和。举例：

课程名称：数据结构 第 1 周，第 1 讲次 摘 要 授课题目（章、节） 第一章 绪论 【目的要求】介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基 本概念和术语，掌握算法复杂度的分析方法。 【重 点】理解数据结构的逻辑结构、存储结构及数据的操作三方面的概念。 【难 点】算法时间复杂度的分析方法。 内 容 【本讲课程的引入】数据结构课程主要讨论现实世界中数据的各种逻辑结构、在计算机中 的存储结构以及各种算法的设计问题。通过这门课程的学习可以是我们掌握如何组织数据、 如何存储数据和如何处理数据的基本概念和软件设计的基本方法。这一次课我们要介绍数 据结构课程相关的一些基本概念，了解学习数据结构的意义，以及分析算法的优劣的方法。 【本讲课程的内容】 第一章 绪论 1.1 数据结构讨论的范畴 瑞士的计算机专家在 1976 年出版了一本书，书名为《算法+数据结构 = 程序设计》， 它说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组" 指令"，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构 即为问题的数学模型。 很多问题求解最后都转化为求解数学方程或数学方程组，即使是不需要用计算机求解 的简单问题也需要一个数学模型来描述，例如，大家都熟悉的"鸡兔同笼"问题，可转化为 对"二元一次方程组"进行求解。 而当计算机进入非数值计算领域、特别是用在管理上的时候，计算机的操作对象之间 的关系就无法用数学方程加以描述了。很多数值计算问题的数学模型通常可用一组线性或 非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课 程要讨论的数据结构。 1.2 与数据结构相关的基本概念 1. 数据和数据元素 （1）数据：是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等) 的集合，它是计算机操作对象的总称。 （2）数据元素：是数据(集合)中的一个"个体"，在计算机中通常作为一个整体进行考 虑和处理，是数据结构中讨论的"基本单位"。 2.数据结构 若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该 数据元素的集合为“数据结构”。换句话说，数据结构是带"结构"的数据元素的集合。" 结构"即指数据元素之间存在的关系。 在客观世界中存在的各个事物之间存在着千丝万缕的"联系"，因此在计算机对它进行 处理的时候必然也要将这种关系描述进去，如数学方程就是变量之间的约束关系的一种描 述，在此称这种关系为结构，因此，数据结构是一堆数据元素和这些数据元素之间的关系 的总和。 举例：

a.假设以三个4位的十进制数表示一个含12位十进制数的”长整数”，则可用如下描述的数学模型表示：它是一个含三个数据元素(al,a2,a3)的集合，且在集合上存在下列次序关系：[，]。《x，y》意为x和y之间存在“x领先于y”的次序关系。如长整数321465879345”可用a1=3214，a2=4658和a3=9345的集合表示，且三者之间的次序关系必须是，al表示最高4位，a3表示最低的4位，a2则是中间4位。b.可以用下述数据结构来描述2行3列的矩阵：它是一个含6个数据元素(al,a2,a3,a4,a5,a6)的集合，且集合上存在”行关系”和”列关系”两个次序关系，其中行关系[，《a2,a3>，《a4,a5>，《a5,a6>)，列关系[《al,a4>，《a2,a5>，《a3,a6》]。则得到矩阵：al α2 a2Lα4 a5 α6[al α2 a3a4 a5 α6]再如，描述1行6列的矩阵的数据结构的定义为：它是一个含6个数据元素(al,a2,a3,a4,a5,a6)的集合，且集合上只存在一个次序关系，即：，《a2,a3>，《a3a4>，《a4,a5>》，)。则得到矩阵：从这个例子可见，即使数据元素集合相同，而其上的关系不同，则构成的数据结构不同。数据结构应该包括数据的逻辑结构和数据的”物理结构”两个方面（层次），下面分别介绍这两个方面：（1）数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。常见的数据的逻辑关系有：（1）集合结构：仅同属一个集集合中的数据元素之间没有任何关系，我们可以把没有关系看作是一种特殊的关系。（2）线性结构：一对一（1：1）。线性结构是除第一个和最后一个数据元素外每个数据元素只有一个前驱数据元素和一个后继数据元素。（3）树结构：：一对多（1：n）：层次关系。树结构是除根结点外每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。（4）图结构：多对多(m:n)：网状关系。图结构是每个数据元素可有零个或若干个前驱数据元素和零个或若干个后继数据元素。（2）数据的物理结构亦称存储结构是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。常见的数据的物理结构有：（1）顺序存储结构是把数据元素存储在一块连续地址空间的内存中，程序设计方法是使用数组。顺序存储结构的特点是，逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。（2）链式存储结构是用对象的引用把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。链式存储结构的特点是，逻辑上相邻的数据元素在物理上（即内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。3数据的操作对一种类型的数据进行的某种方法的处理称作数据的操作，一种类型的数据所有的操作集合称作数据的操作集合。对每一个数据结构而言，必定存在与它密切相关的一组操作

a.假设以三个 4 位的十进制数表示一个含 12 位十进制数的"长整数"，则可用如下描述 的数学模型表示：它是一个含三个数据元素{a1,a2,a3}的集合，且在集合上存在下列次序 关系：{，}。 意为 x 和 y 之间存在 "x 领先于 y" 的次序关系。 如长整数 "321465879345" 可用 a1=3214，a2=4658 和 a3=9345 的集合表示，且三者 之间的次序关系必须是，a1 表示最高 4 位，a3 表示最低的 4 位，a2 则是中间 4 位。 b.可以用下述数据结构来描述 2 行 3 列的矩阵：它是一个含 6 个数据元素 {a1,a2,a3,a4,a5,a6} 的集合，且集合上存在"行关系"和"列关系"两个次序关系，其中行 关系{，，，}，列关系{，，}。则 得到矩阵： 再如，描述 1 行 6 列的矩阵的数据结构的定义为：它是一个含 6 个数据元素 {a1,a2,a3,a4,a5,a6}的集合，且集合上只存在一个次序关系，即：{，， ，，}。则得到矩阵： 从这个例子可见，即使数据元素集合相同，而其上的关系不同，则构成的数据结构不 同。 数据结构应该包括数据的"逻辑结构"和数据的"物理结构"两个方面（层次）,下面分 别介绍这两个方面： （1）数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与 数据的存储无关，是独立于计算机的。 常见的数据的逻辑关系有： （1）集合结构： 仅同属一个集集合中的数据元素之间没有任何关系，我们可以把没有 关系看作是一种特殊的关系。 （2）线性结构: 一对一（1:1）。线性结构是除第一个和最后一个数据元素外每个数据 元素只有一个前驱数据元素和一个后继数据元素。 （3）树结构: 一对多（1:n）：层次关系。树结构是除根结点外每个数据元素只有一个 前驱数据元素，可有零个或若干个后继数据元素。 （4）图结构: 多对多 (m:n)：网状关系。图结构是每个数据元素可有零个或若干个前 驱数据元素和零个或若干个后继数据元素。 （2）数据的物理结构亦称存储结构是数据的逻辑结构在计算机存储器内的表示（或 映像）。它依赖于计算机。 常见的数据的物理结构有： （1）顺序存储结构是把数据元素存储在一块连续地址空间的内存中，程序设计方法是 使用数组。顺序存储结构的特点是，逻辑上相邻的数据元素在物理上也相邻，数据间的逻 辑关系表现在数据元素的存储位置关系上。 （2）链式存储结构是用对象的引用把相互直接关联的结点（即直接前驱结点或直接后继 结点）链接起来。链式存储结构的特点是，逻辑上相邻的数据元素在物理上（即内存存储 位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。 3 数据的操作 对一种类型的数据进行的某种方法的处理称作数据的操作，一种类型的数据所有的操 作集合称作数据的操作集合。对每一个数据结构而言，必定存在与它密切相关的一组操作。 a a a a a a 1 2 3 4 5 6 1 2 2 4 5 6 a a a a a a      

4数据结构课程讨论的内容数据结构课程主要讨论线性表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构，在讨论这些典型的常用数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。5抽象数据类型在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及枚举型。数据类型是指一个类型和定义在这个类型上的操作集合。如在高级编程语言中实现的整型都具有下列“数学特性”：它是这样一个序列..-2,1,0,1,2，它可以进行“”、“”、“"、""及"取模"等运算。抽象数据类型（AbstractDataType，缩写为ADT）是指一个逻辑概念上的类型和这个类型上的操作集合。1.3算法和算法的时间复杂度算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要设计算法的概念。而数据结构课程的重点不是讨论一般意义算法的设计方法而是和数据结构相关的算法设计方法以及算法的评价。1.算法的定义和性质算法是描述求解问题方法的操作步骤集合。算法满足以下性质：（1）输入性：具有零个或若干个输入量；输入值即为算法的操作对象，但操作的对象也可以由算法自身生成，如"求100以内的素数"，操作对象是自然数列，可以由变量逐个增1生成。（2）输出性：至少产生一个输出或执行一个有意义操作：算法必须有输出是不言而喻的。如果没有输出这个算法就没有必要。因为输入和输出的关系正是反映了算法的功能。（3）有限性：执行语句的序列是有限的：这里有两重意思，即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。这个有限要有实用价值，例如一千年，在数学上来说是一个有限值，但是用在算法上显然是不合适的。（4）确定性：每一条语句的含义明确，无二义性：确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。（5）可执行性：每一条语句都应在有限的时间内完成。可行性指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题，例如，“求x和y的公因子就不够基本语句，因为它本身还存在一个算法问题。在设计算法时，通常应考虑以下原则：首先说设计的算法必须是"正确的"，其次应有很好的"可读性”，还必须具有"健壮性”，最后应考虑所设计的算法具有"高效率与低存储量“。所谓算法是正确的，除了应该满足算法说明中写明的功能"之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，嗨涩难读的程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。但是要注意高效率和低存储量通常是矛盾的两个方面，通常的做法是根据实际应用的需要，在高效率和低存储量之间取其一作为算法设计的目标

4 数据结构课程讨论的内容 数据结构课程主要讨论线性表、堆栈、队列、串、数组、树、二叉树、图等典型的常 用数据结构，在讨论这些典型的常用数据结构时，主要从它们的逻辑结构、存储结构和数 据操作三个方面进行分析讨论。 5 抽象数据类型 在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式， 明确说明它们所属的数据类型。例如，C 语言中的基本数据类型有：整型、字符型、实型 （包括单精度型和双精度型）及枚举型。 数据类型是指一个类型和定义在这个类型上的操作集合。 如在高级编程语言中实现的整型都具有下列“数学特性”：它是这样一个序 列：.,-2,-1,0,1,2,.，它可以进行“+”、“-”、“× "、"/"及"取模"等运算。 抽象数据类型（Abstract Data Type, 缩写为 ADT）是指一个逻辑概念上的类型和这个 类型上的操作集合。 1.3 算法和算法的时间复杂度 算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要设计算 法的概念。而数据结构课程的重点不是讨论一般意义算法的设计方法而是和数据结构相关 的算法设计方法以及算法的评价。 1.算法的定义和性质 算法是描述求解问题方法的操作步骤集合。 算法满足以下性质： （1）输入性：具有零个或若干个输入量；输入值即为算法的操作对象，但操作的对象 也可以由算法自身生成，如"求 100 以内的素数"，操作对象是自然数列，可以由变量逐个 增 1 生成。 （2）输出性：至少产生一个输出或执行一个有意义操作；算法必须有输出是不言而喻 的。如果没有输出这个算法就没有必要。因为输入和输出的关系正是反映了算法的功能。 （3）有限性：执行语句的序列是有限的；这里有两重意思，即算法中的操作步骤为有 限个，且每个步骤都能在有限时间内完成。这个有限要有实用价值，例如一千年，在数学 上来说是一个有限值，但是用在算法上显然是不合适的。 （4）确定性：每一条语句的含义明确，无二义性；确定性表现在对算法中每一步的描 述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相 同。 （5）可执行性：每一条语句都应在有限的时间内完成。 可行性指的是，序列中的每 个操作都是可以简单完成的，其本身不存在算法问题，例如，"求 x 和 y 的公因子"就不够 基本语句，因为它本身还存在一个算法问题。 在设计算法时，通常应考虑以下原则：首先说设计的算法必须是"正确的"，其次应有 很好的"可读性"，还必须具有"健壮性"，最后应考虑所设计的算法具有"高效率与低存储量 "。所谓算法是正确的，除了应该满足算法说明中写明的"功能"之外，应对各组典型的带有 苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一 位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的 程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是 算法执行过程中所需最大存储空间。 但是要注意高效率和低存储量通常是矛盾的两个方 面，通常的做法是根据实际应用的需要，在高效率和低存储量之间取其一作为算法设计的 目标

2.算法的时间复杂度分析（1）算法的时间效率度量方法算法的时间效率反映了算法执行时间的长短。度量一个算法在计算机上的执行时间通常有如下两种方法：（A）事后统计方法。计算机内部均设有计时功能，可设计一组或若干组测试数据，然后分别运行根据不同的算法编制的程序，并比较这些程序的实际运行时间，从而确定算法时间效率的优劣。这样做的缺点是耗费的时间比较长，有的时候还容易陷入迷范状态。例如，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。(B)事前分析方法。用数学方法直接对算法的时间效率进行分析。因为这种分析方法是在计算机上实际运行该算法之前进行的，所以称为事前分析方法。相比之下前者的缺点是，必须在计算机上实地运行程序，容易由其它因素掩盖算法本质：而后者的优点是，可以预先比较各种算法，以便均衡利弊而从中选优。因此在多数情况下，我们都是采用事前分析方法。特别是当一个问题有多个解法时，比较多个算法的优劣，那么如何估算算法的时间效率？首先分析一下和算法执行时间相关的因素有：1）算法所用“策略”：不同策略得到的算法其时间效率就有可能不同。2）算法所解问题的“规模”；显然两个1000*1000的矩阵相乘的时间要比两个10*10的矩阵相乘的时间要多的多。3）编程所用“语言”：4）“编译"的质量；5）执行算法的计算机的速度”。显然，后三条受着计算机硬件和软件的制约，既然是"估算"，仅需考虑前两条。后三个和算法本身无关，取决手当时所用的计算机的硬件和软件的条件。（2）00)函数一个算法的"运行工作量通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其增长的趋势为准则。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：表示算法的时间效率与算法所处理的数据元素个数n函数关系的最常用函数是OO函数（O0)读做大O。该函数表示算法和所处理数据元素个数n的数量级关系。[定义]算法的时间复杂度T(n)=O((n))当且仅当存在正常数c和nO，对所有的n(n≥nO)满足T(n)≤c*(n)。上述定义表示，算法的时间复杂度T(n)随数据元素个数n的增长率和函数(n)的增长率在数量级上相同。（3）算法的时间复杂度分析任何一个算法都是由一个控制结构”和若干“原操作"组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和（原操作(i)的执行次数*原操作(i)的执行时间），则算法的执行时间与所有原操作的执行次数之和成正比。”原操作"指的是固有数据类型的操作，显然每个原操作的执行时间和算法无关，相对于问题的规模是常量。同时由于算法的时间复杂度只是算法执行时间增长率的量度，因此只需要考虑在算法中"起主要作用"的原操作即可，称这种原操作为基本操作"，它的重复执行次数和算法的执行时间成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环

2. 算法的时间复杂度分析 （1）算法的时间效率度量方法 算法的时间效率反映了算法执行时间的长短。度量一个算法在计算机上的执行时间通 常有如下两种方法： （A）事后统计方法。计算机内部均设有计时功能，可设计一组或若干组测试数据，然 后分别运行根据不同的算法编制的程序，并比较这些程序的实际运行时间，从而确定算法 时间效率的优劣。 这样做的缺点是耗费的时间比较长，有的时候还容易陷入迷茫状态。例 如，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。 (B)事前分析方法。用数学方法直接对算法的时间效率进行分析。因为这种分析方法是 在计算机上实际运行该算法之前进行的，所以称为事前分析方法。 相比之下前者的缺点是，必须在计算机上实地运行程序，容易由其它因素掩盖算法本 质；而后者的优点是，可以预先比较各种算法，以便均衡利弊而从中选优。 因此在多数情况下，我们都是采用事前分析方法。特别是当一个问题有多个解法时， 比较多个算法的优劣，那么如何估算算法的时间效率？ 首先分析一下和算法执行时间相关的因素有： 1）算法所用“策略”；不同策略得到的算法其时间效率就有可能不同。 2）算法所解问题的“规模”；显然两个 1000*1000 的矩阵相乘的时间要比两个 10*10 的 矩阵相乘的时间要多的多。 3）编程所用“语言”； 4）“编译”的质量； 5）执行算法的计算机的“速度”。 显然，后三条受着计算机硬件和软件的制约，既然是"估算"，仅需考虑前两条。后三 个和算法本身无关，取决于当时所用的计算机的硬件和软件的条件。 （2）O()函数 一个算法的"运行工作量"通常是随问题规模的增长而增长，因此比较不同算法的优劣 主要应该以其"增长的趋势"为准则。假如，随着问题规模 n 的增长，算法执行时间的增长 率和 f(n)的增长率相同，则可记作：表示算法的时间效率与算法所处理的数据元素个数 n 函数关系的最常用函数是 O()函数（O()读做大 O）。该函数表示算法和所处理数据元素个数 n 的数量级关系。 [定义] 算法的时间复杂度 T(n) = O(f(n))当且仅当存在正常数 c 和 n0，对所有的 n(n ≥ n0)满足 T(n) ≤ c*f(n)。 上述定义表示，算法的时间复杂度 T(n)随数据元素个数 n 的增长率和函数 f(n)的增长率 在数量级上相同。 （3） 算法的时间复杂度分析 任何一个算法都是由一个“控制结构”和若干“原操作”组成的，因此一个算法的执行时 间可以看成是所有原操作的执行时间之和 ∑( 原操作(i)的执行次数*原操作(i)的执行时 间 )，则算法的执行时间与所有原操作的执行次数之和成正比。 "原操作"指的是固有数据类型的操作，显然每个原操作的执行时间和算法无关，相对 于问题的规模是常量。同时由于算法的时间复杂度只是算法执行时间增长率的量度，因此 只需要考虑在算法中"起主要作用"的原操作即可，称这种原操作为"基本操作"，它的重复 执行次数和算法的执行时间成正比。 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法 中重复执行的次数作为算法时间复杂度的依据。 这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环

境无关，只暴露算法本身执行效率的优劣。例1：for (i=1; i<=n; ++i)for (j=1; j<=n; ++i) (c[][] =0;for (k=1; k<=n, ++k)c[i][i] =c[i][i]+a[i][k]*b[k][i];1解答：设基本操作的执行次数为n),有(n)=C1*n2+c2*n3因T(n）=n)=c1*n2+c2*n3<=c*n3,其中c1C2c均为常数，所以该算法的时间复杂度为T(n)= O(n3)。例2:for(i=1;i<=n;i=2*i)cout<<" i="<<i,解答：设基本操作的执行次数为(n),有2.(n)<=n,即有(n)<=log2n。因T(n）=(n)<=log2n，所以该算法的时间复杂度为T(n)=O(log2n)课上练习：计算时间复杂度(1 ) for(int i=0;i<n;i++)for(int j=0;j<n;j++)system.out.print(i*);时间复杂度为On2)(2) for(int i=1;i<=n;i*=2)for(int j=1:j<=n;j++)system.out.print(i*j);时间复杂度为O(nlog2n)小结：算法时间复杂度取决于最深循环内包含的基本语句的重复执行次数！(4)指数级时间复杂度的问题算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度的算法，是可接受、可实际使用的算法：具有指数时间复杂度的算法，是只有当n足够小时才可使用的算法。举例说明：当n=50时，多项式函数n3=125000，而指数函数2n=1.0*1015nl=3.0*1064,nn=8.9*1084。通常当基本操作的执行次数超过1.0*1014时，该算法的计算机执行时间将相当长，设计算机每秒可执行一亿（1.0*108）条基本操作，则执行一个需要1.0*1014次基本操作的算法需时为：T=1.0*1014/1.0*108=1.0*106秒=1.0*106/3600=277.8小时=277.8/24=11.6天1.4算法的空间复杂度分析

境无关，只暴露算法本身执行效率的优劣。 例 1： for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i][j] = 0; for (k=1; k<=n; ++k) c [i][j] = c[i][j]+ a[i][k]*b[k][j]; } 解答：设基本操作的执行次数为 f(n),有 f(n)＝c1*n2+c2*n3 因 T(n) ＝ f(n)＝c1*n2+c2*n3<=c* n3,其中 c1 c2 c 均为常数，所以该算法的时间复杂度为 T(n) = O(n3)。 例 2： for(i=1;i<=n;i=2*i) cout<< " i=“<<i; 解答：设基本操作的执行次数为 f(n),有 2 f(n)<=n,即有 f(n)<=log2n。 因 T(n) ＝ f(n) <=log2n，所以该算法的时间复杂度为 T(n) = O(log2n) 课上练习：计算时间复杂度 （1）for(int i=0;i<n;i++) for(int j=0;j<n;j++) system.out.print(i*j); 时间复杂度为 O(n2) （2）for(int i=1;i<=n;i*=2) for(int j=1;j<=n;j++) system.out.print(i*j); 时间复杂度为 O(nlog2n) 小结：算法时间复杂度取决于最深循环内包含的基本语句的重复执行次数！ (4) 指数级时间复杂度的问题 算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂 度的算法，是可接受、可实际使用的算法；具有指数时间复杂度的算法，是只有当 n 足够 小时才可使用的算法。 举例说明：当 n＝50 时，多项式函数 n3＝125000，而指数函数 2n＝1.0*1015， n!=3.0*1064，nn=8.9*1084。 通常当基本操作的执行次数超过 1.0*1014 时，该算法的计算机执行时间将相当长，设 计算机每秒可执行一亿（1.0*108）条基本操作，则执行一个需要 1.0*1014 次基本操作的算 法需时为：T= 1.0*1014/ 1.0*108 = 1.0*106 秒＝ 1.0*106 /3600＝277.8 小时 ＝277.8/24＝11.6 天 1.4 算法的空间复杂度分析

算法的空间复杂度分析主要是分析算法在运行时所需要的内存空间的数量级。算法的空间复杂度通常也采用O0函数。算法的空间复杂度分析方法和算法的时间复杂度分析方法类同。算法的存储量指的是算法执行过程中所需的最大存储空间。算法执行期间所需要的存储量应该包括以下三部分：（1)输入数据所占空间：(2)程序本身所占空间：（3)辅助变量所占空间。程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑：由此只需要分析除输入和程序之外的额外空间。类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为S(n）=O(g(n)，表示随着问题规模n的增大，算法运行所需辅助存储量的增长率与g(n)的增长率相同。例：staticvoidreversel(inta,intb)1int n = a.length,for(inti=O;i=(y+1)*(y+1)ytt;2.设求解同一个问题有三种算法，三种算法的空间复杂度相同，各自的时间复杂度分别为O(n2)、O(2n)、O(nlog2n)，哪种算法最可取？为什么？

算法的空间复杂度分析主要是分析算法在运行时所需要的内存空间的数量级。算法的 空间复杂度通常也采用 O()函数。 算法的空间复杂度分析方法和算法的时间复杂度分析方法类同。 算法的存储量指的是算法执行过程中所需的最大存储空间。算法执行期间所需要的存 储量应该包括以下三部分：(1)输入数据所占空间；(2)程序本身所占空间；(3)辅助变量所占 空间。 程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以 不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身， 和算法无关，则在比较算法时也可以不加考虑；由此只需要分析除输入和程序之外的额外 空间。 类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。 定义算法空间复杂度为 S (n) = O (g(n))，表示随着问题规模 n 的增大，算法运行所需 辅助存储量的增长率与 g(n)的增长率相同。 例：static void reverse1(int[] a, int[] b) { int n = a.length; for(int i = 0; i =(y+1)*(y+1)) y++; 2.设求解同一个问题有三种算法，三种算法的空间复杂度相同，各自的时间复杂度分别为 O(n2)、O(2n)、O(nlog2n)，哪种算法最可取？为什么？