数据结构与算法·基本概念

首先我们要明确一些基本概念,这对于我们后续的学习是有极大的帮助的。

计算

所谓算法,即特定计算模型下,旨在解决特定问题的指令序列。一般来说,算法应满足以下这些特点:

  • 输入 待处理的信息(问题)
  • 输出 经处理的信息(答案)
  • 正确性 的确可以解决指定的问题
  • 确定性 任一算法都可以描述为一个由基本操作组成的序列
  • 可行性 每一基本操作都可实现,且在常数时间内完成
  • 有穷性 对于任何输出,经有穷次基本操作,都可以得到输出

对于“有穷性”这一特点,我们加了着重符号,这是因为这一点有时是很难实现的,却容易被忽略。我们可以考察Hailstone sequence的问题:

上面这段代码很明显是一个求Hailstone sequence长度的函数,但具体的说它还不能当成是一个算法,因为对于任意的n,不一定能满足有穷性这一点。

我们既然已经知道了算法的特性,那么什么样的算法才算是一个好的算法呢?其实我们更应关注的是算法的效率,即:速度尽可能快,存储空间尽可能少。那么我们现在的问题就进步到了如何定量的衡量一个算法的优劣呢?即我们所谓的算法分析,算法分析有两个主要方面:正确成本,正确是指算法功能是否与问题要求一致,而成本则是指运行时间和所需存储空间。我们先来讨论算法的成本问题,之后再讨论正确性方面,我们用TA(P)来代表算法A求解问题实例P的计算成本,但是这种做法意义不大,因为可能出现的问题实例太多,那么我们该如何归纳概括呢?显然,通过观察我们可以发现,问题实例的规模往往是决定计算成本的主要因素,一般来说,规模接近,计算成本也接近,规模扩大,计算成本亦上升。这时我们就可以用TA(n)来代表算法A求解某一问题规模为n的实例所需的计算成本,讨论特定算法A(及其对应的问题)时,可简记作T(n)。然而这一定义仍有问题,因为同一问题等规模的不同实例,计算成本不尽相同,甚至有实质差别,既然如此,又该如何定义T(n)呢?为了稳妥起见,取\(T\left ( n \right )= max\left \{ T\left ( P \right )\mid \left | P \right |= n \right \}\),亦即,在规模同为n的所有实例中,只关注最坏(成本最高)者。前面我们说的只是特定算法在不同实例上的问题,然而同一问题通常有多种算法,如何评判其优劣呢?实验统计是最直接的方法,但却不足以准确反映算法的真正效率,为给出客观的评价,需要抽象出一个理想的平台或模型,从而直接而准确地描述、测量并评价算法。我们的计算模型有Turing Machine、Random Access Machine等,在这些模型中,算法的运行时间与算法需要执行的基本操作次数成正比,即T(n) = 算法为求解规模为n的问题,所需执行的基本操作次数。

渐近分析

