image.png

• 数据的逻辑结构
• 数据的存储结构

1.1 什么是数据结构

 众所周知，计算机是一种信息处理装置。信息中的各个元素在客观世界中不是孤立存在的，它们之间具有一定的结构关系。如何表示这些结构关系，如何在计算机中存储数据，采用什么样的方法和技巧去加工处理这些数据，都成为数据结构这门课程所要努力解决的问题。

1. 数据（data）

 数据是描述客观世界的数字，字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号集合。简言之，数据就是计算机加工处理的“原料”，是信息的载体。
 人们日常所涉及到的数据主要分为两类：一类是数值数据，包括整数、实数和复数等，它们主要用于工程和科学计算以及商业事务处理；另一类是非数值数据，主要包括字符和字符串以及文字、图形、语音等，它们多用于控制、管理和数据处理等领域。
 数据的含义十分广泛，在不同场合可以有着不同的含义。例如，在数据计算问题中，计算机处理的对象大多数都是整数或者实数；在文字处理程序中，计算机处理的数据大多是一些符号串；而在一些控制过程问题中，数据可能又是某种信号。然而，在许多场合，人们对数据和信息的引用没有加以严格区分。信息是指数据这个集合中元素的含义；而数据则是信息的某种特定的符号表示形式，可以从中提取信息。

2. 数据元素（data element）

 数据元素是数据整体中相对独立的基本单位，它是数据这个集合中的一个一个的客体。数据元素也称为数据结点，甚至简称结点。如数学中的一个数列称为数据，其中的一个一个元素称为数据元素。字符串就是数据，串中的单个字符就是该字符串的一个数据元素。有的时候，一个数据元素由若干个数据项组成（可见，数据项是数据不可分割的最小单位）。例如，数据文件中一个记录就是它所属文件的一个数据元素，而每个记录又是由若干个描述客体某一方面特征的数据项组成的。当然，一个记录相对于所包含的数据项而言又可以看做事数据。可以说，数据元素是本书中出现频率最高的名词。

3. 数据对象（data object）

 一个数据对象被定义为具有相同性质的数据元素的集合。它是数据这个集合的一个子集。例如，自然数的数据对象是集合｛1，2，3，...｝该集合中的每一个数据元素都是一个自然数，而由26个大写英文字母组成的数据对象则是集合｛‘A’,‘B’,‘C’,...｝。

4. 结构

 在客观世界中，任何事物及活动都不会孤立地存在，都在一定程度上相互影响，相互联系，甚至相互制约。同样，数据元素之间也必然存在着某种联系，这种联系称为结构。人们不仅要考虑到数据的这种结构，而且还要考虑将要施加于数据上的各种操作及其种类。从这个意义上说，数据结构是具有结构的数据元素的集合。
 这里也可以给数据结构一个形式化的描述。数据结构是一个二元组
  Data-Structure=(D,R)，其中，D是数据元素的有限集合，R是D上关系的集合。
 上述定义中的“关系”通常是指数据元素之间存在的逻辑关系，也称为数据的逻辑结构。由于讨论数据结构的目的在于实现计算机中对它的操作，因此还需要研究数据在计算机存储器中的表示。通常把数据结构在计算机中的表示（或者称映像）称为数据的物理结构。物理结构又称为存储结构，它包括数据元素的表示以及关系的表示两个方面。
 根据数据元素之间具有的不同关系，可以将数据的逻辑结构主要分为集合、线性结构与非线性结构几大类。在集合结构中，数据元素仅存在“同属于一个集合”的关系；而在线性结构中，数据元素之间的逻辑关系是“一对一”的关系，即除了第1个数据元素和最后那个数据元素之外，其他每一个数据元素有且仅有一个直接前驱元素，及有且仅有一个直接后继元素，这就是说，结构中的各个数据元素依次排列在一个线性序列中。对于非线性结构，一般情况下，各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或多个其他数据元素发生关系。非线性结构又分为层次结构和网状结构两种，其中层次结构称为树型结构，在这种逻辑结构中，数据元素之间的逻辑关系一般都是“一对多”或者“多对一”的，即每个数据元素有且仅有一个直接前驱元素，但可以有多个直接后继元素。在网状结构中，数据元素之间存在的一般是“多对多”的关系，即每个元素可以有多个直接前驱元素，也可以有多个直接后继元素（此时这种前后关系已经没有实际意义）。网状结构也称为图形结构，简称图。
 一种逻辑结构通过映像便可以得到他的存储结构。由于映像的方式不同，同一种逻辑结构可以映像成不同的存储结构，如顺序映像与非顺序映像，相应的存储结构为顺序存储结构与非顺序存储结构，后者包括链式存储结构（简称链表），索引结构和散列结构；反之，在很大程序上，数据的存储结构要能够正确反映数据元素之间具有的逻辑结构。数据的逻辑结构与存储结构是密不可分的两个方面，以后读者将会看到，一个算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。
 为了说明这些，下面看一个例子。
 表1.1是一个反映某个班级30名学生情况的表格，若利用计算机来管理这个表格，它就对应着一个数据文件。该数据文件有30个记录，每一个记录由若干个数据项组成，一个记录就是一个数据元素，它反映了该班一个学生的情况，30个记录在文件中的先后顺序是按学生年龄从小到大排列的。

