14 第1章基本概念 3.给定n个布尔变量1，~，xm,我！希望打印所有可能的真值组合。例如，如果n=2 共有四种可能：(true,true,(false,true,(tue,false),(false,false)。用C语言编程实现。 4.写一个C程序，按升序打印x,z的整数值。 5.鸽笼原理指出，如果函数f有n个不同的输入，H只有小于n个输出，则一定有两个输 入a,b,a≠b,使f(a)=f(b)。写一个C程序，找出其值域相等的a和b。 6.给定正整数”，判定n是否等于其因子的总和，即判定n是否等于所有t的和，t可以整 除n,1<t<n。 7.阶乘函数n定义为：若n≤1，其值为1：若n>1,其值为n×(n-1)。写出计算阶乘 的递归函数和循环函数。 8.Fibonacci数定义为：f0=0,斤=1，以及当i>1时，后=f后1+f-2。写出计算f的C 语言递归函数和循环函数 9.写出计算二项式系数的循环函数，再把它转为等价的递1函数。 10.Ackerman函数A(m,n)定义为： n+1, if m =0; A(m,n)=A(m-1,1), if n=0: A(m-1,A(m,n-1)),otherwise. 这个的数的特性是：即使m,n很小，它的增长也非常迅速，因此得到泛研究。写出它 的递归实现和循环实现。 11.(Hanoi塔)有三根柱子，64个直径不等的空心碟子套在第一根柱子上，卜面的碟子都比 上而的碟子人。传说一些和尚要把这些碟子从第一根柱子移到第三根柱子，移动时必须 遵循以下规则： (a)一次只能移动一个碟子， b)人碟子不能放在小碳子上。 写一个递归程序，打印移动碟子的过程 12.令S是n个元素的集合，它的幕集是它所有f集的集合。例如，如果S={a,b,那 么powerset(S)={},{a,{b,{c,{a,b},{a,c,{b,c,{a,b,c}。写出递归函数实现 powerset(S). S1.4数据抽象 本书读者无疑熟悉C语言的基本数据类型，如char,nt,float,doub1e,int还 可以有修饰符1og,uns1gned。从真实世界抽象出的问题，最后都是由这些数据类型表示
1砼 第 】章 基本概念 3.给 定 彳个布尔变蚩 γ1厂.'艿刀,我 们希望打印所仃 H△能的真值细~合。例如,如 呆 ″=2, 共 有 四 种 可 能 :(true'true)'(false'true)'(true'false)'(false'false)。 用 C语 言 编 稆 实 现 。 4,写 一个 C程 序,按 升序打印t'珈 z的 整数值。 5.鸽 笼原理指出,如 果函数r有 彳个不同的输入,吐 只有小丁彳个输出,则 一定有两个输 入 伢'抄'伢≠抄,使 r(伢)=r(乙 )。写一个 C稆 序,找 出其值域相等的伢和 抄。 6.给 定正整数 彳,判 定 彳是否竿丁其际l子F向总和,即 判定彳是否竿T所 有 F的和,汐可以整 除 彳 ,1兰 f(彳 。 7.阶 乘函数 彳!定义为:若 彳兰1,其 值为 1;柠 彳>1,其 值为彳×(彳-1)。 写出计算阶乘 的递归函数和循环函数。 8.F山 onacci数 定 义 为 :ro=0'fl=1`以 及 当 j)1时 ,乃 =乃 1+乃 2° 写 出 计 算 乃 的 C 语 言递归函数和循环函数。 9.写 出计算⊥项式系数的循环函数,再 把它转为等价的递丿l函数。 10.Ackerman函 数 A(昭 '彳 )定 义 为 : 这个函数的特性是:即 使 昭'彳很小/占 的增 K也 非常迅速,冈 此得到广泛研究。写出它 的递旷l实现和循环实现。 11.(Hanoi塔 )有 二根柱子,“ 个直径不等的空心碟 f套 在第 一根杵子上,卜 面的碟子都比 上面的碟 lF人 。传说 一些和尚耍把这些碟 F从 第 一根柱子移到第工根柱子,移 动时必须 遵循以下规则: (al一 次只能移动 一个碟 f。 (b)人 碟子不能放在小碟 丫上。 写 一个递归稆序,打 印移动碟丫的过不V。 12,令 S是 彳个元素的集合,它 的幂集足它所有 F集 的集合。例如,如 呆 S=(伢 '抄'c),那 么 powerset(S)=((l'f伢 l'{bl'(c)'伽 'bl'(伢 `c)'(b'c)'扣 '乙 'cl)° 丐 出 递 归 函 数 实 现 powerset(S)° §1。珏 数 据抽象 本 书 读 者 无 疑 熟 悉 C语 亩 的 基 本 数 据 类 型 ,如 char,土 nt,f】 oa△ ,doub】 e,土 n△ 还 可以有修饰符 】ong,unsigned。 从真实世界抽象出的问题,最 后都是由这些数据类型表示
51.4数据抽象 15 的。除了这些基木数据类利，C语言还提供两种聚合数据类刊机制，一种是数组，一种是结 构体。数组是相同数据类型的集体，数组中所有数据的类型都相同，无需显小给出，例如。 t1ist[51,定义了含有五个（相同的）整数的数组，数组下标的范围是0，·，4。结构体 可以是不同元素类型的集体，这些不同的元素类刊必须显式给出。例如 struct student char lastName int studentId; char grade; 在这个结构体中定义了二个成员域，两个成员域是字符型，一个成员域是整型，结构体 名称是student。C语言结构体的详细解释作第2登中给出。 所有程序设计语言都全少提供一个最小的、预定义的数据类型集合，还要提供构造新类 型的机制，域由州户门定义类型的机制。现在我要问：“数据类型是什么？” 定义数据类型是数据对象和施加在数据对象上操作的聚合休。 无论科序中用到的是预定义数据类型，或山定义数据类型，都应考悲数据对象和数 据揆作两方面内容。例如，数据类型t的数据对象是{0，+1，-1，+2，一2，NT_MAX, NTMN,其中NT.MAX和INT.MIN是机器所能表小的坡人整数和最小整数（这两个俏 定义在C语言的头文件1imc8.h之中)。整数操作有很多，当然包括算术运算+，-， %。其它操作还包括测试两数是否相等，以及赋值樑作。这些探作都有操作名称。操作可以 是前缀算符，如ato1,或是中缀算符，如+。不管数据操作是由语言本身定义的，或者是 由库函数定义的，其名称、参、以及执行结果都应指定， 除了必须了解数据类刚的操作之外，我还应了解数据对象是如何表小的。例如，人多 数计算机的char类型表示占州一个字节存储完间的比特串，而nt可能片H川2个或4个字 的存储空间，如果1nt占用2个字作，那么IwTx=25-1=32767 了解数据类型中数据对象的表乐格式，当然很有用处，但使用不当也有可能带米危险 如果已知数据类型的存储格式，编写算法时当然可以加以允分利用，然而，一川该数据对象 的格式改变了，那么程序代码也必须做应改动。很多软件设计人员都发现，把数据对象的 表示隐藏起米，不为用户所知，反倒是更好的设计策略。这样的话，用户只能通过提供的函 数接口处理数据对象。只要某操作所提供的州户接口不变，设计者就可以修改表示方法，而 出户并不要修收码。 定义抽象数据类型(ADT)中的数据对象和数据揉作的规范声明与数据对象的表示和数据 操作的实现相互分离。 一些程序设计语言提供明显的机制支持区分规范声明利和实现，例如虹，Ad妇语言中的 package和C+语中的类都提供这种支持，可供程序员直接用米定义抽象数据类型。尽 管C语言并未明显地提供实现ADT的机制，我们还是可以利州C语言的现有机制构造类似 的数据类型，信心十足地定义ADT
§】。4数 据抽象 15 的。除了这些基本数据类犁,C语 言还提供两种聚合数据类型机制,一 种是数细~, 一种是结 构体。数组是相同数据类型的集体,数 纽中所有数据的类型都相同,尢 需显示给出,例 如, 土nt1土 st[51,定 义了含有TL个 (相 同的)整 数的数细,数 细 卜标的范围楚 0'. ·'4。结构体 可以足不同元素类型的集体,这 些不同的元素类型必须显式给出。例如, g△ ruct student ( char 1astName` 土nt studentId` char grade` )氵 在这个结构体中定义了二个成员域,两 个成员域足字符型,一 个成 员域足整型,纬 构体 名称足 student。 c语 宀结构体的详细解释在第 2章 中给|l{。 所有程序设计语 宀都至少捉供一个鼓小的、预定义的数据类Ⅱ吵集合,还 耍捉供构造新类 型的机制,或 曲用户 向定义类型的机制。现仵我们要问:“数据类型足什么?” 定义 数据类型足数据对象和施加在数据对象上操作的聚合体。 □ 无论稆序中用到的足顶定义数据类Ⅱ吵,或 臼定义数据 类l丿,都 应考虑数据对象和数 据操作两方面 内容。例如,数 据类烈 土n△的数据对象足 {0、+1'-1'+2'-2`. ·`INT山 ΙAX' INT MIN),其 屮 INT MAX和 INT山 ΙIN足 机器所能表 /Jx的鼓人整数和最小整数 (这 两个值 定义在 C诂 疒f的 头文件 1土m⊥ts.h之 中)。整数操作仃饣k多 ,肖 然包括笄术运算 +'~'冰 '/、 %。 其它操作还包括测试两数足否廾H竿 ,以 及赋伯操作。这些操作都仃操作名称。操仵可以 足前缀算符,如 at。土,u戈捋足屮缀算符,如 +。 不什数据操作足由订丨宀本呀定义的,或 煮足 由厍函数定义的,其 名称、参牡、以及执行结采都应指定。 除了必须了解数据类Ⅱu的操作之外,我 们还应了解数据×lJ象足如何表/Jx的。例如,人 多 数计算机的 char类 I丿表 /Jxˉ|吁川一个字 l⒈仃储空问的比特 串,而 土nt H1能 丨卜「川J2个 或 茌个字 △的存储空问,如 呆 h△ 丨"+刂 2个 字 i⒈,那 么 INT M眍 =’ 5-1=m%7。 了解数据类型中数据对象的茯/Jxˉ格式,当 然彳艮有川处,lu使 川不)I勹也仃可能带来危险。 如呆己知数据类烈的存储格式,编 丐箅法时肖然可以加以允分利川,然 而,一 「⒈该数据对象 r向格式改变了,那 么不V序 代码也必须做相丿ψ改动。彳k多 软件设计人员都发现,把 数据对象的 表示隐藏起来,不 为川户所知,反 倒是更好的设计策略。这样的活,用 户只能通过捉供的函 数接 口处理数据对象。只要某操作所提供的用户接 凵不变,设 计者就可以修Llk表示方法,而 用户并不需耍修改代码。 定义 抽象数据类卫 (ADT)中 的数据对象和数据操作的规范声明与数据对象的表示和数据 操作的实现相互分离。 □ 一些程序设计语 疒i^提供明显的机制支持K分 规范芦明和实现 ,例 如,Ada语 占屮的 package和 C++语 占屮F向类都提供这种攴持,可 供不V序 员直接用来定义抽象数据类烈。尽 管 C语 言并未明显地捉供实现 ADT的 机制,我 们还足可以利用 C语 言的现有机制构造类似 的数据类型,信 心十足地定义 ADT
16 第1章基本概念 那么，ADT之中数据探作的规范声明与数据榤作的实现，其差别究竞是什么？规范声明 包括所有函数的名称，它们的参量类型，以及返同结果的类型，还应包括函数的功能描述， 但不涉及内部表示和实现细节。这样的需求界定及为重要，也就是说，抽象数据类型应独立 于实现。数据类型中的函数还可以进一步分成以下类别： (1)创建函数/构造函数：这类函数为特定类型创建新实例 (2)变换函数：这类函数也为特定类型创建实例，但通常使州一个或多个其它实例。变换函 数与构造函数的养别可以通过后续例了进一步滑清。 (③)观察函数/报告函数：这类函数提供数据类型的实例信息，但不修改实例。 常用ADT至少要包括以上类别中的一种函数。 本书全书不断强调规范卢明和实现的区别。为方便读名理解两者之间的差异，我们从 个ADT的定义开始。这个定义有助丁于读者理解问题的实质，这里我们无需讨论数据对象的 表示和数据操作实现细节。在ADT的定义清楚尤误之后，我们才接着讨论数据对象的表示 和操作的具体实现，这两方面内容是数据结构的核心。以卜出ADT的记法。 例l.5(抽象数据类型NaturalNumber)这是第一个ADT例了，我们要花些篇幅解释记 法。ADT1.1定义了山然数的抽象数据类型NaturalNumber. ADT NaturalNumber 数据对象：有序整数数列，范围从0到机器能够表示的最大整数(INT.MAX) 成员函数： 以下x,y∈NaturalNumber;TRUE,FALSE∈Boolean, 且+，-，<，=是整数类型的操作符」 NaturalNumber Zero() ::=0 Boolean IsZero(x) ::if (x)return FALSE else return TRUS Boolean Equal(x,y) ::= if (x=-y)return TRUE else return FALSE NaturalNumber Successor(x) ::= if (x==INT_MAX)return x else return x t 1 NaturalNumber Add(x,y) if ((xty)<INT_MAX)return x +y else return INT MAX NaturalNumber Subtract (x,y)::=if (x<y)return 0 else return x-y end NaturalNumber ADTl.1:抽象数据类型NaturalNumber
16 第 】章 基本概念 那么,ADT之 中数据操作的规范声明⊥J数 据操作的实现,其 并别究竞足什么?规 范卢明 包括所有函数的名称,它 们的参量类型,以 及返冂结呆的类型,还 应包括函数的功能描述, 但不涉及内部表示和实现细节。这样的需求界定及为重要,也 就足说,抽 象数据类Iu应 独立 J=实现。数据类型中的函数还可以进一步分成以 卜类别: (1)创 建函数`构造函数:这 类函数 为特定类丿:刂创建新实例。 ⑵ 变换函数:这 类函数也为特定类型创建实例,但 通常使用 一个或多个其它实例。变换函 数与构造函数的并别可以通过后续例 丫进 一步澄清。 ⑶ 观察函数/报告函数:这 类函数提供数据类’T刂的实例信忌、,但 不修改实例。 常川 ADT至 少要包括以上类别中的一种函数。 本书全书不断强调规范声明和实现的l× ˉ 刖。为方便读煮理解两者之间的并异,我 们从一 个 ADT的 定义开始。这个定义有助 「读者理解 问题的实质,这 咀我们无需讨论数据对象的 表示和数据操作实现细节。在 ADT的 定义清楚尢误之后,我 们才接着讨论数据对象的表示 和操作的具体实现,这 两方面内容足数据结构的核心。以 卜引出 ADT的 记法。 例 ⒈5(抽 象数据类型 NaturalNumber)这 足第 一个 ADT例 F,我 们要花些筋幅解释 记 法 。 ADT1.1定 义 了 臼 然 数 的 抽 象 数 据 类 裂 Natura1Number。 ^DT Natura1Number 数据对象:有 序整数数列,范 围从O到机器能够表示的最大整数 (INT yAX) 成员函数 : 冫以 ^F X'y ∈ Natura1Number氵 TRUE' FALSE ∈ Boo△ ean, 且 +` -`(`一 是整数类型的操作符。 Natura1Number Zero() ::= O Boo1ean IsZero(x) ::= 土 f (x) return FALSE e△ ge return TRUE Boo1ean Equa1(x' y) ::= 土 f (x==y) return TRUE e1ge return FALSE Natura1Number Successor(x) ::= 土 ￡ (x==INT MAX) return x e△ ge return x + △ Natura1Number Add(x` y) ∶ := 土 ￡ ((x+y)<INT~MAX) return x + y e△ 臼e return INT MAX Natura1Number Subtract(x` y) ::〓 土 ￡ (x(y) return O e△ ge return x - y end Natura1Number ADT1.△ 抽 象 数 据 类 型 NaturalNumber
51.5性能分析 17 这个白然数抽象数据类刚，从定义关键字DT开始，主要内容分两竹：数据对象和成员 函数。数据对象实际正是计算机系统中的整数类型，但此时并未显式指明整数的表示。成员 函数的定义要复杂一些。首先，定义中用符号x,yi记NaturalNumber的两个元素，再用 TRUB,FALSE记Boolean类型元素，接着定义了整数的加、减、相等、小于函数。这个例子 说明，要定义新的数据类刚，我们可能会用到其它数据类型的操作。每个函数的形式为：返 同结果类型位于函数名称的左边，定义部分位于右边，中何是符号：：=，意思是“定义为”， 第一个函数的名称是zero,无参量，返同白然数零，是构造函数。函数Successor(x 返同白然数序列中×的卜一个，这个函数是变换函数的例子。注意，如果数列中不再有后继 元素了，就是说，x本身就是INTMAX的话，那么这个闲数返同INTMAX。.有些程序员这时 中师向版问出错信良，也是可以的。其它两个变换函数是Add和Subtract,当然以任 上述越界情形返同出错信息，但我选抒返同NaturalNumber中的一个元素。 本书后续的抽象数据类型定义，将遵循ADTL.1给的形式，不过后续ADT中的函数 定义形式不一定是C语言语)，有可能会用结构化的自然语言（英语）解释函数的功能，原 因在千，引入ADT的口的是藏实现细行，顶而在ADT的定义中，无需物龙C语音。有 时，ADT中的成员函数与相应的C语言函数（具体实现）会有差异，甚至参数个数也不相 同，为避免混淆，ADT中的成员函数都以人写字母开头，而C语言函数都以小写字丹开头。 习题 参照ADT1.1,出以抽象数据类刊。 1.为白然数ADT加上如卜成员函数：Predecessor,IsGreater,Multiply,Divide (前驱、人丁、乘法、除法) 2.构造集合ADT set,遵循标准数学定义，成员函数包括：Create,Insert,Remove, IsIn,Union,IIntersection,Difference (创建、插入、删除、属于、并，交，) 3.构造ADT Bag,可以有重复元素的集合。至少包括成员函数：Create,Insert,Remove, IsIn (创建、插入、别除、屈于) 4.构造ADT Boolean,至少包括成员函数：And,Or,Not,Xor,Equivalent,Implies。 (与、或、非、异或、等价、蕴含) S1.5性能分析 本书的一个主要日标是教会读者判断程序性能的优劣。判断程序性能优劣的标准很多， 至少包括如下儿点： (1)程序是否符合任务的规范说明
§】。5性 能分析 这个白然数抽象数据类型,从 定义关键字ADT开 始,主 要内容分两 |∵:数 据对象和成员 函数。数据对象实际正是计算机系统中的整数类l丿,但 此时并木显式指明整数的灰示。成员 函数的定义要复杂 一些。莳先,定 义中川符 刂x`y记 Natura1Number的 两个元素,lFI用 TRUE`FALSE记 Boo1ean类 型元素。接着定义了整数的加、减、相等、小1=函数。这个例子 说明,耍 定义新的数据类犁,我 们可能会用到其它数据类型的操作。每个函数的形式为:返 冂结呆类型位 ∫函数名称的左边,定 义部分位 丁右边,屮 间足符号 :∷ ,意 思足 “定义为”。 第 一个函数的名称是 zer。 ,无 参量,返 冂 白然数零,是 构造函数。函数 successor(x) 返回 自然数序列中 x的 卜一个,这 个函数是变换函数的例 Fˉ。注意,如 呆数列中不再有后继 元素了,就 是说,x本 身就是 工NT~MAx的 活,那 么这个函数返冂 INT MAX。 有些程序员这时 更倾 向 f返 冂出错信息,也 足可 以的。其它两个变换函数是 Add和 subtract,当 然可以在 上述越界情形返冂出错信息,但 我们选择返冂 Natura1Number中 的一个元素。 □ 本书后续的抽象数据类型定义,将 遵循 ADT1.1给 出的形式,不 过后续 ADT中 的函数 定义形式不一定是 C语 言语句,有 可能会用绀i构化的 白然语亩 (英语)解 释函数的功能,原 冈在 丁,引 入 ADT的 日的是隐藏实现细 ”,l,xl而在 ADT的 定义中,无 需拘泥 丁C语 亩。有 时,ADT中 的成员函数 !j相应的 C语 言函数 (J1体 实现 )会 有并异,甚 至参数个数也不相 同,为 避免混浠,ADT中 的成员函数都以人写字母开头,而 C语 宙函数都以小写字母开头。 习题 参照 ADT1.1,写 出以 卜抽象数据类型。 1.为 臼 然 数 ADT加 上 如 下 成 员 函 数 :Predecessor` IsGreater`Mu1t土 p1y'D土 v土 de。 (前驱、人丁、乘法、除法) 2.构 造 集 合 ADT Set,遵 循 标 准 数 学 定 义 ,成 员 函 数 包 括 :Create` Insert`Remove` IsIn、 Un土 on, IIntersect土 on` D土 fference。 (创建、插入、删除、属 「ˉ、并,交 ,并 ) 3.构 造 ADT Bag,可 以 有 重 复 元 素 的 集 合 。 至 少 包 括 成 员 函 数 :create` Insert`Remove` (创建、插入、删除、属 1∴) 在 .构 造 ADT Boo1ean,至 少 包 括 成 员 函 数 :And`○ r`Not`Xor`Equ土 va1ent`工 mp1土 es。 (与、或、非、异或、等价、蕴含) §1。5 性 能 分 析 本书的一个主要 日标是教会读者判断程序性能的优劣。判断稆序性能优劣的标准很多, 至少包括如下儿点: (1)程 序足否符合任务的规范说明。 17
18 第1章基本概念 (2)程序是否正确。 (3)是否有配套文档，说明程子的用法和原理。 (④)程序是否根据逻辑关系分解成能有效执行的函数。 (⑤)程序代码是否易读。 以上判据至关重要，对构建人规模程序系统，显得更为关键：然而，若要指出如何达到 上述林准却并非易事。我们只能说，以上判据可以指导程序员遵循良好的习惯和风格，而且 这样做有益于系统开发，能使开发过程按良好的步调推进。程疗员必须在实战中不断摸索， 从白身的经验中提炼出优秀的编程技能，培养出良好的编程风格。本书后续内容包括人量实 例，我们希望这些内容有助丁读者达到望的日标。除了上述一般性判据之外，以卜两条判 据更加具体： (6)程序是否能够高效使用主存和辅存。 (门)程序的运行时间是否令人满意。 这最后两条判据用米评价程序的性能，可以分成两方面讨论。第一方面的性能估计'机 器无关的空间代价和时间代价，称为性能分析，其研究内容是计算机科学的一个重要分支 属复杂性理论研究的核心问题。第方面称为性能度量，即获取程序在真实环境的实际运行 时间。通过性能度量能够获得程序运行的时间，有助丁发现托费时间较多的程序片段。本节 用米专门讨论性能分析，下节内容时论性能变革。以下首先给空间复杂度与时间复杂度的 定义。 定义空间复杂度是程序运行所需的存储空间：时间复杂度是程序的运行时间。 51.5.1空间复杂度 程序运行所需空间包括两部分： ()定长空间需求：即与程序输入、输出无关的空向，包括指令空间（存储代码的空间）、简 单变量的存储空间、定长结构变量（如结构体）的仟储空间、常革存储空间。 (2)变长空间需求：即马与求解的问题实例相关的结构化变单所上空间人小。如果是递归程 序，还应加上递时所需作空间的人小。给定问题实例1，程序P的变长空间记为 S(I)。S(I)通常为白变量定义在【的特征空间之上的一个数学函数。这些特征常常表 现为关于1的输入、输出个数、长度、或取值。例如，若输入是长度为n的数组，则n是 一个实例特征。如果n是唯一的实例特征，那么Sp(I)可以具体化为Sp(m)。 任何程序所需空间总坐是： S(P)=c+Sp(I) 其中的c表示定长空间需求。分析一个程序的空间父杂度，通常仅考察变长空间需求：分析 多个程序的空间复杂度也是这样。下面看儿个例子
18 第Ι章 基本概念 (勾 稆序楚否正确。 ⑶ 是否有配套文档,说 明程序的川法和原理。 (4)稆 序是否根据逻辑关系分解成能有效执行r向函数。 (sl稆 序代码是否易读。 以上判据至关重要,对 构建人规模稆序系统,显 得更为关键;然 而,若 要指出如何达到 上述柄t准却并 i卜易芋。我们只能说,以 上判据可以指导程序员遵循 良好的习惯和风格,而 且 这样做有益于系统开发,能 使开发过程按 良好的步调推进。程序员必须在实践中不断摸索, 从 臼身的经验中提炼出优秀的编程技能,培 养出良好的编程风格。本书后续 内容包括人董实 例,我 们希望这些 内容有助 T读 者达到期望的日标。除了上述一股性判据乏外,以 卜两条判 据更加具体: ⑹ 程序是否能够高效使川主存和辅存。 ⑺ 程序的运行时间是否令人满意。 这最后两条判据用来评价稆序的性能,可 以分成两方面讨论。第一方面的性能估计 !J机 器无关的空间代价和时问代价,称 为性能分析,其 研究内容是计算机科学的一个重要分支, 属复杂性理论研究的核心问题。第工方面称为性能度量,即 获取不V序 在真实环境的实际运行 时间。通过性能度鲎能够获得程序运行的时问,有 助 丁发现耗费时间较多的程序片段。本节 用来 争门讨论性能分析,卜 |Ⅰ^内容讨论性能度蚩。以 卜浒先给l||空间复杂度与时问复杂度f向 定义。 定义 空间复杂度足稆序运行所需的存储空间;时 间复杂度足稆序的运行时问。 □ §1.5.1 空 间复杂度 稆序运行所需空问包括两部分: (1)定 长空间需求:即 与程序输入、输出尢关的空问,包 括指令空间 (存储代码的空间)、简 单变蚩的存储空问、定 κ结构变蚩 (如 结构体)的 存储空问、常董存储空间。 (2)变 长空间需求:即 与求解的问题实例相关的结构化变鞋所 占空间人小。如呆是递归稆 序,还 应加上递归时所需 l∶作空间的人小。给定问题实例 Ⅰ,程 序 P的 变 K空 间记为 SP(r)。 SP(r)通 常为 白变鞋定义在 r的 特征空间之上的 一个数学函数。这些特征常常表 现为关 l=r的 输入、输出个数、K度 、或取值。例如,若 输入足长度为 彳的数细,则 ″足 一个实例特征。如呆 彳足唯一的实例特征,那 么 SP(r)可 以具体化为 SP(彳)。 任何程序所需空问总兰足: S(P)=c+SP(r) 其中的 c表 示定长空间需求。分析一个稆序的空间父杂度,通 常仅考察变 K空 间需求;分 析 多个程序的空问笈杂度也足这样。下面看儿个例丫