回到原先的问题:随着问题规模的增长,计算成本如何增长?注意,这里更关心足够大的问题,注重考察成本的增长趋势,因此我们引入渐近分析(Asymptotic analysis)的思想,即当n>>2后,对于规模为n输入,算法需执行的基本操作次数T(n)等于多少?需占用的存储单元数S(n)又等于多少?但是,通常情况下S(n)是不考虑的。对此我们引入大O记号(big-O notation),即当且仅当存在c > 0,当n >> 2后,有T(n) < c*f(n),则令T(n) = O(f(n))。这样之后,与T(n)相比,f(n)更为简洁,但依然反映前者的增长趋势,另外我们可以得到以下两个特性:(1)、常数项可忽略,即O(f(n)) = O(c * f(n));(2)、低次项可忽略,即O(n+ nb) = O(na),a > b > 0。另外我们要注意,T(n) = O(f(n))中的“=”并不是“等于”的意思,O(f(n))也不是某个具体的函数,事实上,可以把O(f(n))理解成一个由某一类函数构成的集合,该集合中的函数都具有O记号定义中描述的性质,而T(n) = O(f(n))意思是T(n)∈O(f(n)),即T(n)是该集合的一个元素。还有一些其它的记号:T(n) = Ω(f(n)):存在c > 0,当n>>2后,有T(n) > c * f(n);T(n) = Θ(f(n)):存在c> c> 0,当n>>2后,有c1*f(n) > T(n) > c2*f(n)。有了大O记号之后,我们就可以用它来衡量算法的复杂度了,首先是常数复杂度,即O(1),就渐进而言,再大的常数也要小于递增的变数,因此这类算法的效率最高;其次是对数复杂度,即O(logcn),注意,我们这里不注明底数,一般来说,常底数无所谓:因为对于任意a,b > 0,logan = logab * logbn = Θ(logbn);另外常数次幂也无所谓:因为对于任意c > 0,lognc = c * logn = Θ(logn),这类算法非常有效,它的复杂度无限接近于常数;紧接着是多项式复杂度,即O(nc),一般地:aknk + ak-1nk-1 + …+ a1n + a0 = O(nk),a> 0,另外的,对于所有的O(n)类函数,我们称其为线性的,通常编程习题主要覆盖的范围是从O(n)到O(n2),这类算法的效率通常认为已可令人满意;最后是指数复杂度,即O(2n),这类算法的计算成本增长极快,通常被认为不可忍受,从O(nc)到O(2n),是从有效算法到无效算法的分水岭,很多问题的O(2n)算法往往显而易见,然而,设计出O(nc)算法却极其不易,甚至,有时注定地只能是徒劳无功,更糟糕的是,这类问题要远比我们想象的多得多。我们来考察一个2-Subset问题,即S包含n个正整数,∑S = 2m,那么S是否有子集T,满足∑T = m?要解决这个问题,我们首先考虑一种直觉算法,即逐一枚举S的每一子集,并统计其中元素的总和,根据我们学过的集合的相关知识,显然S共有2n个子集,也就是说,直觉算法需要迭代2n轮,并(在最坏情况下)至少需要花费这么多的时间(P.S.严格讲,这只是程序,而不是算法),这看起来似乎不甚理想,应该有更好的办法吧?但实际上,这是一个NP-complete,就目前的计算模型而言,不存在可在多项式时间内回答此问题的算法,就此意义而言,上述的直觉算法已属最优。

算法分析

为确定算法的成本即复杂度,我们不必将算法描述为RAM的基本指令,再统计累计的执行次数,因为C++等高级语言的基本指令,均等效于常数条RAM的基本指令;在渐进意义下,二者大体相当。我们给出复杂度分析的主要方法:对于迭代,主要采用级数求和;对于递归(Recursion),主要采用递归跟踪(Trace)和递推方程(Recurrence)。因此,我们首先来看级数的相关知识:

  • 算数级数:与末项平方同阶
  • 幂方级数:比幂次高出一阶
  • 几何级数(a>1):与末项同阶
  • 收敛级数:常数复杂度O(1)
  • 调和级数:Θ(logn)
  • 对数级数:Θ(nlogn)

接下来用级数来分析迭代:

算术级数:O(n2)

算术级数:O(n2)

算术级数:O(n2)

几何级数:O(n)

几何级数:O(logn * 2logn)

现在我们来讨论之前提到的算法分析的另一个主要任务:正确性,我们通过冒泡排序的问题来探讨正确性,即给定n个整数,将它们按(非降)序排列。通过观察可以发现,有序/无序列表中,任意/总有一对相邻元素顺序/逆序,因此我们可以采用扫描交换的策略,即依次比较每一对相邻元素,如有必要,交换之,若整趟扫描都没有进行交换,则排序完成,否则,再做一趟扫描交换。算法如下:

我们可以证明其正确性,先看其不变性:经k趟扫描交换后,最大的k个元素必然就位;再看其单调性:经k趟扫描交换后,问题规模缩减至n-k;则其正确性显而易见:经至多n趟扫描后,算法必然终止,且能给出正确解答(即k=n)。现在我们接着讨论其性能,最坏情况下,输入数据反序排列,则共要进行n-1趟扫描交换,每趟的效果都等同于当前有效区间循环左移一位,第k趟中,需做n-k次比较和3*(n-k)次移动,0<k<n,因此,累计则有:#KMP = (n-1)+(n-2)+…+1 = n(n-1)/2,#MOV = 3 * n(n-1)/2,T(n) = 4 * n(n-1)/2 = O(n2);最好情况下,所有输入元素已经完全(或接近)有序,则外循环仅1次,做n-1次比较和0次元素交换,共累计:T(n) = n-1 = Ω(n)。