image.png

 对于这样一个数据文件，由于数据元素之间的逻辑关系为线性关系，因此，该数据文件的逻辑结构为线性结构，在第2章的讨论中将会看到，该文件被称为一个线性表。对于这个线性表，在计算机内可以有多种存储结构，除了索引存储结构和散列存储结构外，采用较多的是顺序存储结构和链式存储结构。前者在计算机存储器中用一片地址连续的存储单元（即存储单元之间不能间隔）依次存放数据元素的信息，数据元素之间的逻辑关系通过数据元素的存储地址来直接反映。在这种存储结构中，逻辑上相邻的数据元素在物理地址上也必然相邻。图1.1给出了这个存储结构。顺序存储结构的优点是简单，容易理解，并且实际占用最少的存储空间；缺点是需要占用一片连续的整块空间，并且存储分配要事先进行；另外，对于一些操作的时间效率较低也是这种存储结构的主要缺陷之一。

一个顺序存储结构的例子.jpg

一个链式存储结构的例子.jpg

• 研究数据元素之间固有的客观联系（逻辑结构）
• 研究数据在计算机内部的存储方法（存储结构）
• 研究在数据的各种结构（逻辑和物理的）的基础上如何对数据实施有效的操作或处理（算法）。
   为此，应该说数据结构是一门抽象的、研究数据之间结构关系的学科。

1.3 算法

1.3.1 算法及其性质

 数据结构与算法之间存在着密切的联系。可以说，不了解施加于数据上的算法需求就无法决定数据结构；反之，算法的结构设计和选择在很大程度上又依赖于作为基础的数据结构，即数据结构为算法提供了工具，而算法则是运用这些工具来实施解决问题的最优方案。凡是从事过程序设计的人都会有这样一个体会：程序设计过程中相当多的时间花费在考虑如何解决问题上，即通常所说的构思算法，一旦有了合适的算法，用某种具体的程序设计语言来实现（编写程序）并不是一件很困难的事情。难怪有人说，算法+数据结构=程序。从这个角度来说，要设计出一个好的程序，很大程度上取决于设计出一个好的算法。
 什么是算法？
 算法是用来解决某个特定课题的一些指令的集合；或者说，是由人们组织起来准备加以实施的一系列有限的基本步骤。简单地说，算法就是解决问题的办法。如果需要解决的问题比较简单，可以采用自然语言来描述算法。可以说，程序就是用计算机语言表述的算法，而流程图是图形化的算法，甚至一个公式也可以叫做算法。
 待解决的特定课题一般可以分为数值的和非数值的两类。解决数值问题的算法称为数值算法。科学与工程计算方面的算法大都属于这一类算法，如求解数值积分、代数方程或者线程方程组及微分方程等。解决非数值问题的算法称为非数值算法。数据处理方法的算法大多属于非数值算法，如各种各样的查找算法、排序算法、插入或删除算法以及遍历算法。非数值算法主要进行的操作就是比较和逻辑运算。另外，由于特定的课题可能是递归的，也可能是非递归的，因而解决它们的算法那就有递归算法与非递归算法之分。从理论上说，任何递归算法都可以通过循环的方法，或者利用堆栈或队列等机制转化为非递归算法。
 在计算机领域，一个算法实质上是根据所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算。由于数据的逻辑结构与存储结构不是唯一的，在很大程度上可以由用户自行选择和设计，因而解决同一个问题的算法也不一定唯一；另外，即使具有相同的逻辑结构与存储结构，但如果算法的设计思想和技巧不同，设计出来的算法也可能大不相同。显然，根据数据处理问题的需要，为待处理的数据选择合适的逻辑结构与存储结构，进而设计出比较满意的算法，是学习“数据结构”这门课程的重要目的之一。
 作为一个完整的算法应该满足下面5个标准，通常称之为算法的基本特性。

