1.2 算法
1.2.1 什么是算法
1.算法定义
曾获图灵奖的著名计算科学家D.knuth对算法做过一个为学术界广泛接受的描述性的定义。一个算法（algorithm）是一个有穷规则的集合，其规则确定了一个解决某一特定类型问题的操作序列。算法的规则必须满足以下5个特性。
◉ 有穷性：对于任意一组合法的输入值，算法在执行有穷步骤之后一定能结束。即算法的操作步骤为有限个，且每步都能在有限时间内完成。
◉ 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且，在任何条件下，算法都只有一条执行路径。
◉ 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。
◉ 有输入：算法有零个或多个输入数据。输入数据是算法的加工对象，既可以由算法指定，也可以在算法执行过程中通过输入得到。
◉ 有输出：算法有一个或多个输出数据。输出数据是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。
2.算法设计目标
算法设计应满足以下5个目标。
◉ 正确性：算法应确切地满足应用问题的需求，这是算法设计的基本目标。
◉ 健壮性：即使输入数据不合适，算法也能做出适当处理，不会导致不可控结果。
◉ 高时间效率：算法的执行时间越短，时间效率越高。
◉ 高空间效率：算法执行时占用的存储空间越少，空间效率越高。
◉ 可读性：算法表达思路清晰，简洁明了，易于理解。
如果一个操作有多个算法，显然应该选择执行时间短和存储空间占用少的算法。但是，执行时间短和存储空间占用少有时是矛盾的，往往不可兼得，此时算法的时间效率通常是首要考虑因素。
3.算法描述
可以用自然语言描述算法。例如，查找是数据结构的一种基本操作，有多种查找算法可实现查找功能，最简单的是顺序查找算法。在图1.5所示的学生信息表中，以“姓名”为关键字进行顺序查找，从表的一端开始，依次将每位学生的姓名与给定值进行比较，若有相等者，则查找成功，查找操作结束；否则继续比较，直到比较完所有元素，若仍未有相等者，则查找不成功，给出结果信息。
也可以用伪码描述算法。采用伪码描述顺序查找的算法如下：
元素search（关键字key）
{
e= 数据序列的第一个元素;
whiIe（数据序列未结束 &&e的关键字不是key）
e= 数据序列的下一个元素;
返回查找到的元素或查找不成功标记;
}
用自然语言或伪码描述算法能够抽象地描述算法设计思想，但是计算机无法执行。因此，数据结构和算法实现需要借助程序设计语言，将算法表达成基于一种程序设计语言的可执行程序。
4.算法与数据结构
算法建立数据结构之上，对数据结构的操作需要用算法来描述。例如，线性表有遍历、插入、删除、查找、排序等操作；树有遍历、查找、插入、删除等操作。通过研究算法，我们能够更深刻地理解数据结构的操作。
算法设计依赖于数据的逻辑结构，算法实现依赖于数据的存储结构。例如，线性表的插入和删除操作，由于采用顺序存储结构，数据元素是相邻存储的，所以插入前、删除后都必须移动一些元素；采用链式存储结构，插入或删除一个元素只需改变相关结点的链接关系，不需移动元素。顺序表和链表的插入操作如图1.6所示。
图1.6 线性表的插入操作
实现一种抽象数据类型，需要选择合适的存储结构，使得以下两方面的综合性能最佳：数据操作所花费的时间短，占用的存储空间少。对线性表而言，当不需要频繁进行插入和删除操作时，可采用顺序存储结构；当插入和删除操作很频繁时，可采用链式存储结构。
1.2.2 算法分析
衡量算法性能的标准主要有算法的时间效率和空间效率。
1.度量算法的时间效率
算法的执行时间是算法中涉及的存、取、转移、加、减等各种基本运算的执行时间之和。算法的执行时间与参加运算的数据量有关，很难事先计算得到。
算法的时间效率是指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量。当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所耗费的时间也以某种单位由1增加到T（n），称此算法的时间复杂度（time complexity）为T（n）。当n增大时，T（n）也随之增大。
在算法的渐进分析中，用大O表示法作为算法时间复杂度的渐进度量值。大O表示法指，当且仅当存在正整数c和n0，使得T（n）≤cf（n）对所有的n≥n0成立时，则称该算法的时间增长率与f（n）的增长率相同，记为T（n）=O（f（n））。
若算法的执行时间是常数级，不依赖于数据量n的大小，则时间复杂度为O（1）；若算法的执行时间是n的线性关系，则时间复杂度为O（n）；同理，对数级、平方级、立方级、指数级的时间复杂度分别为 O（log2 n）、O（n2）、O（n3）、O（2n）。这些函数按数量级递增排列具有下列关系：O（1）<O（log2 n）<O（n2）<O（n3）<O（2n）。
时间复杂度O（f（n））随数据量n变化情况的比较如表1-2所示。
表1-2 时间复杂度随数据量n变化情况的比较
如何估算算法的时间复杂度？一个算法通常由一个控制结构和若干基本操作组成，则
算法的执行时间 =
基本操作（i）的执行次数×基本操作（i）的执行时间
由于算法的时间复杂度表示的是算法执行时间的增长率而非绝对时间，因此可以忽略一些次要因素。设基本操作的执行时间是常量级O（1），则算法的执行时间是基本操作执行次数之和，以此作为估算算法时间复杂度的依据，可表示算法本身的时间效率。
【例1.1算法的时间复杂度分析。
本例讨论各种算法结构的时间复杂度。分析一个算法中基本语句的执行次数，可求出该算法的时间复杂度。
① 一个简单语句的时间复杂度为O（1）。
int count=0;
② 执行n次的循环语句，时间复杂度为O（n）。
int n=8, count=0;
for（int i=1; i<=n; i++）
count++;
③ 时间复杂度为O（log2 n）的循环语句。
int n=8, count=0;
for（int i=1; i<=n; i＊=2）
count++;
i取值为1、2、4、8，循环执行1+log2n次，故循环语句的时间复杂度为O（log2n）。
④ 时间复杂度为O（n2）的二重循环。
int n=8, count=0;
for（int i=1; i<=n; i++）
for（int j=1; j<=n; j++）
count++;
外层循环执行n次，每执行一次外层循环时，内层循环执行n次。所以，二重循环中的循环体语句执行n×n次，时间复杂度为O（n2）。如果
int n=8, count=0;
for（int i=1; i<=n; i++）
for（int j=1; j<=i; j++）
count++;
外层循环执行n次，每执行一次外层循环时，内层循环执行i次。此时，二重循环的执行次数为
，时间复杂度仍为O（n2）。
⑤ 时间复杂度为O（n×log2 n）的二重循环。
int n=8, count=0;
for（int i=1; i<=n; i＊=2）
for（int j=1; j<=n; j++）
count++;
外层循环执行1+log2 n次，内层循环执行次数恒为n，总循环次数为n×（1+log2 n），时间复杂度为O（n×log2 n）。
⑥ 时间复杂度为O（n）的二重循环。
int n=8, count=0;
for（int i=1; i<=n; i＊=2）
for（int j=1; j<=i; j++）
count++;
外层循环执行1+log2n次，i取值为1，2，4，…，内层循环执行i次，i随着外层循环的增加而成倍递增。总循环次数为
，时间复杂度为O（n）。
2.度量算法的空间效率
执行一个算法所需要的存储空间包括三部分：输入数据占用的存储空间、程序指令占用的存储空间、辅助变量占用的存储空间。其中，输入数据和程序指令所占用的存储空间与算法无关，因此辅助变量占用的存储空间就成为度量算法空间效率的依据。
当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的存储空间也以某种单位由1增加到S（n），则称此算法的空间复杂度（space complexity）为S（n）。当n增大时，S（n）也随之增大。空间复杂度用大O表示法记为S（n）=O（f（n）），表示该算法的空间增长率与f（n）的增长率相同。
1.2.3 算法设计
表达数据结构和算法的设计思想不依赖于程序设计语言，实现数据结构和算法则依赖于程序设计语言。不仅如此，描述数据结构所采用的思想和方法还必须随着软件方法及程序设计语言的不断发展而发展。面向对象程序设计方法是目前软件设计的主流方法，C++语言是目前应用广泛的一种面向对象程序设计语言，具备了表达数据结构和算法的基本要素。
算法设计是软件设计的基础。“数据结构”课程是一门理论和实践紧密结合的课程，既要透彻理解抽象的理论知识，又要锻炼程序设计能力。因此，依托一种功能强大的程序设计语言，充分表达和实现复杂的设计思想，是提高程序设计能力的一种有效手段。
本书依托功能强大的C++语言，不仅能够描述数据结构和实现算法，而且以面向对象程序设计思想贯穿始终，体现了软件模块化、可重用的设计思想。以C++语言的类实现各种数据结构参见后续章节。以下通过讨论交换、查找、排序等典型问题，说明使用C++语言的函数、指针、引用、模板等的常见问题，说明算法的必要性、算法表达以及时间复杂度和空间复杂度分析。
【例1.2交换两个变量值的问题讨论。
在应用程序设计时，交换两个变量值是经常遇到的一个问题，这个问题的关键是一个函数如何返回两个变量值。在C++语言中可将函数参数声明为指针（*）或引用（&）类型实现。
本例的目的是说明表达设计思想、实现特定功能所需要使用的函数、指针、引用、模板等C++语言基础。
① 函数参数声明为基本数据类型
如果swap（ ）函数声明如下：
void swap（int x,int y） //不能实现交换
{
int temp=x;
x=y;
y=temp;
}
调用语句如下：
int i=1,j=2;
swap（i,j）;
调用swap（i, j）函数时，将实际参数i、j的值传递给形式参数x、y；在函数体中交换了两个局部变量x、y的值，但交换结果并未影响实际参数i、j，如图1.7所示。因此，上述swap（ ）函数不能实现交换两个变量值的功能。
图1.7 基本类型的函数参数调用时传递值
② 函数参数声明为指针类型
将函数参数声明为指针类型，声明如下：
void swap（int＊x,int＊y） //指针参数得到实际参数的地址
{
int temp=＊x;
＊x=＊y;
＊y=temp;
}
调用语句如下：
swap（&i,&j）;
swap（&i, &j）函数调用时，传递给形式参数x、y的是实际参数的地址&i、&j，此后对*x、*y的操作就如同对i、j的操作，如图1.8所示。因此，上述swap（ ）函数能够实现交换两个变量值的功能。
图1.8 指针类型的函数参数调用时传递地址
③ 函数参数声明为引用类型
与指针类型的函数参数相似，在C++语言中，也可将函数参数声明为引用类型，对形式参数操作就是对实际参数操作。声明如下：
void swap（int&x,int&y） //参数为引用，对x、y操作就是对实际参数操作
{
int temp = x;
x = y;
y = temp;
}
调用语句如下（执行过程同图1.8）：
swap（i, j）;
④ 函数模板
采用函数模板交换任意数据类型的两个变量，声明如下：
tempIate <cIass T>
void swap（T&x,T&y） //T指定变量类型
{
T temp = x;
x = y;
y = temp;
}
调用语句如下：
swap（i, j）;
⑤ 交换一个数组中的两个元素值
当数组作为函数参数时，传递的是数组首地址。因此，以下函数能够交换一个数组中的两个元素。
tempIate <cIass T>
void swap（T tabIe[],int n,int i,int j） //交换tabIe[i]、tabIe[j]值，n指定数组元素个数
{
if（i>=0&&i<n&&j>=0&&j<n&&i!=j） //避免下标越界
{ T temp=tabIe[i];
tabIe[i] = tabIe[j];
tabIe[j] = temp;
}
}
执行过程如图1.9所示。
图1.9 交换一个数组中的两个元素
在swap（ ）函数中，使用3条语句实现交换功能，时间复杂度是O（1）；使用一个局部变量temp作为额外存储空间，空间复杂度是O（1）。
【思考题】以下交换两个变量值的swap（ ）函数声明是否正确？为什么？
void swap（int ＊x, int ＊y）
{
int ＊temp = x;
x = y;
y = temp;
}
【例1.3求两个整数的最大公约数。
本例以求最大公约数为例，说明算法的必要性。
① 质因数分解法
数学方法求两个整数的最大公约数是，分别将两个整数分解成若干质因数的乘积，再比较两者的公约数，从中选择最大者。例如，已知26460=22×33×5×72，12375=32×53×11，则26460与12375的最大公约数为32×5=45。
质因数分解法基于算术基本定理，解决了公约数和公倍数问题。但它的理论成果很难应用于实际计算中，因为大数的质因数很难分解。
② 更相减损术
在中国古代数学经典著作《九章算术》的方田章中，给出最大公约数的“更相减损”解法，“以少减多，更相减损，求其等也，以等数约之。等数约之，即除也，其所以相减者皆等数之重叠，故以等数约之。”其中等数即指两数的最大公约数。如求91和49的最大公约数，其逐步减损的步骤为：（91, 49）=（42, 49）=（42, 7）=7。
该法“寓理于算，不证自明”，不仅给出解题步骤，也说明了解题道理。
③ 欧几里得（Euclid）的辗转相除法
记gcd（a, b）为两个整数a和b的最大公约数，gcd（a, b）具有如下性质：
gcd（a,b）=gcd（b,a）
gcd（a,b）=gcd（-a,b）
gcd（a,0）=|a|
gcd（a,b）=gcd（b,a%b）, 0≤ a %b ＜b
例如，gcd（91,49）=gcd（49,42）=gcd（42,7）=gcd（7,0）=7。实际上，辗转相除法就是现代版的更相减损术。
实现辗转相除法的C++语言描述的gcd（a,b）函数如下：
int gcd（int a,int b） //返回a与b的最大公约数
{
whiIe（b!=0）
{ int k=a%b;
a = b;
b = k;
}
return a;
}
求整数26460和12375的最大公约数，计算过程如下：
gcd（26460,12375）=gcd（12375,1710）=gcd（1710,405）=gcd（405,90）=gcd（90,45）=gcd（45,0）=45
求三个整数a、b、c的最大公约数的调用语句如下：
gcd（gcd（a, b）, c）
【例1.4】数组的顺序查找算法。
本例实现1.2.1节中描述的顺序查找算法，采用数组存储数据序列。根据数据序列是否排序的前提条件，采取的顺序查找算法有所不同。
① 顺序查找算法
1.2.1节中描述的是数据序列没有排序的顺序查找算法。以下程序采用随机数序列作为未排序的数据序列，进行顺序查找。
#incIude <iostream.h>
#incIude<stdIib.h> //其中定义随机数函数rand（ ）
void random（int tabIe[],int n） //将数组元素填充为非0随机数，n指定数组长度
{
int i=0;
whiIe（i<n）
{ int vaIue=rand（ ）% 100; //随机数范围是0～99
if（vaIue!=0）
tabIe[i++] = vaIue;
}
}
tempIate <cIass T>
void print（T tabIe[],int n） //输出数组的n个元素，函数体省略
tempIate <cIass T>
int index（T tabIe[],int n,T vaIue） //在数组中查找值vaIue
{ //若查找成功返回元素下标，否则返回-1
for（int i=0; i<n; i++）
{
cout<<tabIe[i]<<"?"; //输出中间结果，可省略
if（tabIe[i]==vaIue）
return i;
}
return -1;
}
int main（ ）
{
const int N=10;
int tabIe[N]={0};
random（tabIe,N）;
cout<<"随机数序列：";
print（tabIe, N）;
int key=50;
cout<<"顺序查找 "<<key<<"，"<<（（index（tabIe,N,key）==-1）?"不"：""）<<"成功\n";
return 0;
}
程序运行结果如下：
随机数序列：41 67 34 69 24 78 58 62 64 5
41?67?34?69?24?78?58?62?64?5? 顺序查找 50, 不成功
顺序查找的比较次数取决于元素位置。已知数据序列的元素个数为 n，设各元素的查找概率相等，若查找成功，第i（0 i＜n）个元素的比较次数为i+1，平均比较次数为n/2；若查找不成功，则比较n次。因此，顺序查找的时间复杂度为O（n）。算法分析详见第8章。
② 已排序数据序列的顺序查找算法
如果数组元素已按升序排序，采用顺序查找从数组的第一个元素开始比较，只要遇到一个元素大于给定值，则能够确定查找不成功，不需要再比较其他元素。修改的index（ ）函数见例1.5。
在已排序的数据序列中进行顺序查找，查找成功和查找不成功的平均比较次数都是n/2。已排序数组可采用折半查找算法，效率较高，详见第8章。
顺序查找是其他一些操作的基础，如求数组的最大值或最小值、替换指定元素值等。
【例1.5】排序算法及其必要性。
本例说明排序算法的必要性，描述直接插入排序和直接选择排序思路，给出直接插入排序算法实现。
① 排序算法的必要性
已知经过一次比较可判断两个数的大小，据此可实现两个数排序输出。函数如下：
void sort（int a,int b） //两个整数按升序排序输出
{
if（a<b）
cout<<a<<","<<b<<endI;
eIse
cout<<b<<","<<a<<endI;
}
已知3个整数有6种排列，将3个整数按升序排序输出的函数如下：
void sort（int a,int b,int c） //三个整数按升序排序输出
{
if（a<b）
if（b<c）
cout<<a<<","<<b<<","<<c<<endI;
eIse if（a<c）
cout<<a<<","<<c<<","<<b<<endI;
eIse
cout<<c<<","<<a<<","<<b<<endI;
eIse if（a<c）
cout<<b<<","<<a<<","<<c<<endI;
eIse if（c<b）
cout<<c<<","<<b<<","<<a<<endI;
eIse
cout<<b<<","<<c<<","<<a<<endI;
}
这种方法考虑了所有可能情况，称为穷举法，也称为蛮力法。显然，它不能解决n（n>3）个元素的排序问题，不具有广泛性就不能被称为一种算法。因此，必须提供通用的排序算法解决n个元素的排序问题。
② 直接插入排序
将一个元素value插入到一个已排序数组中，使得插入后该数组元素仍然是排序的。首先需要使用顺序查找算法确定元素value的插入位置i，再将i位置之后的若干元素向后移动，空出i位置，最后将元素value存放在数组的i位置。
在数据序列{24, 34, 41, 67, 69, 78}中，插入元素58的算法描述如图1.10所示。
图1.10 在已排序数组中插入一个元素
依次将多个元素插入到指定数组中，则实现直接插入排序（straight insertion sort）。
程序如下。
#incIude <iostream.h>
#incIude <stdIib.h>
tempIate <cIass T>
void print（T tabIe[],int n） //输出数组的n个元素，函数体省略
tempIate <cIass T>
int index（T tabIe[],int n,T vaIue） //在已按升序排序的数组中顺序查找vaIue
{ //若查找成功返回元素下标，否则返回-1
for（int i=0;i<n&&tabIe[i]<=vaIue;i++）
{ cout<<tabIe[i]<<"?"; //输出中间结果，可省略
if（tabIe[i]==vaIue）
return i;
}
return-1;
}
tempIate<cIass T>
void insert（T tabIe[],int n,T vaIue） //在数组中插入vaIue，n指定数组元素个数
{
int i=0;
whiIe（i<n&&vaIue>=tabIe[i]） //顺序查找vaIue的插入位置
i++;
for（int j=n-1;j>=i;j--）
tabIe[j+1]=tabIe[j]; //元素向后移动
tabIe[i]=vaIue; //i是vaIue的插入位置
}
int main（ ）
{
const int N=8;
int tabIe[N]={0};
int i=0;
whiIe（i<N） //产生N个非0的随机数
{ int vaIue=rand（ ）% 100; //随机数范围是0～99
if（vaIue!=0）
{ cout<<"插入"<<vaIue<<",\t";
insert（tabIe,i,vaIue）; //按升序插入到数组中
i++;
print（tabIe,i）;
}
}
int key=50;
cout<<"顺序查找 "<<key<<"，"<<（（index（tabIe,N,key）==-1）?"不"：""）<<"成功\n";
return 0;
}
程序运行结果如下：
插入41, 41
插入67, 41 67
插入34, 34 41 67
插入69, 34 41 67 69
插入24, 24 34 41 67 69
插入78, 24 34 41 67 69 78
插入58, 24 34 41 58 67 69 78
插入62, 24 34 41 58 62 67 69 78
0?24?34?41 顺序查找 50，不成功
insert（ ）函数每插入一个元素，平均比较次数为n/2，平均移动次数为n/2，因此插入一个元素的时间复杂度为O（n），直接插入排序的时间复杂度为O（n2）。详细分析见第9章。
③ 直接选择排序
直接选择排序的基本思想是：第一趟从n个元素的数据序列中选出关键字最小（或最大）的元素并交换到最前（或最后）位置，下一趟再从n-1个元素中选出最小（大）的元素并放到次前（后）位置，依次类推，经过n-1趟完成排序。详见第9章。
④ 任意数据类型T需要重载某些运算符
查找和排序操作都需要经过若干次比较来获得结果，比较由6种关系运算（==、!=、>、>=、<、<=）实现。但查找和排序操作所进行的关系运算是不同的，一般而言，查找操作需要比较两个元素是否相等，采用关系运算==和!=；排序操作需要比较两个元素的大小，采用关系运算>、>=、<、<=。
C++的基本数据类型定义了这6种关系运算；字符串（char*）的比较由string.h中的strcmp（ ）函数提供（见例8.1）；结构体类型和类没有定义这6种关系运算，因此若采用函数模板表达查找或排序算法，T的实际数据类型必须提供所需的关系运算，即重载某些关系运算符（见第4章的例4.4）。
同理，例1.4和本例的print（T table[], int n）函数使用以下语句输出数组指定元素：
cout<<tabIe[i]<<" ";
该语句能够正常运行的前提是，T的实际数据类型提供输出流运算。
重载输出流运算符<<见第2章的例2.2。