接下来我们引入“封底估算”这种思想,所谓封底估算,英文为Back-of-the-Envelope Calculations(BotEC),这个术语由物理学家恩里科·费米创造,指用简单到可以在手边随便的什么小纸片——比如信封的背面上——进行的计算,对复杂的方程作同一数量级内的近似求解。运用封底估算对现实世界进行分析,可得一些基本常识,如:地球(赤道)周长 ≈ 787 * 360/7.2 = 787 * 50 = 39350 km;1天 = 24hr * 60min * 60sec ≈ 25 * 4000 = 10sec;1生 ≈ 1世纪 = 100yr * 365 = 3 * 10day = 3 * 10sec;50年 ≈ 1.6 * 10sec;三生三世 ≈ 300 yr = 1010 = (1 googel)(1/10) sec;宇宙大爆炸至今 = 1021 = 10 * (1010)2 sec。

迭代与递归

我们先来看一个问题,即计算任意n个整数之和,显然我们可以逐一取出每个元素并累加之,如下代码:

上面的求和代码,无论A[]内容如何,都有:T(n) = 1 + n*1 + 1 = n + 2 = O(n) = Ω(n) = Θ(n),然而空间消耗确是巨大的。因此我们可以采用减而治之(Decrease-and-conquer)的思想来改进这个算法,即为求解一个大规模的问题,可以将其划分为两个子问题:其一平凡,另一规模缩减,分别求解子问题,由子问题的解得到原问题的解。所谓“平凡的问题”,是指无需进行复杂运算,可以直接给出结果的问题。例如,“对n个数进行排序”是一个复杂的问题,但当n等于1时,问题便成为了一个平凡的问题,因为序列长度为1,则序列自然是有序的。像下面这段代码:

这是一个线性递归(Linear Recursion),我们按照前面提到过的递归的分析方法,先用递归跟踪分析:检查每个递归实例,累计所需时间(调入语句本身,计入对应的子实例),其总和即算法执行时间。本例中,单个递归实例自身只需O(1)时间,则T(n) = O(1) * (n+1) = O(n)。再运用递推方程进行分析:从递推的角度看,为求解sum(A, n),需递归求解规模为n-1的问题sum(A, n-1)( T(n-1) ),再累加上A[n-1]( O(1) )。递推方程如下:

T(n) = T(n-1) + O(1)

T(0) = O(1)

求解过程如下:

T(n) – n = T(n-1) – n-1 = …

= T(2) – 2

= T(1) – 1

= T(0)

T(n) = O(1) + n = O(n)

还有另一种思想叫做分而治之(Divide-and-conquer),即为求解一个大规模的问题,可以将其划分为若干(通常两个)子问题,规模大体相当,分别求解子问题,由子问题的解得到原问题的解。我们来看一个计算指定区间整数之和的算法:

这是一个二分递归(Binary Recursion),仍然和前面一样,先用递归跟踪分析:T(n) = 各层递归实例所需时间之和 = O(1) * (2+ 2+ 2+ … + 2logn) = O(1) * (21+logn – 1) = O(n)。更快捷的来看,这其实就是我们上面提到过的几何级数,它的时间复杂度应该与末项同阶。再运用递推方程进行分析:从递推的角度看,为求解sum(A, lo, hi),需递归求解sum(A, lo, mi)和sum(A, mi+1, hi)(2 * T(n/2)),进而将子问题的解累加( O(1) )。递推方程如下:

T(n) = 2 * T(n/2)

T(1) = O(1)

求解过程如下:

T(n) = 2*T(n/2) + c1

T(n)+c1 = 2*(T(n/2) + c1) = 22*(T(n/4) + c1) = …

=2logn(T(1) + c1) = n*(c2 + c1)

T(n) = (c1+c2)n – c1 = O(n)

上面说了那么多,接下来我们看一个实例,即从数组区间A[lo, hi)中找出最大的两个整数A[x1]和A[x2],且A[x1]>=A[x2],并要求元素比较的次数尽可能地少。先来看第一个迭代的算法,如下:

正如上面代码注释中所提到的这个算法无论如何比较次数都是2n-3次,下面的代码将是一个改进版的:

这段代码在最好的情况下,比较次数为:1 + (n-2)*1 = n-1;在最坏情况下,比较次数为:1 + (n-2)*2 = 2n-3。但是我们并不满足,比较次数可否进一步减少呢?其实是可以的,只要运用递归和分而治之的思想:

相比于2n-3,5n/3-2已经有所减少了。

通过以上这些分析,我们发现递归算法易于理解和实现,但空间(甚至时间)效率低,在讲求效率时,应将递归改写为等价的迭代形式。还有另一种递归叫做尾递归(Tail Recursion),即最后一步是递归调用,这是最简单的递归模式,可便捷地改写。

动态规划