• 输入：由算法的外部提供n(n>=0)个有限量作为算法的输入。这里的“0个”指在算法内部的确切初始条件。也就是说，某些特殊情况下，一个算法可以没有输入。
• 输出：无论什么情况，至少有一个量作为算法的输出，没有输出的算法毫无意义。这些输出与输入有着特定的联系。
• 有穷性：算法必须在有限的步骤内结束。这并不意味着在人们可以容忍的时间内结束，因为算法的性质不应该与具体的机器相联系，只是说明算法要有结束。
• 确定性：组成算法的每一条指令必须有着清晰明确的含义，不能让读者理解它时产生二义性或者多义性。就是说，算法的每一个步骤都必须准确定义。虽然采用自然语言传递的信息具有许多语义不清之处，但人们在理解它们时可以根据周围情景和上下文信息以及推理准确地接受它们，而机器却不能。
• 有效性：算法的每一条指令必须具有可执行性。也就是说，算法所实现的每一个动作都应该是基本的和可以付诸实施的。例如，一个树除以0，这个动作是不能执行的。同时，实施了的算法应该能够达到预期的目的。

1.3.2 基本算法

 作为算法，还有一个重要的侧面，就是构成这个算法所依据的办法（公式、方案和原则），即通常所说的解题思路。有许多问题，只要对处理的对象进行仔细分析，处理的方法就有了，有的则不然。但是作为寻找思路的基本思想方法对任何算法设计都是有用的。

1. 枚举法（enumeration）
    枚举原理是计算机领域十分重要的原理之一。所谓枚举，即从集合中一一列举各个元素。如果不知道一个命题是否为真，利用一一列举每一个元素的方法，如果都为真，找不到反例，则此命题为真。这就是枚举证明。
    枚举的思想作为一个算法能够解决许多问题。一个简单的例子就是对不定方程求解的百鸡问题-----公鸡每只5元，母鸡每只3元，小鸡3只一元，问100元钱买100只鸡能有多少种买法？设x，y，z分贝为3种鸡的只数，可得代数方程
   x+y+z=100
   5x+3y+z/3=100
    再也找不到其他关系了。对于这个不定方程的求解采用枚举法比较方便。若假设可以买到的公鸡、母鸡和小鸡的数目分别用x，y和z表示，则算法可以描述如下。

