本章的目的是阐述算法分析的重要性、它们的表示法和关系，并尽可能求解多个问

题。首先，让我们重点关注算法的基本要素、分析的重要性，然后再逐步讨论上述提及

的其他主题。在完成本章的学习后，能够分析任意给定算法的复杂度（特别是递归函数）。

1.1 变量

在开始讨论变量的定义之前，先来看看以前学习过的数学方程式，它与变量是有关

联的。许多人从初中阶段就学会了求解许多数学方程式。例如，考虑如下方程式：

x2+2y-2=1

我们不必关心这个方程式用在什么地方。需要理解的重点是，这个方程式包含一些

名称(x和y),它们能保存值（数据）。即名称(x和y)是用来表示数据的占位符。类似地，

在计算机科学中，也需要一些东西来保存数据，变量就是实现这一功能的方式。

1.2数据类型

在上述方程式中，变量x和y能表示任意值，例如整数(10、20)、实数(0.23、5.5)》或仅仅是0和1。为了求解该方程式，需要将它们与其所能表示的数据值的类型关联起来。在计算机科学中，数据类型就用于这一目的。编程语言中的数据类型是指具有预定义值的一个数据集合。典型的数据类型有：整数、浮点数、字符、字符串等。计算机内存中全由0和1填充。如果直接用0和1来编码求解问题是非常困难的。为了帮助程序员，编程语言和编译器提供了数据类型。例如，整数(integer)数据类型占2字节（具体的字节数与编译器有关），浮点(float)数据类型占4字节等。这就是说，在内存中将2个字节组合起来(16位)可称为整数。类似

地，将4个字节组合起来(32位)可称为浮点数。数据类型可以减少编码的工作量。在顶层，有两种数据类型：系统定义的数据类型（也称为基本数据类型）。用户定义的数据类型。

1.系统定义的数据类型（基本数据类型）》

系统定义的数据类型叫作基本数据类型。许多编程语言提供的基本数据类型有：it、float、char、double、bool等。每一个基本数据类型分配的位数与编程语言、编译器和操作系统有关。对于相同的基本数据类型，不同的编程语言可能使用不同的大小。根据数据类型的大小变化，总的有效数据值（值域）也是变化的。例如，it可能占2字节或4字节。如果占2字节(16位)，则总的取值范围为一32768~32767(-215~215-1);如果占4字节(32位)，那么总的取值范围为-2147483648~2147483648(一231~231一1)。其他数据类型也是这样。

2.用户定义的数据类型

如果系统定义的数据类型不够，那么大多数编程语言允许用户定义自己的数据类型，称为用户定义的数据类型。用户定义的数据类型的经典实例是：C/C++中的结构体和Java中的类。

例如，下面的代码片段把许多系统定义的数据类型组合在一起，然后用新的名字“new Type'”将其表示为用户定义的数据类型。这样可以更加灵活和方便地处理计算机内存。

public int datal;

public int data 2;

private float data3;

private char data;

/1操作

1.3 数据结构

基于上述讨论，一旦变量中有数据，就需要一种操纵这些数据的机制来求解问题。

数据结构(data structure)就是计算机中存储和组织数据的一种特定方式，它将使得数据

处理更加有效。一个数据结构就是一种组织和存储数据的特定形式。常用的数据结构包

括数组、文件、链表、栈、队列、树和图等。

根据元素的组织方式，数据结构可以分为两种类型：

1)线性数据结构：可以按线性次序访问元素，但它并不强制将所有元素连续地存储

在一起（例如，链表）。例如，链表、栈和队列。

2)非线性数据结构：这种数据结构的元素是以非线性次序来存储和访问的。例如，

树和图。

1.4抽象数据类型

在定义抽象数据类型前，先从不同的视角分析系统定义的数据类型。我们都知道，在默认情况下，所有基本数据类型(int、float等)都支持基本运算，如加法和减法。系统实现了这些基本数据类型的基本运算。对于用户自定义的数据类型，也需要定义相应的运算。在实际使用这些运算时需要实现这些运算。即，通常用户定义的数据类型需要与它们的运算一起定义。为简化求解问题的过程，将数据结构和相关的运算组合起来，将其称为抽象数据类

型(ADT)。一个ADT包含两个部分：

1)数据的声明。

2)运算的声明。

常用ADT包括：链表、栈、队列、优先队列、二叉树、字典、并查集（并和查找）、

散列表、图和许多其他类型。例如，栈使用后进先出(LIFO)机制将数据存储到数据结构

中，最后插入栈的元素第一个被删除。它的常用操作有：创建栈、入栈、出栈、查找栈

顶元素、在栈中查找某一个元素等。

当定义ADT时，不需要考虑其实现细节。仅当需要使用它们时才考虑具体的实现。

不同的ADT类型适合不同的应用。有些是用于高度专业化的特定任务。到本书结束时，

我们将探讨许多ADT。读者也能够学会将相关数据结构与需要解决的问题进行关联。