我们先来看一个求Fibonacci数列中第n个数的问题,显然fib(n) = fib(n-1) + fib(n-2):{0, 1, 1, 2, 3, 5, 8, …},因此我们可以写出这样的算法:int fib(n){return (2 > n) ? n : fib(n-1) + fib(n-2);},但是这个算法在当n特别大的情况下,运行速度非常的慢,我们来分析一下它慢的原因:

复杂度:T(0) = T(1) = 1; T(n) = T(n-1) + T(n-2) + 1, n > 1

令    S(n) = [T(n) + 1] / 2

则    S(0) = 1 = fib(1), S(1) = 1 = fib(2)

故    S(n) = S(n-1) + S(n-2) = fib(n+1)  //Θ = (1+√5)/2 = 1.61803…

T(n) = 2*S(n) – 1 = 2*fib(n+1) – 1 = O(fib(n+1)) = O(Θn) = O(2n)

之所以慢,原来是可怕的指数复杂度,其实递归版fib()低效的根源在于,各递归实例均被大量重复地调用,先后出现的递归实例,共计O(Θn)个,而去除重复之后,总共不过O(n)种。因此我们可以有下面的解决方法:

解决方法A(记忆:memoization):将已计算过实例的结果制表备查,避免重复调用;

解决方法B(动态规划:dynamic programming):颠倒计算方向:由自顶而下递归,改为自底而上迭代

经过这样的改进,上面算法的T(n) = O(n),而且仅需O(1)的空间。

再来看另一个最长公共子序列(LCS:Longest Common Subsequence)的问题,子序列是由序列中若干字符,按原相对次序构成的,而最长公共子序列是指两个序列公共子序列中的最长着。但要注意,这个LCS可能有多个,也可能有歧义,我们接下来的讨论不考虑这些复杂情况。通过分析,不难得出,对于序列A[0, n]和B[0, m],LCS(A, B)无非三种情况:

(0)若n = -1或m = -1,则取作空序列(“”)                            //递归基,“递归基”是递归函数的一种平凡情况,只有有递归基,递归才不会一直进行下去。

(1)若A[n] = ‘X’ = B[m],则取作:LCS(A[0, n), B[0, m)) + ‘X’             //减而治之

(2)A[n] != B[m],则在LCS(A[0, n], B[0, m))与LCS(A[0, n), B[0, m])中取更长者  //分而治之

现在我们来分析这个算法:

单调性:无论如何,每经过一次比对,原问题的规模必可减小,具体地,作为输入的两个序列,至少其一的长度缩短一个单位

最好情况(不出现第2种情况)下,只需O(n+m)时间,但问题在于,(在第2种情况)原问题将分解为两个子问题,更糟糕的是,它们在随后进一步导出的子问题,可能雷同。在最坏情况下,LCS(A[0, a], B[0, b])出现的次数为,特别的,LCS(A[0], B[0])的次数可多达,当n=m时,为Ω(2n)。我们可以发现,与fib()类似,这里也有大量重复的递归实例(子问题),(最坏情况下)先后共计出现O(2n)个,各子问题分别对应于A和B的某个前缀组合,因此总共不过O(n*m)种,如果采用动态规划的策略,只需O(n*m)时间即可计算出所有子问题,为此只需:(0)将所有子问题(假想地)列成一张表;(1)颠倒计算方向,从LCS(A[0], B[0])出发,依次计算出所有项。

抽象数据类型

我们思考这样一个问题,抽象数据类型(Abstract Data Type)与数据结构(Data Structure)有什么区别呢?其实,抽象数据类型 = 数据模型 + 定义在该模型上的一组操作,而数据结构 = 基于某种特定语言,实现ADT的一整套算法。因此,抽象数据类型是一种抽象定义,它是外部的逻辑特性,不考虑时间复杂度,且一般是操作和语义,不涉及数据的存储方式;而数据结构是多种具体实现,它是内部的表示与实现,与复杂度密切相关,且一般是完整的算法,要考虑数据的具体存储机制。在数据结构的具体实现和实际应用之间,ADT就分工与接口制订了统一的规范,在实现方面,高效率的兑现数据结构的ADT接口操作,类似做冰箱、造汽车;在应用方面,便捷地通过操作接口使用数据结构,类似用冰箱、开汽车。按照ADT规范,高层算法设计者与底层数据结构实现者可高效地分工协作;不同的算法与数据结构可以任意组合,便于确定最优配置;每种操作接口只需统一地实现一次,代码篇幅缩短,软件复用度提高。



发表评论

电子邮件地址不会被公开。 必填项已用*标注