void BUYCHICKS{
    int x,y,z;
    for(x=1;x<=20;x++){
      for(y=1;y<=33;y++){
        z=100-x-y;
        if(5*x+3*y+z/3==100){
          printf("x=%d",y=%d,z=%d",x,y,z);  /*输出一组解*/
      }
    }
  }
}

 上述算法的基本思想是在x,y,z可能的范围内，把x,y,z可能的只数一一进行列举，如果有解，则解必在其中，而且可能不止一个。枚举法的实质是枚举所有可能的解，用检验条件来判断哪些是有用的，哪些是无用的。枚举法的特点是算法比较简单，但有时运算量比较大，效率显得很低。在那些可确定解的值域，但一时又找不到其他方法时，采用枚举法不失一个较理想的选择。在本书后面的一些内容中，如在迷宫中寻找通路，在图中寻找路径以及某些查找和遍历时都用到了枚举法的思想。

2. 归纳法（induction）
    当人们苦于枚举法的低效时，往往总是乐于从问题中归纳出某种规律。例如，求自然数1-100之和∑i时，采用枚举方法要进行99次加法运算后才能得到结果5050。然而，利用归纳法可以归纳出一个计算公式∑i=n(n+1)/2，利用这个公式可以很容易求得1-100的和为5050，这只需要做一次乘法，一次加法和一次除法运算即达到目的，而且n值越大，优越性越明显。显然，在这一点上归纳法要比枚举法高明得多；但是，要归纳出一个公式也并非容易的事，这其中的过程没有一定规律可循。归纳法源于类比，通过仔细观察找出共同特点，用数学语言或者其他方式将其描述出来。由于是从特殊找出一般关系，归纳也是抽象。归纳法中常用的有数学归纳法，递推和递归也都属于归纳法。
3. 回溯法（backtracking）
    有些问题一时难于归纳出一组简单的公式或者步骤，又不能漫无边际地进行枚举；但是，只要有一点点线索就不妨“试一试”总还是可以的，即使试的=的不成功，再返回到问题的出发点，再换一个办法去试......直到所有可能的办法都试过了，问题也许就能够解决。这就是从方法和路线这一级采用枚举法，也正是人们习惯的思维方法之一。试失败了再返回，再试，这就是回溯。回溯法是设计递归过程的重要手段之一。本书后面介绍的迷宫求通路以及树与图的遍历等，都是使用了回溯法的一些典型例子。
4. 模拟法（simulation）
    自然界和日常生活中有些事件若采用计算机处理很难建立枚举、递推、递归和回溯等算法，甚至于连数学模型都建立不了，使得问题的解决难于下手。这时，解决这类问题的合适方法可以选择模拟。模拟法本身没有固定的模式，其本质是建立模拟的数据模型，根据数据模型展开算法设计，最终达到问题的解决。

1.3.3 算法的描述

 算法独立于具体的计算机，与具体的程序设计语言无关。设计一个算法时，如何选择一种合适的方式来表达算法思想？或者说，有了解决问题的算法思想，如何选择一种合适的语言来描述算法的各个步骤？这也是本节要讨论的重要问题之一。
 在计算机发展的初期，由于计算机解决的问题相对比较简单，人们往往采用自然语言（如中国人多用汉语）来表达自己的算法思想。下面看一个简单例子。
 例1.1 求两个非零正整数M与N的最大公因子。
 若采用自然语言来描述解决问题的各个步骤，则可以表达如下。

• M除以N，将余数送中间变量R。

• 判断R是否为零。
   a. 若R等于零，算法到此结束，求得的最大公因子为当前的N的值。
   b. 若R不等于零，则将N值送M，R值送N，重复算法的1和2。
   这就是一个用自然语言描述的算法。类似的简单问题采用自然语言表达还是可以的，但很快发现，采用自然语言描述算法不方便，也不直观，更谈不上良好的可读性，稍微复杂一些的算法就难以表达，甚至无法表达；另外，由于自然语言自身的一些局限性，用自然语言描述的算法可能会出现语义表达不清楚，甚至多义性现象。采用程序流程图也是一重描述算法的形式，它比采用自然语言表达算法似乎直观了一些，但是依然没有解决复杂算法的表达，而且移植性也不好。

  
  
  求M和N的最大公因子.jpg
  
  

   有人认为，算法最终要通过程序设计语言实现而变成程序在计算机上运行，不如开始就直接采用一种具体的程序设计语言（如Pascal，C和C++语言来描述），目前在较多的“数据结构”教材中也的确用了这种方法。准确地说，用具体的程序设计语言描述的算法就是程序。另外，也可以采用自己设计出的一种既脱离某种具体程序设计语言，又具有各种程序设计语言共同特点的形式化语言来描述算法。
   这种能正确而方便地表达算法思想的语言，可以在一定程度上省去一般程序设计语言对各种类型的数据（如变量、数组或语句标号等）进行的说明或者定义，仅仅利用大多数程序设计语言所具有的那些基本的可执行语句的格式来确定所需要的语句。用这种语言编写的“程序”（实际上是算法）虽然不能直接在计算机上运行，但其书写自由，并且不受具体程序设计语言的词法和语法的限制，熟悉任何一种程序设计语言的人只要对其稍做修改或补充，就能很容易地转变成计算机所能接受的程序。
   本书将才有标准C语言描述书中出现的所有算法。
   对于例1.1求最大公因子的问题，用C语言可以描述如下。

int COMFACTOR(int M,int N){
  int r;
  while(1){
    r = M % N;      /* 求M除以N的余数 */
    if(r==0){
      return N;    /* 输出公因子*/
    }
   M = N;
   N = r;
  }
}

 本书中涉及到的C语言成分包括以下几项。

1. 数据结构的表示（存储结构）采用类型定义（typedef）描述，而数据元素的类型则由用户在使用该数据类型时自行定义。
2. 基本操作的算法采用以下形式的函数描述。

函数类型 函数名（参数表）{
语句序列
}

 在本书中，约定用大写英文字符串或者加上数字作为算法名（即函数名）。参数表（即C函数的形参表）中包括参数的类型说明。参数表可有可无，根据具体情况决定。为了便于算法描述，使算法具有更好的可读性，算法之间除了值调用方法外，还采用了C++语言的引用调用的参数传递方式。在参数表中，以符号&开头的参数即为引用参数。

3. 赋值语句有如下两种。
   a. 简单赋值 变量名=表达式;
   b. 条件赋值 变量名=条件表达式?表达式（真）:表达式(假);
4. 条件语句包括如下4种。
   a. 条件语句1 if(表达式)
          语句序列；
   b. 条件语句2 if(表达式)
          语句序列；
         else
          语句序列；
   c. 开关语句1 switch(表达式){
          case 值1：语句序列1;break;
          .
          .
          case 值n：语句序列n;break;
          default: 语句序列n+1;
          }
   d. 开关语句2 switch{
          case 值1：语句序列1;break;
          .
          .
          case 值n：语句序列n;break;
          default: 语句序列n+1;
          }
5. 循环语句包括如下3种。
   a. for语句 for(赋值表达式序列;循环条件;修改表达式序列)
          语句序列;
   b.whiley语句 while(条件)
          语句序列;
   c. do_while语句 do
          语句序列;
          while(条件);
6. 结束语句包括如下3种。
   a. 函数返回语句return表达式;
   b. case结束语句 break;
   c. 异常结束语句 exit(异常代码);
7. 输入/输出语句如下。
   a. 输入语句 scanf([格式串],变量1,...变量n);
   b.输出语句 printf([格式串],表达式1,...,表达式n);
8. 注释行的书写格式“/* 注释内容*/”。
    在进行程序设计过程中，注释行对于那些目的不太明确或者比较复杂的语句序列是十分有用的，它使得程序易于调试和维护，不仅对程序的编写者有一定帮组，而且对该程序的其他用户也有益处。对算法也是如此。对算法或者算法的局部做一些注释，可以增强算法的可读性。
    原则上说，注释行可以出现在算法的每一个词法单位之外的任何地方，其行数不受限制。

1.4 算法分析

 同一个问题可以采用不同算法解决，例如将一个按值任意排列的数据元素序列转换为一个按值有序排列的数据元素序列的问题，可以通过多种排序算法解决；而一个算法的质量优劣将影响到算法乃至程序的效率。本节讨论的算法分析旨在介绍分析算法质量优劣的基本方法与概念。
 算法分析的目的在于改进算法。那么，如何对一个算法进行评价呢？首先，别评价的算法应该是正确的，这是前提。所谓一个正确的算法是指，当输入一组合理的数据时，能够在有限的运行时间内得到正确的结果；对于不合理的数据输入，能够给出警告提示信息（对不合理的数据输入的反应和处理能力，通常称为算法的健壮性）。通过对数据输入的所有可能情况的分析以及上机调试，可以验证算法是否正确；然而，要从理论上证明一个算法的正确性不是一件容易的事情。除了算法的正确性之外，还应该从以下3个方面考虑对算法进行分析。

1. 依据该算法编写的程序在计算机中运行时间多少的度量，即通常所说的时间复杂度，它是一个算法（程序）运行时间的相对量度。
2. 依据该算法编写的程序占用计算机存储空间多少的度量，即空间复杂度。
3. 其他方面，如算法的可读性、简洁性、可移植性以及易测试性的好坏等。
    这里所说的时间复杂度与空间复杂度的概念不是一个绝对时间多少与绝对空间多少的概念，它们分别都是只是一个数量级的概念；另外，在很多时候，算法的时间复杂度与空间复杂度之间往往是相互影响和制约的。从主观上讲，人们都希望选用一个既不占用很多存储空间，运行时间又少，而且其他方面性能也比较理想的算法；然而，时间与空间上的开销往往是一对矛盾，十全十美的算法实际上很少。有时，一个形式上看起来很简单的算法，其对应的程序运行时间可能要比一个形式上复杂得多的算法对应的程序运行时间慢得多;一个运行时间很少的程序可 能占用的存储空间却很大。有时，为了达到获得较好时间效率的目的，甚至不惜以牺牲空间开 销作为代价。这些，在实际程序设计活动中都是存在的，也都不难理解。在具体设计一个算法时，要尽可能综合考虑以上几个方面。

1.4.1 时间复杂度

 一个程序在计算机中运行时间的多少与诸多因素有关，其中主要包括以下内容。

1. 问题的规模，例如，是求100以内还是求10000以内的所有整数之和所花费的时间显然是有明显差异的。
2. 源程序的编译功能的强弱以及经过编译后产生的机器代码质量的优劣。
3. 机器执行一条目标指令的时间长短。
4. 程序中语句的执行次数。
    前3个因素与计算机系统的硬件、软件以及要解决的问题的规模有关，而与算法本身无直接关系。同一个算法采用不同的程序设计语言实现，或者利用不同的编译程序进行编译，或者在不同的计算机上运行，效率都不会相同，也就是说，对于不同的计算机可能会得出不同的结果，这就表明使用绝对的时间单位的概念来衡量算法的效率是不合适的。上述4个影响算法效率的因素中，只有第4个因素直接与算法有关。因此，通常的做法是把算法中语句执行的次数作为算法时间多少的量度。因为知道了解解决同一个问题的两个不同算法的语句执行次数，就可以比较出它们的时间复杂程度。这种把语句执行次数的多少作为算法时间复杂程度的度量分析方法称为频度统计法。
    一条语句的频度是指该语句被执行的次数，而整个算法的频度就是指算法中所有语句的频度之和。
   例1.2 对计算Fibonacci序列的算法做算法时间复杂度分析
   Fibonacci序列定义为：F0 = 0 F1=1 Fn=Fn-1+Fn-2(n>=2)相应的算法如下。

FIBONACCI(int n){
  int fn1,fn2,fn;
  fn2=0;
  fn1=1;
  printf("%d %d",fn2,fn1);
  for(i=2;i<=n;i++){
    fn = fn2 +fn1;
    printf("%d",fn);
    fn2 = fn1;
    fn1 = fn;
  }
}

 算法中各语句的最右端列出了各语句的频度。整个算法的频度用f(n)表示，有f(n)=1+1+1+n+4(n-1)=5n-1
 要全面分析一个算法的效率，需要考虑算法在最坏情况下的时间代价，对于最坏情况，主要采用大O（符号O为英文单词Order（数量级）的第1个字母的大写）表示方法来描述，一般的提法是：当且仅当存在正整数c和n0，使得f(n)<=cg(n)对所有的n>=n0成立，则称该算法的渐进时间复杂为f(n)=O(g(n))，即当实例特性n充分大时，算法的时间复杂度随n变化。在最坏的情况下，若存在一个增长上界，即ng(n),则该算法的时间复杂度增长的数量级为g(n)，即算法的渐进时间复杂度为O(g(n))。
 对于计算Fibonacci序列的算法而言，其时间复杂度为O(n)，因为此时有g(n）=O（n）。
 算法的时间复杂度采用数量级形式表示以后，将给求一个算法的f(n)带来很大方便。这是只需要分析影响一个算法时间复杂度的关键部分即可，不必对算法的每一个步骤都进行详细的分析。如果最后给出的是渐进值，可以直接考虑算法中关键操作的执行频度，找出与n的函数关系，从而得到整个算法的渐进时间复杂度。
 关键操作大多数在循环和递归过程中。对于单个循环，循环体内的简单语句就是关键操作，该算法段的渐进时间复杂度应该用词关键操作的执行频度的大O表示。对于几个并列的循环，先分析每个循环的渐进时间复杂度，然后利用大O表示法的加法规则来计算其渐进时间复杂度。大O表示法的加法规则是指，当两个并列的算法段的时间代价分别为f1(n)=O(g1(n))和f2(m)=O(g2(m))时，那么，将两个算法段连在一起后的算法段的时间代价为
f(n,m)=f1(n)+f2(m)=O(max(g1(n),g2(m)))这里max指的是n与m充分大时取两者中的较大值。
 如果存在循环嵌套的情况，关键操作应该在最内层循环中，首先自外向内层层分析每一层的渐进时间复杂度，然后利用大O表示法的乘法负责来计算其渐进时间复杂度。例如，当两个嵌套
算法段的时间代价分别为 fj(n)=O(gj(n)) 和 fz(m)=O(gz(m)) 时，则整个算法段的时间代价为
f(n.m) =f1 (n) x fz (m) =O(g1 (n) X g2 (m)).
 这里需要说明的是，诸如查找与排序这样的操作，通常是通过计算操作过程中所进行的元素之间的比较次数的最坏情况来得到算法的时间复杂度。
 算法的时间复杂度通常具有O(1),O(n),O(n2),O(n3),O(log2n),O(nlog2n),O(2n)和O(n!)等几种形式。其中O(1)表示算法的时间复杂度为常量，它不随问题规模n的大小而改变，例如访问一个表中的第一个元素，或者在链表指定位置插入或删除一个链结点的操作，无论该表的大小或者链表的长度如何，其时间复杂度都为O(1) 。具有O(n)数量级的算法被称为线性算法，其运行时间与n成正比。例如，在长度为n的线性表中采用顺序查找方法进行查找时，其时间复杂度为O(n)。时间复杂度为O(log2n)的算法的运行时间与n的对数成正比，如在具有n个记录的排序连续顺序文件中采用折半查找方法进行查找时算法就是如此。
 表中给出了不同的n值，各种典型的数量级所对应的值。
 从表1.2 不难看到，随着问题规模 n 值的增大，各种数量级的对应值的增长速度大不相同，对数值增长速度最慢，线性值较之快一些。当 n 的值增长到一定程度后，各种不同数量级 所对应的值存在如下关系。

image.png

 显然，若一个算法的时间复杂度为表1. 2 中列出的前几个数量级之一，如 0(lOg2n> ，O(n)或者 O( nlog2 川，甚至是 0 (1>，说明该算法的时间复杂度比较满意;如果取到 O(n勺
或者 0(n3)，说明该算法的时间复杂度差强人意;若取到后面几个，则当 n 稍大一点，算法的时 间复杂度会急剧增大，以至于不能计算了。
 当然，有些程序的执行时间不仅依赖于问题的规模，还随着程序所处理的具体数据集的状态不同而不同。例如，有的排序算法对某些原始数据(如按值从小到大排列有序的数据元素序列).其算法的时间复杂度为 O(n) ，而对另一些状态则可以达到O(n）。因此，除特别说明外， 一般都根据可能出现的各种情况中最坏的情况来估算算法的时间复杂度。当然，有时也在某 个特定的约定(如等概率)下讨论某些算法的平均时间复杂度，如查找操作对应的算法就是这样。

1.4.2 空间复杂度

 一个算法在计算机存储器上所占用的存储空间应该包括存储算法本身所占用的空间、算法的输入/输出数据所占用的空集以及算法在运行过程中临时占用的空间3个部分。
 输出/输出数据所占用的存储空间是由解决的问题所决定的，不随算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须写出比较精炼的算法。算法在运行过程中临时占用的存储空间因算法而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，这种算法被称作是“就地”进行的，是节省空间的算法；有的算法需要占用的临时工作单元的数目则随着问题规模的增大而增大，当问题的规模较大时，算法将占用较多的存储空间。
 分析一个算法所占用的存储空间要综合考虑各方面因素。如递归算法来说，它们形式上一般都比较简单，算法本身是所占用的存储空间不多，但算法在运行过程中，需要设置一个附加堆栈，从而占用了较多的临时工作单元。若写成相应非递归算法，算法形式上可能较长，算法本身占用的存储空间也就较多，但算法运行需要的临时空间却相对比较少。
 算法的空间复杂度比较容易计算.主要包括局部变量(即算法泡围内定义的变量)所占用
的存储空间和系统为实现递归(如果算法是递归的话)所使用的堆横空间两个部分。算法的空 间复杂度一般也以数量级的形式给出，如 O(1)，O(n) ，O(n2 ) 和 O(log2 n) 等。
1.4. 3 其他方面
 评价一个算法质量优劣标准的第 3个方面包括算法的简洁性和可读性等。最简单和最直 接的算法往往不→定是最有效的(即最节省时间和空间) ;但是，算法的简洁性可以使算法的正
确性证明变得比较容易，同时也便于编写、修改、调试和阅读。因此，还是应该强调编写出尽可 能简洁的算法。当然.对于那些需要经常使用的算法来说，有效性比简洁性更重要。
 上面简单讨论了如何从 3 个方面来分析一个算法质量的优劣。需要说明的是。这3个方 面往往是相互矛盾的，也就是说，有时为了追求较少的运行时间.可能会占用较多的存储空间;
当追求占用较少的存储空间时，又可能带来运算时间增加的问题。因此.只有综合考虑到算法 的使用频率、算法的结构化和算法的易读性以及所使用系统的硬件与软件环境等因素.才可能 设计出高质量的算法。
 算法分析是一项比较复杂的工作，但不是本书要讨论的主要内容.对这方面有兴趣的读者 可以参考有关专著或资料。