请问是计算机算法设计与分析的大神吗？求助_百度知道
请问是计算机算法设计与分析的大神吗？求助
我有更好的答案
把问题直接发上来或者私信
采纳率：39%
为您推荐：
其他类似问题
计算机算法的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。当前位置： >>
计算机算法-设计与分析导论
计算机算法－设计与分析导论Sara Baase Allen Van Gelder 译者：sttony.dark前言 第一章 分析算法和问题：原理与例子1.1 概述说一个问题是算法可解的（非正式的） ，意味着可以编写一个计算机程序，如果我们允 许这个程序有足够的运行时间和存储空间，这个程序可以为任何输入处理出一个正确的结 果。在 20 世纪 30 年代，计算机出现之前，数学家们就已经积极的定型和研究算法的概念。 算法被解释成（非正式的）一套清楚的简单指令，按照这套指令可以解决某个问题和计算某 个函数。 多种形式的计算模型是设计和研究出来的。 早期这个领域工作的重点叫可计算理论， 其主要是描述或总结那些可算法解决问题的特征， 以及指出那些问题是不能算法解决的。 由 阿兰. 图灵建立的一个重要的否定结论是：证明“停机问题”（halting problem）是不可解决 的。停机问题是说：能否判断一个任意给出的算法（或计算机程序）在给定输入的情况下是 否最终停止（也就是说是否进入死循环） 。这个问题不能用计算机程序解决。 尽管可计算理论对于计算机科学是明显和基础的本质， 但是判断一个问题是否在理论上 可以在计算机上解决的知识还不足以告诉在实际中是否也可以。 例如， 可以写出一个完美的 国际象棋程序。这并不是一件很困难的事情；棋子在棋盘上的摆放方式是有限的，在一定的 规则下棋局总会在有限步之后结束。 程序可以考虑计算机可能走的每一步， 对手对这一步所 有可能的响应，再考虑如何应对对手这一步…… 一直到每一种可能的走法到达结束。既然 知道了每一步的最后结果， 计算机就可以选择一个最好的。 考虑棋子在棋盘上合理的排列 （这 50 比步数要少的多） ，估计就超过 10 。检查所有可能结果的程序需要运行几千年，如此程度 的程序不能运行。 实际应用中大量的问题都是可解决的――就是说可以为他们写出程序――但是对一个 实用的程序来说时间和存储空间的要求是十分重要的。 一个实际程序明确的时间空间要求是 很重要的。因此，他们变成了计算机科学中一个分支的主题，叫计算复杂性。本书并不包含 这一分支，这一分支关心一套正式、有些抽象的关于可计算函数复杂性的理论。 （解决一个 问题等价于根据一套输入计算出函数的输出。 ）度量复杂性的公理已经公式化了；他们是如 此的基础和一般以致一个程序执行指令的条数和需要存储空间的 bit 数都可以作为 复杂性 度量。使用这些公理，我们可以证明任意一个复杂问题的存在，以及问题没有最好的程序。-1-（Using these axioms, we can prove the existence of arbitrarily complex problems and of problems for which there is no best program.） 本书中学习的计算复杂性分支只关心分析特殊问题和特殊算法。 本书打算帮助读者建立 一份解决通用问题的经典算法的清单，分析算法、问题的一些一般性的设计技术、工具和指 导方针，以及证明正确性的方法。我们将呈现、学习和分析计算机程序中常用的解决各种问 题的算法。我们将分析算法执行所需的时间，我们也分析算法执行所需要的空间。在描述各 种问题的算法的时候， 我们将看到几种经常被证明很有用的算法技术。 因此我们暂停一下谈 一谈一些一般性的技术， 比如分而治之 （divide-and-conquer） 、贪 婪 算 法（ greedy algorithms）、 深度优先搜索（depth-first search）和动态编程（dynamic programming） 。我们也将学习问题 本生的复杂性，就是不管用什么算法解决问题所需固有的时间和空间。我们将学习分类 NP 完全问题――目前还没有找到这类问题的有效算法――并试图用一些试探的方法找到有用 的结果。我们也将说明用 DNA 代替电子计算机来向解决这类问题接近。最后，我们将介绍 并行计算机算法的主题。 在下面的一节中我们将给出算法描述语言的大概，回顾一些本书用到的背景知识和工 具，并展示在分析算法中涉及的主要概念。1.2 Java 作为算法描述语言通过平衡多种条件之后，我们选择 Java 作为算法描述语言。算法必须易读。我们想将 注意力放在一个算法的策略和技术上， 而不是编译器关心的申明和语法细节。 语言必须支持 数据抽象和问题分解， 这样才能够简单清楚的表示一个算法的思想。 语言必须提供一种实际 的 实 现 （ 即 已 经 了 编 译 器 ， 原 文 The language should provide a practical pathway to implementation.） 。 他必须在大部分平台上可用而且提供程序开发的支持。 实际的实现和运行 一个算法能增强学生的理解，不能陷入与编译器、调试器失败的战斗中。最后因为本书是教 算法的，不是程序设计，能轻易的将算法转换成读者使用的各种语言必须是合理的要求，特 殊语言特性必须减到最少。 在我们要求的许多方面 Java 表现的很好，尽管我们没有宣称他是理想的。他支持自然 的数据抽象。 Java 是类型安全的， 这意味着一种类型的对象不能在需要另一种对象的操作中 使用；不允许任意类型之间的转换（叫&cast&） 。他有显式的 boolean 类型，所以如果程序员 混淆了&=&（赋值运算符）和&= =& （比较运算符） ，编译器可以发现这个错误。 Java 不允许指针操作， 这些要求通常是含糊不清错误的源头； 事实上编译器向程序员隐 藏了指针，而在幕后自动处理。在运行期，Java 检查越界的数组下标，检查其他由含糊不清 错误引起的矛盾。他执行垃圾收集器，这意味着自动回收不在引用的对象；这大大减轻了程 序员管理空间的负担。 Java 的缺点是：他有许多和 C 一样的简洁、含糊的语法特征。对象结构可能导致时间 和空间上的低效。许多 Java 构造需要比其他语言大的多的冗余，比如 C。 尽管 Java 有许多特殊的特性，本书展示的算法避免使用他们，只对语言独立的部分感 兴趣。事实上，算法中许多步骤都是易读的伪代码。这一节描述了我们在这本书中使用的 Java 的一个小子集，以及用于增加算法可读性的伪代码约定。附录 A 中给出了运行 Java 程 序需要的其他的实现细节，但是这些细节对理解主要内容没有关系。-2-1.2.1 一个可用的 Java 子集完全熟悉 Java 对于理解本书中的算法并不重要。本节给出了本书出现的 Java 特性的一 个大概，主要是为那些想亲自实现算法的读者准备的。这里，我们指出使用的 Java 的 OO 特性，但是尽量避免以使文字得到完全的语言独立性；这主要对熟悉其他 OO 语言（比如 C++）而不是完全熟悉 Java 的读者有好处。附录 A 中有一个简单的 Java 程序。许多书深入 讲解 Java 语言。 有丰富 Java 经验的读者肯定会注意到许多例子中都没有使用 Java 的优秀特性。但是， 算法后面的概念不需要任何特殊的特性， 而且我们希望这些概念可以容易的被领悟， 并使用 各种语言，所以我们将他留给读者，一旦读者领悟了这些概念，就可以用他们喜欢的语言实 现。 熟悉 C 语法的读者将会意识到 Java 的语法有许多相似的地方：块由大括号分隔，&{&和 & }&；数组的索引在方括号&[& 和&]&中。和 C 和 C++一样，二维数组实际上是一个元素是一 维数组的一维数组，所以存取二维数组需要两重 [ ] 就像& matrix[i][j]& 。运算符 &= =& & ! =& && =& 和&& =& 是数学关系运算符的关键字。 在文中使用的伪代码中使用的是数学符 号。文中使用 &++& 和&--& 运算符来增加和减少，但是决不会将他们嵌入到其他表达式中。 这里也有从 C 借用的运算符 &+=& &- =& &* =& &/ =& 。例如 p+= /*p=p+q */ y-= // y=y-x 就像在例子中一样，注释从 &// & 到行结尾，或是从 & /* & 到& */ &，和 C++一样。 Java 的函数头也和 C 一样。函数头在函数名字后的括号中指定了 参数的类型特征；在 函数名字之前指定了返回类型。返回类型和参数类型的组合叫函数的完全类型特征也叫原 型。因此 int getMin(PriorityQ pq) 告诉我们 getMin 接收一个类型（或类）为 PriorityQ 的参数，返回类型 int。 Java 只有很少的原始类型，其他所有类型都叫 classes。原始类型是逻辑（boolean）和 数字类型（byte、char、short、int、long、float 和 double）类型。所有的 Java 类（非原始 类型）都是引用类。在底层，在类中申明的变量都是“指针”；他们的值都是地址。类的实例 叫对象。申明一个变量不会创建对象。通常用&new&运算符来创建对象，&new&返回新对象的 一个引用。 对象的数据域按 OO 术语叫实例域。二元的点运算符用来存取对象的实例域。 例 1.1 创建和存取一个 Java 对象 在这个例子，让我们假设数据信息遵循下面的嵌套逻辑结构： ? year ? number ? isLeap ? ? month day-3-这里使用非正式的术语， year 是由布尔属性 isLeap 和整数属性 number 构成的组合属性， 而 month 和 day 只是简单的整数属性。 为了反映这个嵌 套结构，我们必须在 Java 中定义两个类，一个表示整个数据，另一个表 示 year 域。 假设我们为这两个类分别取名 Date 和 Year。 接下来我们要申 明 number 和 isLeap 作为 Year 类的实例域， 申明 year、month、day 为 Date 类的实例域。除此之外，我们最好将 Year 定义为 Date 的内部类。语法如 图 1.1。 class Date { public Y public static class Year { public boolean isL } } 图 1.1 带一个内部类 Year 的类 Date 的 Java 语法 不带 public 关键字，实例域就不能在 Date 和 Year 外面访问；为了 简单，我们在这里使用 public。申明内部类，Year 带 static 修饰符的原因 是， 因为我们可以单独创建 Year 的实例而不与任何特定 Date 对象相关联 。 本书中所有的内部类都将是 static。 假定我们创建了一个由 dueDate 变量引用的 Date 对象。为了存取对 象中的 year 实例域，使用.运算符，如&dueDate . year&。如果一个实例域 在类中 （与之对应的是在原始类型中） ， 要再接一个. 来存取他的实例域 ， 如&dueDate .year. isLeap& 。 赋值语句仅仅拷贝类对象的引用或地址；不拷贝实例域。例如， & noticDate = dueDate& 导致变量 noticDate 指向了变量 dueDate 指向的同一 对象。因此下面的代码很可能是逻辑错误： noticDate = dueD noticDate .day = dueData .day -7 ; 参见 1.2.2 节，对这个问题有另外的讨论。Java 中的控制语句 if , else , while , for 和 break 和他们在 C（和 C++）中的意义相同， 本书中将用到。存在许多其他的控制语句，但不用他们。while 和 for 的语法是 while （继续条件）body for （初始化；继续条件；增量）body an 这里“初始化”和“增量”都是简单语句 （不带{ }）， “body”是任意语句， “继续条件”是 boole boolean 表达式。break 语句导致立即从最近的 for 或 while 循环中跳出（当然也包括 switch，但本-4-书不使用 switch） 。 Java 是单根继承，其根是 Object。当申明一个新类时，他可以从原来的类中 extends， 新类就成了继承树种以前定义类的派生类。 文中我们将不建立这样的体系， 为了尽可能的保 持语言独立性；但是在附录 A 中给出了一些例子。如果新类没有申明为从任何类 extend， 默认的他从 Object extend。学习算法不需要复杂的类体系。 在 OO 术语里对象的操作叫方法；但是我们将限制自己只使用静态方法，他们都是简单 的过程和函数。在我们的术语中，过程是一个可以取名字、可以被调用的计算步骤序列（带 参数的） ；函数则是一个可以向调用者返回值的过程。在 Java 中不返回值的过程申明返回类 型为 void； 这一点和 C 和 C++一样。Java 术语 static 意味着这个方法可以被任何对象和合适 类型的对象 （对象类型是它的类） 所调用， 只要依照方法的类型特征就行 （经常被称作原型 ）。 一个静态方法与任何特定对象都无关。 静态方法的行为就像其他程序设计语言中的函数和过 程一样。但是，他们的名字必须跟在类名字的后面，例如&List . first(x) & 指以参数 x 调用在 类 List 中定义的 first 方法。 默认情况下 Java 中的实例域是私有的，这意味着他们仅能被定义在类中的方法（函数 和过程）所存取。这和抽象数据类型（ADT）的设计主题是一致的，即对象只能由定义在 ADT 中的方法所存取。实现这些 ADT 操作（或是静态方法，或是函数、过程）的代码存在 与类中，知道这些私有的实例域和其类型。 默认情况下方法也是私有的，但一般指定为 &public& ，所以定义在其他类中的方法可以调用他们。但是，一些只能由类中其他方法调用 的底层方法可能也是私有的。 ADT 的客户（client） （调用 ADT 的函数、过程）在 ADT“生存”以外的类中实现，所以 他们只能存取 ADT 类的 public 部分。私有数据的维护叫做封装或信息隐藏。 实例域在对象的生存期之内保存赋给他的值， 直到后来又赋给他别的值。 这里我们可以 看到将实例域指定为私有的优点。 一个共有的实例域可以被整个程序的任意一段代码赋成任 意一个值。一个私有的实例域就只能通过 ADT 类中为此目的而设计的方法所赋值。这个方 法可以进行其他计算， 并测试赋给他的值是否和 ADT 要求的一致， 是否和其他实例域一致 。 一个新对象通过语句&new classname( )&创建，例如： Date dueDate = new Date 这条语句导致 Java 调用 Date 类的默认构造函数。构造函数保留一个新对象所占的存储 空间， 返回一个新对象的引用 （很可能是地址） 用于存取对象。 新对象的实例域没有初始化 。Java 语言提示 ：程序员可以为类定义一个额外的构造函数，构造函 数可以初始化各种实例域，执行其他计算。我们感兴趣的是语言独立性， 文中将不使用这样的构造函数，所以忽略其细节。Java 中的数组申明和 C/C++中不太一样， 他们的特征也明显不同。 Java 语法申明一个整 型数组 （非常明确， 申明了一个类型为“整型数组”的 变 量 ） 是 & int [ ] x &， 而 C 使用 & int x [ ]&。这条语句不初始化 x ，下面这条语句才初始化 x = new int [howMany] ; 这里 howMany 可以是一个常量也可以是一个变量，他的值指示了数组的长度。申明一个类 的数组是一样的。申明和初始化可以，通常都是合到一条语句中： int [ ] x = new int [howMany]; Date [ ] dates = new Date [howMany ];-5-当这些语句初始化 x 和 dates ，保留数组的存储空间时，只能以默认值初始化元素，这未 必有用。 因为在单个元素使用之前可能需要单独的值 （很可能使用 new 运 算 符 ） 。 在 Date 类 外初始化的语法 dates[0] = new Date( ); dates[0]. month = 1 ; dates[0]. day =1 ; dates[0]. year = new Data.Year( ); dates[0]. year. number =2000; dates[0]. year. isLeap =true ， 注意，域名字跟在指定数组元素的索引之后。在第二条 new 语句中，内部类名字， Year， 被外部类 Date 所限定，因为这条语句在类 Date 的外面。就像前面提到的，Java 程序员可以 写一个带参数的构造函数以初始化一个构造好的新对象， 但是本文为了语言独立性不使用这 样的构造函数。 一旦用 new 语句初始化了 x 数组，x 引用的数组长度就不能改变了。 Java 提供查询长度 的方法，x . length。实例域 length 是 new 语句自动附加到数组对象上的，可以被 x 所存取。 有效的元素索引是从 0 到（x.length －1） 。如果程序试图存取一个越界的元素，Java 将 停止程序 （抛出异常） 。 我们经常希望索引从 1 到 n， 因此常常初始化数组为 & new int [ n+1] & 。 Java 允许重载 和覆盖方法。一个重载方法是说，有多个带不同参数的定义，但是有相 同的返回值。 许多算术操作是重载的。 覆盖则是在类体系中多次定义了有同样参数类型的同 一方法，Java 采用在类体系中最接近的定义。 （还是为了和其他语言兼容，而且这个特性对 于理解算法也不是决定性的，我们避免使用这个特性，读者可以去阅读 Java 语 言的 书。 ）在 不同类中可能使用相同名字的方法，但是这不是覆盖，因为在类外面方法时，必须使用类名 （对象名）来限制。在后面的例子将看的更清楚 。 对于熟悉 C++的读者，必须指出 Java 不允许程序员重载运算符。本文在伪代码中使用 这样的运算符来增加可读性（例如，x & y 这里 x 和 y 都是非数值类，比如 String） 。但是， 如果你定义一个类，开发一个实际的 Java 程序，你就必须写一个有名字的函数（比如 less （） ） ，调用他来比较你的类。1.2.2组织者类我们创造术语组织者类，这不是标准的 Java 术语，他指一种只是为了将多个实例域组 织到一起的简单的类。组织者类实现类似 C 的结构、Pascal 或 Modula 记录的规则；类似的 东西存在于 Lisp、ML 和其他大部分程序设计语言中。组织者类和 ADT 的目的正好相反； 他们只是简单的组织数据，不限制数据的存取，也不为数据提供任何定制的方法。习惯于在 其他类中定义组织者类；由于这个原因，在 Java 术语中组织者类叫内部类。 一个组织者类仅有一个方法，叫 copy。既然 Java 中的变量都是对象的引用，赋值语句 仅拷贝引用，而不是对象的实例域，就像我们在例 1.1 中看到的。如果这些变量在一个叫 Date 的组织者类中定义，我们可以使用语句 noticDate = Date. copy( dueDate ); noticDate .day = dueDate .day -7 ;-6-来拷贝 dueDate 对象的实例域到 noticDate 所引用的新对象中，之后修改的只是 noticDate 的 day 域。 定义 1.1 组织者类的拷贝函数 组织者类将实例域赋值到一个新对象的 copy 函数（方法）的一般规 则如下（例子中假设对象 d 被拷贝到新对象 d2）： 1. 如果实例域（year）是其他的组织者类，copy 方法将调用该 类的 copy 方法，如 d2.year = Year. copy(d . year )。 2. 如果实例域（ day）不是其他组织者类，使用一般的赋值， 如同 d2 .day = d.day。 完整的例子在图 1.2 中给出。 class Date { public Y public static class Year { public boolean isL public static Year copy(Year y) { Year y2 =new Year( ); y2. number = y. y2. isLeap = y. isL return y2; } } public static Date copy(Date d) { Date d2 =new Date( ); d2. year = Year. copy ( d . year); d2. month = d. d2. day = d. return d2; } public static int defaultC } 图 1.2 带内部组织者类 Year 的组织者类 Date 程序员必须保证在定义组织者类时不能发生循环引用，否则 copy 函数将陷入递归不能 结束。当然，组织者类中新对象可以由一般方法创建： Date someDate = new Date ( )-7-Java 语言提示：Java 提供一种一层对象的机制，不需要写出每一条 赋值语句，clone 方法，但是他不能自动处理像 Date 这种嵌套结构；你仍 然要写出处理这种情况的代码。附录 A 给出了一个 copy1level 函数的一 般性代码。一个组织者类包含唯一一个 public 实例域。如果 static 关键字也出现在域的申明中， 该域不与任何实际对象相关，关键在于他不是一个全局变量了。 例 1.2 典型组织者类 在图 1.2 中，为例 1.1 的类增加了 copy 函数，所以他们有成为组织者类的资 格。就像我们看到的， copy 的定义是机械的，而且单调的。在后面的例子中将省 略实现的细节。为了更加完整，我们包含了全局变量 defaultCentury，而一般情况 组织者类是不包含全局变量的。 总结，我们创造了术语组织者类，他指那些只是简单将实例域组织起来，为他们定义一 个拷贝函数的类1.2.3基于 Java 的伪代码约定本书中的大多数算法使用了基于 Java 的更易读的伪代码，而不是严格的 Java。使用了 下面的约定（除了在附录 A 中的以外） 。 1. 2. 省略了块分隔符（&{& 和&}&） 。块边界用缩进指出。 tic 方法 （函数或过程） 申明中省略了 static 关键字。 本文中申明的所有方法都是 sta static （偶尔会有 Java 内建的非静态方法；特别是 s. length( ) 用来获得字符串的长度。 ） 关键字 static 会出现在需要实例域和内部类的地方。 3. 在调用方法 （函数或过程） 前面省略了类名字。 例如 x = cons( z, x) ， 用完整的 Java 语法需要写成 x= IntList. cons ( z, x) （IntList 类在 2.3.2 节中描述） 。无论什么时候 静态方法在其定义的类之外调用都必须加上类名字前缀。 4. 5. 省略存取控制的关键字 public 、 private 和 protecte。 将所有与一个 Java 程序相 关的文件都放在一个目录下，省去了处理可见的麻烦。 经常使用使用数学关系运算符 ?, ?, ? 来代替他们的关键字版本。 关系运算符用在意 义明确的地方，比如 String ，即使在 Java 中是非法的。 6. Java 保留的和 Java 标准部分的关键字都以黑体： int 、String 。注释用斜体。代 码语句和程序变量字体不变。伪代码语句的字体也不变。 当我们特别指出这是 Java 语言时会偶尔离开这些约定。1.3数学知识本书中我们使用各种数学概念、工具和技术。大多数你应该熟悉了，可能会有少部分是 新的。本节一一列举他们，为你提供一个参考，也是一个回顾。设计较深的证明在第三章。-8-1.3.1 集合、元组和关系本节提供一些非正式的定义和集合、关系概念的基础特性。集合是“一堆”不同元素，我 们相将他们作为一个对象处理。通常，元素有同样的类型，有利于我们将他们看作一个对象 的公有的特性。符号 e ? S 读作“元素 e 是集合 S 的一个成员”，或“e 属于 S”注意这里 e 和 S 是不同的类别。例如，如果 e 是一个整数，S 是一个与整数完全不同的整数集合。 一个实际的集合有两种定义方式，列举法和描述法，两种方式都在一对大括号中。例如 下面的符号S1 ? {a, b, c}, S 2 ? {x | x是2的整数次幂}, S 3 ? {1,...., n}. 表达式 S 2 读作“集合中所有元素 x 都是 2 的整数次幂”。 （译者：这里罗嗦的说了一大通怎么表示集合。大家对集合的表示应该比较了解吧！什么你不知道集合？去看看高中的数学！ ） 。 如果一个集合 S1 所有的元素都是另一个集合 S 2 的元素，就说集合 S1 包含于集合 S 2 ， 集合 S 2 包含集合 S1 。符号是 S1 ? S 2 和 S 2 ? S1 。为了表示 S1 是 S 2 的子集而不等于 S 2 ， 写为 S1 ? S 2 和 S 2 ? S1 。区别 ? 和 ? 是很重要的。前者表示是一个元素，后者表示集合 之间的包含。空集记做 ? ，表示没有一个元素，所以他是所有集合的子集。 集合没有固定顺序。因此，在前面的例子中， S1 也可以定义成 {b, c, a} ， S 3 也可以定 义为 {i | 1 ? i ? n} ，可以理解为 i 是一个整数。 以特定顺序组合的一组元素称为序列。 除了顺序， 集合和序列的另一个很重要的不同点 是， 序列的元素可以重复。 序列被表示成元素按顺序的列表， 在加上一个圆括号。 因而 （a,b,c）， （b,c,a）和和（a,b,c,a）是不同的序列。序列中也可以使用省略号，比如（1,......n） 。 如果存在一个整数 n，集合 S 元素的数量可以和 {1,...., n} 一一对应，则我们称该集合 为有限集；这种情况下写为 | S |? n 。通常 | S | 表示集合 S 元素的数量，也叫集合的基。如 果存在一个整数 n，序列 S 元素的数量可以和 {1,...., n} 一一对应，则我们称该序列是有限 序列。集合和序列不是有限就是无限的。如果有限序列中所有的元素都不同，则称该序列是 由同样元素构成有限集合的一个排列。 这再一次强调了集合和序列的不同。 一个有 n 的元素 的集合有 n！个不同的排列。 一个有 n 个元素的有限集有多少不同的子集呢？记住空集和集合本身。我们有 2 个子 集。 其中基为 k 的子集有多少呢？有一个专门的符号来表示这个量：? ? ? ? ，读作 “n 中选 k”， 或是或者更罗嗦“n 个中一次选 k 组合的数量”。 也使用符号 C(n,k)， 这个量称为二项式系数。 计算 ? ?k? ? 或 C(n,k)的表达式（译者：这里对表达式的推倒说了半天，排列组合的知n? n? ?k?? n? ? ?识大家都应该学过了，直接给出结论。主要是为了偷懒）? n ? n(n ? 1)...(n ? k ? 1) n! C (n, k ) ? ? ? 其中n ? k ? 0 ?k ? ?? k! (n ? k )!k! ? ?从 0 到 n 每一个数对应子集的数量都知道，我们得到n k ?0(1.1)?? ?k? ??2? ??n?n(1.2)-9-元组和叉积元组是一个有不同类别元素的有限序列。 例如在一个二维平面上的点可以表示为一个有序对（x,y） 。如果是几何平面，x 和 y 都是长度。如果是一个问题大小和运行时间的曲线图， 则 y 可能是秒，x 可能是一个整数。短元组有特定的名字对、三元组、四元组等等（英文中 有 pair、triple、quadruple 等词） 。在元组的上下文里，这些词（指上面那些词，译成汉语有 意义十分明确了）是有序的，在其他上下文中“对”可能表示“两个元素的集合”而不是“两个 元素的序列”。一个 k-元组是有 k 个元素的元组。 两个集合 S 和 T 的叉积，是一个对的集合，该集合中对的第一个元素一定来自 S，第二 个元素一定来自 T。我们将叉积写成：S ? T ? {( x, y ) | x ? S , y ? T }(1.3)因此| S×T| = | S | | T |。两个集合 S 和 T 通常是一样的，但这不一样也可以。我们可以定义叉 积迭代，就可以产生更长的元组。例如，S×T×U，将得到一个由三元组组成的集合，三元组 的元素分别来自 S、T 和 U。关系和函数关系是叉积的一个简单子集。 这个子集可以是有些也可以是无限的， 可以是空集也可以 是叉积本身。最重要的关系是二元关系，他是简单叉积的子集。许多二元关系的例子都是我 们非 常 熟 悉 的 ， 例 如 实 数 的 “ 小于 ” 关系 。 以 R 表示 实 数 ， “ 小于 ” 关系 可 以 定 义 成 {( x, y ) | x ? R, y ? R, x ? y} 。就像我们看到的，他是 R×R 的子集。另一个例子，P 表示所 有的人，P×P 表示所有的一对人。我们可以定义“父子关系”（x,y） ， 或 是 “爷孙关系”，他们 都是 P×P 的一个子集。 尽管许多二元关系的两个元素都有相同的类型，但这不是必须的。{( x, y ) | x ? S , y ? T } 也是二元关系。回顾我们早先的图表的例子，就是一个程序规模和程序运行时间的关系。另一个例子，我们将 F 定义为所有的女人， “母子关系”就是 F×P 的子 集。 尽管关系可以是任意子集，但是两个元素都来自一个集合的关系 R，有许多令我们感兴 趣的特性。因为标准的关系是一个中间符号（比如 x&y） ，符号 xRy 常用于表示 ( x, y ) ? R 。 定义 1.2 关系的重要属性 令 R ? S ? S ，下面是一些特性以及特性的条件。自反性对于所有 x ? S ，有 ( x, x) ? R 。对称性( x, y ) ? R ，则 ( y, x) ? R 。 ( x, y ) ? R ，则 ( y, x) ? R 。反对称性- 10 -传递性( x, y ) ? R 且 ( y, z ) ? R ，则 ( x, z ) ? R 。和可传递 的，则称关系为全等关系，如果一个关系是 自反、对称 记做 ? 。注意， “小于”关系是传递和反对称的， 而“小于或等于”是传递和自反的， 但不反对称 （因 为 x ? x） 。 “等价”关系在很多问题里面都是重要的，因为这样的关系 划分底层集合 S；也就是说， 他将集合 S 划分成一组不相交子集（也叫等价类）S1,S2........，S1 中所有的元素都都等价于 集合中的其他元素，S2 中所有的元素也都等价于其他元素等等。例如，如果 S 是非负整数 的集合， R 定义为 {( x, y ) | x ? S , y ? S , ( x ? y )能被3整除} ，则 R 等价于 S。因为（ x-x ） 可以被 3 整除，如果（x-y）可以被 3 整 除 ， （ y-x）也可以，最后（x-y）和（y-x）可以被 3 整除的话， （ x-z）也可以。所以 R 满足等价关系的条件。R 如何划分 S 呢？可以分为 3 组 ， 按除以 3 的余数分。所有除以 3 余数相等地元素都等价。 既然二元关系是二元组的集合，经常将他写成一张两列的表，每一行是一个二元组。函 数是一个关系，这个关系第一列中的元素不会在关系中出现。 许多涉及二元关系的问题都可以转换成一个图上的问题。 图问题构成一大类很有挑战性 的算法问题。例如，在一个有很多相互关联的小任务的大工程里面，我们有很多形如“任务x 必须在任务 y 完成以后才可以开始”的条件。有固定的人来完成任务，如何安排来在最短时 间内完成？在后面的章节中我们将遇到很多这样的问题。1.3.2 代数和微积分工具本节提供关于对数、概率、排列、求和公式、数列级数（在这里，级数指数列的和）的 定义和一些基本特性。 我们将为第三章中的递推方程介绍数学工具。 你可以在本章后面的注 意和参考找到这里没有的公式。Floor 和 Ceiling 函数对于实数 x， ?x ? （x 的 floor）是大于或等于 x 的最大整数。 ?x ? （x 的 ceiling）是小于 或等于 x 的最大整数。例如 ?2.9? ? 2 ， ?6.1? ? 7 。对数对数函数，通常以 2 为底，是本书中经常用到的数学工具。尽管在自然科学中对数不总 是使用，他们在计算机科学中很流行。 定义 1.3 对数函数和对数底- 11 -对于 b&1，x&0， log b x （读作以 b 为底 x 底对数）是一个实数 L， 满足 b ? x 。 下列对数的属性可以从对数的定义简单的得到。 引理 1.1 令 x 和 y 是任一非负实数，令 a 是任一实数，令 b&1，c&1 的实数。 1.Llog b 是单调递增函数，就是说，如果 x&y，则 log b x ? log b y 。 log b 是一个一一对应函数，即如果 log b x ? log b y ，则 x=y。 log b 1 =0 log b b a =a log b ( xy ) ? log b x ? log b y log b ( x a ) ? a log b x2.3.4.5.6.7.x log b y ? y log b xlog b x ? (log b x) /(log b c)8.既然 以 2 为底 的 对 数 在 计 算 复 杂 性 中 用 的 最 多 ， 特 别 为 他 指 定 一 个 记 号 “ lg ”lg x ? log 2 x 。自然对数（以 e 为底）表示为“In”；就是说，Inx= log e x 。当 log(x)步标注底时，意味着对于底为任何数的情况都适用。 有时对数函数自己进行复合。符号 lglg(x)表示着 lg(lg(x))。符号 lg 所以 lg(2) ( p)( x) 表示复合 p 次，( x) 等同于 lglg(x)。主义 lg ( 3) (65536) ? 2 ，而不是 (lg(65536)) 3 ? 4096 。尽管在上文中我们总是对一个整数求对数， 没有用一个负数， 我们经常用一个整数值作 为对数的底。令 n 是一个负数。如果 n 是 2 的幂，让 n ? 2 ，对于有些整数 k ，则有klg n ? k 。如果 n 不是 2 的幂，则有一个整数 k 使得 2 k ? n ? 2 k ?1 。在这种情况下，?lg n ? ? k 且 ?lg n? ? k ? 1 。表达式 ?lg n ? 和 ?lg n? 将经常使用。你必须验证下面的不等式：- 12 -n ? 2 ?lg n ? ? 2nn ? 2 ?lg n ? ? n 2最后，这里有一些有用的结论： lg e ? 1.443 ， lg10 ? 3.32 。In(x)的导数是 1/x。使用 引理的第八条，lg(x)的导数是 lg(e)/x。排列n 个不同对象的一个排列是包含每一个对象的序列。令 S ? {s1 , s 2 ,....s n } 。注意 S 的元 素以他们的索引排序；就是说 s1 是第一个元素， s 2 是第二个元素等等。S 的一个排列是从 集合 {1,2….,3} 到自己的一个一一对应函数π。我们将π看作通过将第 i 个元素 si 移动到 π(i) 的 位 置 ， 重 新 排 列 S 得 到 。 我 们 可 以 通 过 列 出 他 的 值 来 简 单 的 描 述 π ，(? (1),? (2).....? (i)) 。例如，对于 n=5，π＝（4，3，1，5，2）是以 s3 , s5 , s 2 , s1 , s 4 排列 S得到的。 N 个不同对象的排列总数是 n!。 第一个元素可以移动到 n 个位置中的任意一个， 第二个 有 n-1 种选择…，总数是 n×（n-1）×（n-2）× …×2×1＝n!。概率假设在给定的状况下， ，一个事件，或试验有一个或 k 个结果， s1 , s 2 , s3 ,...s k 。这些结 果叫基本事件。所有基本事件的集合叫事件空间（universe）以 U 标记。对每一个 si 我们关 联一个实数 Pr( s i ) ，叫 si 的概率，有如下性质：0 ? Pr( s i ) ? 1 其中 1 ? i ? k ； Pr( s1 ) ? Pr( s 2 ) ? ... ? Pr( s k ) ? 1很自然的， 令 Pr( s i ) 为 s i 出现的次数和总试验次数的比值。 （Note, However, that the definition does not require that the probabilities correspond to anything in the real world. 译 者 ： “概率对应 现实世界的任何事 anything” ？ ！ ）事 件 s1 , s 2 , s3 ,...s k 被称为相互独立事件，因为至多只有 一个事件会发生。 经常使用的展示概率含义的例子有，投硬币、投骰子以及在玩扑克牌时的各种事件。事 实上最开始概率理论就是从法国数学家 Blaise Pascal 对赌博游戏的研究开始的。 如果 “试验”- 13 -是投掷一个硬币，则硬币可能出现“正面”朝上和“背面”朝上。我们令 s1 ,=“正面”，s2 =“背面”并假定 Pr( s1 ) ? 1 / 2 ， Pr( s 2 ) ? 1 / 2 。 （因为硬币不可能以边立在地上，我们可以令 s3 =“边”， Pr( s 3 ) ? 0 。但是即使有无穷次试验，发生概率为 0 的事件也不产生影 响，所以基本上不定义这样的基本事件。 ）如果投掷六面骰子，则有六种可能的结果：1 ? i ? 6 ， si =“骰子以数字 i 朝上”， Pr( si ) ? 1 / 6 。一般情况下，如果有 k 种可能的结果 ，每个结果发生的概率都相等，则对于每一个 i 令 Pr( si ) ? 1 / k 。通常没有理由认为所有结果 等概率；主要是在例子种做这样的假设，或没有数据做出更好的判断之前做等概率假设。 如果试验包含许多对象，则基本事件必须对所有观测到的事件计数。例如，如果有两个 骰子，A 和 B 一起投掷，则事件“A 以数字 1 朝上”就不是基本事件，因为 B 可以有多个 结果 。 这 种 情 况 下 ， 基 本 事 件 必 须 是 s ij = “ A 以数 字 i 朝上 ， 且 B 以数 字 j 朝上 ”1 ? i, j ? 6 ，我们简写为“A 出现 i，且 B 出现 j”。此时有 36 个基本事件，每个基本事件发生的概率是 1/36。 我们经常需要考虑几个特定结果发生的概率，或是有特定属性的结果发生的概率。令 S 是基本事件 {s1 , s 2 ...s k } 的一个子集，则 S 叫事件，且 Pr( S ) ??si ?SPr( s i ) 。例如，假设投 一 个 骰 子 ， 定 义 事 件 S 是 “ 出 现 可 以 被 3 整 除 的 数 字 ”。 则 S 的 概 率 是Pr( S ) ? Pr({s3 , s 6 }) ? Pr( s3 ) ? Pr( s 6 ) ? 1 / 3 ，基本事件也是事件。两个特殊的事件是 必然事件， U ? {s1 , s 2 ...s k } ，他的概率是 1，和不可能事件Φ，他 的概率是 0。 （ Φ也表示空集。 ）对于所有的事件 S，有一个补事件“非 S”，由所有不再 S 中 的事件组成，即 U-S。显然 Pr(not S)=1-Pr(S)。 事件可以通过同组的其他使用逻辑连词“与”和“或”来定义。事件“ S1 和 S 2 ”是( S1 ? S 2 ) ， S1 和 S 2 的交集。事件“ S1 或 S 2 ”是 ( S1 ? S 2 ) ，是 S1 和 S 2 的并集。我们经常需要分析分析一些带权的概率， 权值是基于试验的知识确定的。 这叫条件概率。 定义 1.4 条件概率 给出事件 T 的情况下事件 S 条件概率定义为Pr( SandT ) Pr( S | T ) ? ? Pr(T )si ?S ?T? Pr(s )i js j ?T? Pr( s)（1.4）这里 s i 和 s j 包括基本事件。- 14 -例 1.3 两个骰子的条件概率 假设在试验中投掷两个骰子，A 和 B。我们定义 3 个事件：S1 ：“A 是 1” S 2 ：“B 是 6” S 3 ：“A 和 B 数字的和小于等于 4”为了得到条件概率的概念，让我们考虑所有基本事件都等概率的简单情 况 。 对 于 我 们 的 例 子 ， 36 个 基 本 事 件 是 “ A 是 i ， 且 B 是 j ” ，1 ? i, j ? 6 。则条件概率 Pr( S1 | S 3 ) 可以解释成这样一个问题，“ S 3 中所有的基本事件，也在 S1 中的比例？” 让我们列出所有在 S 3 中基本事件： “A 是 1，且 B 是 1”，“A 是 2，且 B 是 1”， “A 是 1，且 B 是 2”，“A 是 2，且 B 是 2”， “A 是 1，且 B 是 3”，“A 是 3，且 B 是 1”。 事件 S1 由 6 个基本事件组成，即 A 是 1，而 B 是所有可能的 6 个数 字。三个 S 3 中的基本事件也在 S1 中，所以问题的答案是 3/6，1/2。根据 等式（1.4）可以计算出给出 S 3 时 S1 发生的概率Pr( S1 | S 3 ) ?3 / 36 ? 1/ 2 。 6 / 36注意，给出 S 3 时 S 2 发生的概率是 0，即 Pr( S 2 | S 3 ) ? 0 。 一般情况， 计算条件概率的过程是消去指定事件之外的所有事件， 之后通过通用的因子 来调整剩下的事件， 使得调整之后概率和为 1。 （ 原 文 ：In general, the procedure for calculating conditional probabilities given some specified event S is to eliminate all the elementary events by the same factor so that the rescale the probabilities sum to 1.）要求的因子是 1/Pr(S)。 事件的条件概率可能比事件的非条件概率要大或是小。在例 1.3 中 S1 的非条件概率是 1/6，在给出 S 3 的情况下条件概率是 1/2。另一 方面 ， “A 的数字能被 3 整除”的非条件概率- 15 -是 1/3。但是在例 1.3 中，我们看到给出 S 3 的情况下“A 的数字能被 3 整除”的条件概率是 1/6。 定义 1.5 相互独立 给出两个事件 S 和 T，如果Pr( SandT ) ? Pr( S ) Pr(T )则 S 和 T 是相互独立事件，或者简称相互独立。 如果 S 和 T 是相互独立事件，则 Pr( S | T ) ? Pr( S ) （参见练习 1.8） 。就是说，事件 T 的发生不以任何方式影响事件 S 发生的概率。当独立属性存在时他非常有用，因为他使得 可以分开分析两个不同事件的概率。但是，当错误的假设了独立属性时，将产生许多错误的 分析结果。 例 1.4 相互独立事件 继续我们在例 1.3 中的事件定义，事件 S1 和 S 2 是相互独立的，因为 每一个的概率都是 1/6，而且（ S1 and S 2 ）组成一个基本事件，他的概率 是 1/36。注意， Pr( S1 | S 2 ) ? (1 / 36)(6 / 36) ? 1 / 6 ? Pr( S1 ) 。 从例 1.3 的讨论，我们可以看出 S1 和 S 3 不是相互独立事件， S 2 和S 3 也不是相互独立的。随机变量和他们的期望值在涉及概率的许多情况下都是很重要的。 一个随机变量是一个 与事件是否发生相关的实数函数；就是说，他是一个为事件定义的函数。例如，如果一个算 法执行操作的数目倚赖于输入， 每一个可能的输入都是一个事件， 而操作的数目是随机变量 。 定义 1.6 期望和条件期望 令 f(e)是一个随机变量定义在一套基本事件 e ? U 上。f 的期望，标 记为 E(f)，定义为E ( f ) ? ? f (e) Pr(e)e?U这常被称为 f 的平均值。给出事件 S 后 f 的条件期望标记为 E(f | S)， 定义为E ( f | S ) ? ? f (e) Pr(e | S ) ? ? f (e) Pr(e | S )e?U e?S- 16 -因而任何不再 S 中的事件的条件概率是 0。 期望常常比随机变量本身容易处理， 特别是当涉及几个相互联系的随机变量时。 得出下 面的一条重要规则，他可以从定义上简单的得到证明。 引理 1.2 （期望法则）对于定义在一套事件 e ? U 上的随机变量 f(e) 和 g(e)，以及任意事件 S：E( f ? g ) ? E( f ) ? E( g) E ( f ) ? Pr( S ) E ( f | S ) ? Pr(notS ) E ( f | notS )例 1.5 条件概率和顺序 在第四章我们将把通过比较得到的顺序信息和概率连起来考虑。 让我 们看一个这种类型的例子，这个例子涉及 4 个元素 A、B、C、D，都是互 不相同的数值， 但是开始我们不知道他们值和关系的任何信息。 我们将以 字母的顺序来标记基本事件， 基本事件是他们的关系顺序； 就是说 CBDA 表示 C&B&D&A。有 24 种可能的结果： ABCD ACBD CABD ACDB CADB CDAB ABDC ADBC DABC ADCB DACB DCAB BACD BCAD CBAD BCDA CBDA CDBA BACD BDAC DBAC BDCA DBCA DCBA 我们从假设所有输入结果都是等概率开始，则每个事件的概率都是 1/24。A&B 的概率是多少？换句话说，将 A&B 定义为事件，其概率是多 少。凭直觉，我们期望他是 1/2，可以通过统计 A 出现在 B 之前的结果数 量来验证。 同样的， 对于每一对元素， 其概率至少是 1/2， 例如， 事件 B&D 的概率是 1/2。 现在假设程序比较 A 和 B，发现 A&B。这对概率的影响如何？为了 使这个问题更严格，我们将他表述成“在事件 A&B 下的条件概率是多 少？”。通过检查我们看到组成 A&B 的基本事件都在表的前两行。因此 在给 出 条 件 A&B 的情 况 下 ， 基 本 事 件 的 条 件 概 率 是 原 来 的 两 倍 ， 2/24=1/12，但在给出 A&B 的情况下，后两行的基本事件的条件概率是 0。 回到先前的比较，事件 B&D 的概率是 1/2 。我们没有比较 B 和 D 。 给出 A&B 的情况下 B&D 的条件概率是否还是 1/2？为了回答这个问题， 我们检查在前两行中 B 在 D 前面的结果有几个。事实上，只有四个。所 以 Pr(B&D|A&B)=1/3。 现在考虑事件 C&D。他的条件概率是不是也不是 1/2？再一次检查表 的前两行， 我们检查到 C 出现在 D 之前共有 6 次， 所以 Pr(C&D|A&B)=1/2。 因此事件 A&B 和 C&D 是相互独立的。 这正是我们期望的： A 和 B 的关联 顺序“不对”C 和 D 的顺序产生任何影响。- 17 -最后，假设程序作了另一个比较，发现 D&C（已经发现了 A&B） 。 让我们检查在同时给出这两个事件情况下的条件概率 （就是说给出单独一 个事件“A&B 且 D&C”）。通过检查我们看到事件“A&B 且 D&C”由表 第二行的元素组成。为了使得条件概率的和为 1，所有基本事件都必须有 1/6 的条件概率。 程序不比较 A 或 B 也不比较 C 或 D。 这是否意味着事件 A&C、A&D、B&C 和 B&D 的条件概率不变都是 1/2？答案在练习 1.10 给 出。 例 1.6 逆序数的期望数值 考虑象例 1.5 那样的概率空间。让我们定义随机变量 I(e)为一组元素 中关联顺序与他们的字母顺序相反的字母的个数。这个叫做结果的 逆序 数。例如，I(ABCD)=0，I(ABDC)=1 因为 D&C 但 C 的字母顺序大于 D， I(DCBA)=6 等等 。 通 过 检 查 我 们 看 到 E(I)=3 。现 在 考 虑 E(I|A&B) 和 E(I|B&A) 。 通 过 直 接 计 数 我 们 发 现 他 们 分 别 是 2.5 和 3.5 。 既 然 Pr(A&B)=Pr(B&A)=1/2。 引理 1.2 告诉我们 E(I)=1/2(2.5+3.5)， 这是真命题 。 总结，条件概率反映了在我们知道部分知识的情况下的不确定性。他们的计算步骤是： 消去确认在当前情况下不可能在的基本事件来计算， 然后调整剩下的基本事件的概率使他们 的和为 1。与给出事件相互独立的任何事件，其概率都不会由于这个计算而改变。相互独立 事件经常涉及相互补影响的对象（比如，多次投硬币，多次投骰子） 。级数与求和在分析算法的时候，有几个求和公式经常用到。在本小节和下一小节中列出他们，在这 里简单的描述他们有助你记住他们，注意这个术语：级数就是一个数列的和。 算术级数：连续整数的和。n?i ?i ?1n(n ? 1) 2(1.5)如何记住他：写出 1 到 n 的整数。首尾两两相加， 1+n，2 +n-1，3+n-2 等等。每一对都是 n+1，共有 n/2 对。 （如果 n 是奇数，中心的元素记为“半对”）这个技巧不仅限于 1 到 n。 多项式级数：首先我们考虑下面平方和。n?i2 ?i ?12n 3 ? 3n 2 ? n 6（1.6）可以通过归纳法证明之。关键是要记住第一项是 n / 3 。文中不用等式(1.6)，但是你可能在 一些练习需要用到。 更一般的是n3?ii ?1k?1 k ?1 n k ?1(1.7)这是一个合理的近似，将在后面的章节讨论。 （对于给定的 k 可以通过归纳法证明。 ）仔细比 较这个和下面的“几何级数”。- 18 -2 的幂：这是最常见的几何级数。k?2i ?0i? 2 k ?1 ? 1i(1.8)如何记住他：把每一个 2 当成二进制数的一位；则k?2i ?0i? 11....1 。k ?1共有 k+1 位。如果给这个数加 1 则是 100…0= 2 公式得到。 ） 几何级数：k。 （结果也可以通过下面的几何级数求和? ari ?0 k i ?0i? r k ?1 ? 1 ? ? a? ? r ?1 ? ? ? ?(1.9)为了验证他，变化右边。作为一种特殊情况，令 r=1/2，我们得到：?21i? 2?1 2k(1.10)一个几何级数的特征是一个常数底和变量幂。多项式级数是一个变量底，常数幂。两者的行 为差异很大。 调和级数：n i ?1? i ? In(n) ? ? ，其中 ? ? 0.577和叫调和数。常数γ叫欧拉常量。参见练习 1.7。i1（1.11）算术－几何级数：在下一个和中，i 将是一个算术级数，而 2 则是一个几何级数，因此名字 。n? i2i ?1i? (k ? 1)2 k ?1 ? 2(1.12)他的推导是一个“部分求和”的例子，他和“部分整数求和”类似。将和重新安排成两个不 同的部分，消去中间部分，只留前后两项。k i ?1 k i ?1? i2 i ?? i(2 i ?1 ? 2 i )k i ?1 k i ?1 k ?1 i ?0? ? i 2 i ?1 ? ? (i ? i )2 i ?1k ?1 i ?0 k ?1 i ?0? ? i 2 i ?1 ? ? i 2 i ?1 ? ? 2 i ?1 ? k2k ?1? 0 ? (2k ?1? 2) ? (k ? 1)2 k ?1 ? 2（1.13）- 19 -Fibonacci 数列：Fibonacci 数列以递归方式定义：Fn ? Fn?1 ? Fn? 2 n ? 2F0 ? 0, F1 ? 1尽管这不是一个和，但是这个在算法分析时经常出现。单调递增函数和凸函数有时非常普通的属性就足以让我们得出关于函数行为的有用的结论。 这样的两个属性是 单调递增和凸。贯穿整个对单调递增和凸的讨论，我们假定都在区间 a ? x ? ? ，其中 a 一 般是 0，但涉及 log 时为 1。所有点都在这个区间之内，f 定义为在这个区间上。域可以是实 数也可以是整数。 定义 1.7 单调函数和非单调函数 一个函数 f(x)，如果对于任意 x ? y 都有 f ( x) ? f ( y ) ，则说函数 f 是单调递增或非递减的。如果函数-f(x)是单调递增的的，则函数 f(x)是单 调递减，或非递增的。 最熟悉的单调递增函数是 x， x 2 ( x ? 0) ， log( x)( x ? 0) 和 e 。不太熟悉的单调函数是x?x ? 和 ?x ? ，这也显示出单调递增函数不一定是连续的。一个单调递减函数的例子 1/x，x&0。定义 1.8 线性插值函数 给定函数 f(x)，他两点 u 和 v 之间间的线性插值定义为如下函数(v ? x) f (u ) ? ( x ? u ) f (v) (v _ u ) f (v) ? f (u ) f (v) ? f (u ) ? f (u ) ? ( x ? u ) ? f ( v ) ? (v ? x ) v?u v?uL f ,u , v ( x ) ?(1.14) 是在 f(u)和 f(v)之间的直线（参见图 1.3a）。(a)线性插值（b）将 f(n)扩展到 f * ( x)*插图 1.3 凸函数的讨论： （a）和（b）中的函数 f 是不同的。在（b）中， f ( x) 凸函数。- 20 -定义 1.9 凸函数 一个函数 f(x)如果是凸的，则对于所有的 u&v，区间（u,v）中所有的f ( x) ? L f ,u ,v ( x) 。非正式的，如果函数 f(x)从不向下弯，则他是凸的。因而象 x，x2，1/x，ex 这样的函数是凸的。图（b）中的函数是凸的（但不是单调的） ， 不管他是在实数上还是在整数上；图（a）中的函数是单调的，但不是凸的。 log( x) 和 x 业不是凸的。那么 xlog(x)呢？下面的引理开发出了一种测试凸函数的实用方法。简单的看 （可以证明的）不连续（discontinuous）函数不能是凸的（译者：那 b？） 。引理 1.3 介绍了 一种只需比较几个空间点就能判断凸的简单方法。证明在练习 1.16 中。 引理 1.3 1. 令 f(x)是一个定义在实数上的连续函数。则当且仅当对于任意两 点 x、y 都有 f ( ( x ? y )) ?1 21 ( f ( X ) ? f ( y )) 时，f(x)是 凸 的 。 2换句话说，f 在 x、y 之间所有的点都比 f 在 x、y 之间的线性插 值函数中间点要小。注意， f 在 x、y 之间的线性插值函数中间 点只是 f(x)和 f(y)的平均值。 2. 函数 f(n)是定义在整数上，当且仅当对于任意 n、n+1、n+2 都有f (n ? 1) ?1 ( f (n) ? f (n ? 2)) 时 f(n)是凸的。就是说 f(n+1)小 2于等于 f(n)和 f(n+2)的平均值。 引理 1.4 总结了单调和凸的许多有用的性质。还说明了将仅定义在实数上的函数通过线 性插值扩展到实数上，而且保留了单调和凸的性质。也说明了一些涉及到导数的性质。证明 在练习 1.17 到 1.19。 引理 1.4 1. f(n)仅定义在整数上。令 f * ( x) 是 f 通过线性插值扩展到实数上 的函数（见图 1.3b）。 a) f(n)是单调当且仅当 f * ( x) 是单调的。b) 2. 3. 4.f(n)是凸的当且仅当 f ( x) 是凸的*如果 f(x)的一阶导数存在且非负，则 f(x)是单调的。 如果 f(x)的一阶导数存在且单调，则 f(x)是凸的。 如果 f(x)的二阶导数存在且非负， 则 f(x)是凸的。 （从 2，3 得到 ）。- 21 -利用积分求和许多求和公式在算法分析时经常用到，可以用积分来近似（上界和下界）他们。首先让 我们回顾一些有用的积分公式：? ?n0x k dx ?n 1 k ?1 1 n ， ? e ax dx ? (e an ? 1) 0 k ?1 an1x k In( x)dx ?1 k ?1 1 n In(n) ? n k ?1 2 k ?1 (k ? 1)(1.15)如果 f(x)是单调递增，则?bba ?1f ( x)dx ? ? f (i ) ? ?i?ab ?1af ( x)dx(1.16)同样的，如果 f(x)是单调递减，则?b ?1baf ( x)dx ? ? f (i ) ? ?i ?aba ?1f ( x)dx（1.17）图 1.4 中展示了这两种情况。后面有两个使用他的两个例子。b? f (i) ? ?i?ab ?!af ( x)dx（a）Over approximation?bba ?1f ( x)dx ? ? f (i )i?a(b) Under approximation 图 1.4 单调递增函数的和近似- 22 -n例 1.7 估计?ii ?1 n1n i ?1? i ? 1? ?11dx n ? 1 ? Inx |1 ? 1 ? Inn ? In1 ? In(n) ? 1 x使用等式(1.17)得到。注意我们分开了和的第一项，对剩下的部分进 行了微分近似。避免了积分下限的除 0 运算。类似的n i ?1? i ? In(n ? 1)参见等式(1.11)取得的更接近的近似。n1例 1.8? lg i 的下界i ?1 n i ?2 nn i ?1? lg i ? 0 ? ? lg i ? ? lg xdx1使用等式(1.16)（参见图 1.4b）。n? lg xdx ? ?1n1(lg e)Inxdx ? (lg e) ? Inxdx1nn ? (lg e)( xInx ? x) |1 ? (lg e)(nInn ? n ? 1)? n lg n ? n lg e ? lg e ? n lg n ? n lg e既然 lg e ? 1.443n? lg i ? n lg n ? 1.443ni ?1（1.18）使用前面例子的思想，但是使用更精确的数学方法，就可以推导出 Stirling’s formula 给 出的 n!的边界：?n? ? ? ?e? 不等式运算n?n? 2?n ? n!? ? ? ?e?n2?n (1 ?1 ) 11n其中 n ? 1（1.19）下列连接不等式的规则经常用到。- 23 -传递性 如果 A ? B 且B ? C 则A?C （1．20）加法 如果 A ? B 且C ? D 则 A?C ? B? D正数缩放 如果 A ? B 且? ? 0 则 ?A ? ?B1.3.3 逻辑元素 1.3.3逻辑是一个形式化自然语言语句的系统， 他使得我们可以更精确的推理问题。 最简单的 命题叫原子公式。更复杂的命题可以使用 逻辑连词来组成。原子公式例如“4&3”，“4.2 是 一个整数”，“x+1&x”。注意一个逻辑命题不一定是真。一个正确的证明才能显示一个命题 是真。 最常用的逻辑连词是 ? （ 与 ） ， ? （或）和 ? （非） ，也叫做布尔运算符。复杂命题的 真值，通过连词的规则从原子命题中推出。令 A 和 B 是逻辑命题，则 1. A ? B 为真，当且仅当 A 和 B 都为真时。 2. A ? B 为真，当且仅当 A 和 B 其中一个为真，或都为真时。 3. ? A 是真，当且仅当 A 为假时。 另一个重要的推理连词叫“推导出（implies ）”，我们用符号“ ? ”来表示他。 （也有时用 “ ? ”。 ）命 题 A ? B 读作“A 推导出 B”，或是“如果 A 则 B”。 （注意这个命题没有“else” 子句。 ） “推导出”运算符可以表示成其他运算符的组合，考虑下面的等价：A ? B 在逻辑上等价于 ?A ? B这可以通过真值表来检验。 一个常用的等价变换叫 DeMorgan 法则：（1.21）?( A ? B) 在逻辑上的等价于 ?A ? ?B ?( A ? B) 在逻辑上的等价于 ?A ? ?B 量词（1.22） （1.23）还有一种重要的逻辑连词， 量词。符号 ?x 叫普遍量词 ，读作“对于所有 x”，而符号 ?x 叫 存在量词 ，读作“存在 x ”。这两个量词可以适用于所有包含变量 x 的命题。命题?xP( x) 为真，当且仅当对于所有 x，P（x）都为真时。命题 ?xP( x) 为真，当且仅当有 x使得 P（x）为真。最经常的，一个普通的量词命题是条件： ?x( A( x) ? B ( x)) 。读作“对 于所有 x，A（x）成立，则 B（x） 也 成 立 。 ” 量词命题服从变相的 DeMorgan 法则：?xA( x) 在逻辑上的等价于 ??x(?A( x)) ?xA( x) 在逻辑上等价于 ??x(?A( x))(1.24) (1.25)- 24 -有时将自然语言转换成量词命题是很麻烦的。 人们说得话并不总是很有逻辑。 我们需要 分清“for any x ”常常意味着“for all x”，尽管“any”和“some”在正常语言中是可交换 的（译者：汉语中也有类似的问题） 。最好的方针是，尝试重新以逻辑语言的形式阐述一句 自然语言，然后问自己是否和自然语言有同样的含义。例如， “任何（any）一个活人都必须 呼吸”，可以阐述为“对所有人 x，x 要活着就必须呼吸”，和“对于有些人 x，x 要活着就必 须呼吸”。那一个和原来的句子意义一样？否定量词命题、反例证明一个一般命题，说 ?x( A( x) ? B( x)) 是错的必要条件是什么？我们可以使用前面 提到的等价条件来阐明目标。首先要认识到没有必要证明 ?x( A( x) ? ?B( x)) 。这是一个 过于严格的命题。否定的 ?x( A( x) ? B( x)) 是 ?(?x( A( x) ? B( x))) ，他还可以进行一系 列逻辑变换：?(?x( A( x) ? B( x))) 在逻辑上等价于 ?x?( A( x) ? B( x))在逻辑上等价于 ?x?(?A( x) ? B( x)) 在逻辑上等价于 ?x( A( x) ? ?B( x)) 换 句 话 说 如 果 我 们 可 以 找 到 一 个 x 使 得 A(x) 为 真 而 B(x) 为 假 ， 则 我 们 就 证 明 了 (1.26)?x( A( x) ? B( x)) 为假。象这样的 x 称为反例。逆否命题（contrapositives ）当试图证明一个命题时， 经常将其转换成逻辑上的等价形式。 其中的一个形式叫做逆否命题。 A ? B 的逆否命题是 (?B) ? (?A) 。方程（1.21）允许我们验证当一个命题为真时他的逆否命题也为真：A ? B 在逻辑上等价于 (?B) ? (?A)(1.27)有时，证明命题的逆否命题，叫“反证法”，但是“反证法”有更精确的描述。 “反证法”的 严谨定义在下一小节中。反证法假定要证明的命题的形式 A ? B 。严谨的反证法先做一个附加假设 B 为假即 ?B ，在 证明 B 自己。这样要证明的全命题就是 ( A ? ?B) ? B 。下面的恒等式证明了这个方法：A ? B 在逻辑上等价于 ( A ? ?B) ? B- 25 -(1.28)在算法分析里很难遇到真真的反证法。但是练习 1.21 遇到了一个。大多数叫反证法的实际 上是证明的逆否命题。推理规则迄今为止我们看到了大量的逻辑等价命题，或是逻辑恒等式：一个命题是真，当且仅当 第二个命题也是真。恒等式是“可逆的”。但是很多证明使用的不可逆命题组合。要证明的 完全命题有“如果前提，则结论”的形式。可逆的“如果结论，则前提”经常不是真的。逻 辑恒等式在证明诸如“如果前提，则结论”的命题时不够灵活。在这种情况下，我们需要推 理规则。 一个推理规则是一个通用的允许我们从一套给定命题中得到新结论的模式。 他可以被阐 述为“如果我们知道 B1 ......Bk ，我们可以总结出 C”，这里 B1 ......Bk 和 C 都是逻辑命题。这 里有几个熟悉的规则： 如果我们知道 B 则我们可以总结出和 B?C C (1.29) A? B 和 A?C B?C (1.30) B?C 和 ?B ? C C (1.31) 有些规则通过他们的希腊和拉丁名字为人所知。等式 (1.29)是 modus ponens, 等式(1.30)是 syllogism， 等式(1.31)是 rule of cases。这些规则不是相互独立的；在练习 1.21 中我们可以 证明 rule of cases 使用了其他规则和逻辑恒等式。1.4分析算法和问题我们分析一个算法的目的是要改进他， 如果可能， 为在解决一个问题重到底选那一个方 法提供依据。我们使用下面的标准 1. 2. 3. 4. 5. 正确性 所做工作的量 使用空间的量 简单，清晰 最优性我们将讨论每一个标准的尺度，并给出应用他们的几个例子。当考虑算法的最优性时，我们 将介绍建立问题最低边界复杂性的技术。1.4.1 正确性建立算法正确性主要有三步。第一，在任何决定一个算法是否正确的企图之前，我们必 须对“正确”有一个清晰的概念。我们需要一个清晰的命题来描述期望有效输入的特性（叫 前提） ，和处理每一个输入的结果（叫后置条件） 。在输入前提条件满足，算法结束之后后置 条件也正确的话，我们尝试证明输入输出关系的命题。 算法有两个方面： 要解决的问题和完成所需要的指令序列， 也就是他的实现。 Establishing- 26 -the correctness of the method and/or formulas used may be easy or may require a long sequence of lemmas and theorems about th objects on which th algorithm works (e.g. gtaphs,permutations, matrices).（译者：这句话不太明白，好像是说： “要建立方法的正确性，阐明使用的关于算 法处理对象（例如图、排列、矩阵）的引理和定理，以及如何使用这些理论。 ”）例如，应用 高斯消去法解系统的线性方程的有效性， 依赖于一大堆线性代数的定理。 在本书的算法中使 用的方法不是显然正确的；他们必须被定理证明。 一旦建立了方法，我们用程序实现他。如果一个算法短小，简洁很有美感，我们一般只 使用非正式的含义来使自己相信， 其他的输入也会象我们期望的一样得到正确的结果。 我们 可能会仔细的检查一些细节（例如循环计数器的初值和终值） ，以及用一个简单的例子手工 演算算法。这些都不能证明算法的正确性，但是非正式方法对于一些小的程序就足够了。更 加正式的技术，比如循环不变式（loop invariants） ，可能会用来验证部分程序。3.3 节扩展了 这个话题。 大多数写在类外面程序非常大而复杂的。 为了证明大程序的正确性， 我们可以尝试将程 序分解比较小的模块； 这样的话， 如果所有的小模块都正常的工作， 那么整个程序是正确的 ； 剩下的工作就是要证明每一个小模块的正确性。这样只要算法和程序是以模块形式写成的， 而且模块相互独立，可以分开验证，任务就简单多了（更精确的说法是“只有这样的时候， 任务才是可能的 ”） 。这是许多强壮的算法是结构化、模块化的原因之一。本书中的大多数 算法都是小片断组成的，这样我们就不必处理困难的巨型算法的证明。 本书中， 我们不总是正式的证明， 有时候给出主题， 或是算法中困难或复杂部分的解释 。 正确性是可以证明的，尽管对于长、复杂的程序而言这是一个可怕的任务。在第三章我们将 介绍一些技术来帮助进行证明。1.4.2 所做工作的量如何度量一个算法的工作量？这个我们选择的度量应该能帮助我们比较解决同一个问 题的两个算法， 这样我们就能决定到底那一个方法更有效。 如果我们比较两个算法的实际执 行时间来度量两者所作工作的量将很简单， 但是有很多原因使我们不能用执行时间来作为工 作的度量。 首先当然是， 他随使用的计算机而变化， 而我们不想为一种计算机开发一种理论 。 我们可以用程序执行的指令数或语句的数量来代替执行时间。 他严重依赖于使用的程序设计 语言和程序员的编码风格。 他还需要我们花费时间和精力为每一个要研究的算法编写调试程 序。 我们想要一种工作量的度量方式， 他可以告诉我们算法使用方法的效率而不依赖计算机 、 程序设计语言和程序员，但也不依赖于许多具体的实现细节，比如增加循环计数器的开销、 计算数组索引以及设置数据结构指针的开销。 我们的工作量度量必须足够的精确、 足够的普 通，一致我们可以开发出一种可以用作许多算法和应用程序的丰富的理论。 一个简单的算法可能由许多初始化构造和循环组成。 对于这样一个算法来说， 循环体执 行的次数是一个公平指示工作量的好的度量。 （译者：原文 “ The number of passes made through the body of the loop is a fairly good indication of the work done by such an algorithm. ”） 当然， 一次循环内的工作量和其他循环次数中可能不一样， 一个算法可能有比其他算法大的 循环体，但是我们只限于良好的工作量的度量。尽管有些循环有 5 步而有些是 9 步，但循环 次数巨大时， 一次循环的步数就显得不重要了。 因此统计一个算法循环的次数是一个好主意 。 在许多时候，为了分析一个算法，我们可以隔离出一种解决所研究问题的基本操作（或 者是算法的组成类型） ，忽略初始化、循环控制和其他额外开销，仅仅统计算法执行的选择- 27 -的基本操作的量。对于许多算法，每一次循环执行一次这样的操作，所以这种度量与前一段 描述的比较类似。 这里的例子是对于几个问题合理基本操作的选择： 问题 在一个数组中查找 x 两个实数矩阵相乘 数组排序 遍历一二叉树（参见 2.3.3 节） 任一迭代过程，包括递归 操作 比较 x 和数组中的元素 两个实数作乘法（或者是乘法和加法） 比较数组的两个元素 遍历边 过程调用只要选定了基本操作， 就可以粗略的估计出执行基本操作的数目， 我们有了一个度量算法工 作量的好标准，以及一个比较算法的好标准。这是我们在本章和其他章节中使用的方法。你 可能还是不认同这是一个好的选择；在下一节中我们将列出他合理的另一个例子。现在，我 们简单的摆出这个观点。 首先，有些情况下，我们本来就对基本操作感兴趣：可能是一个花费昂贵的比较操作， 或者可能因为一些理论上的兴趣。 其次， 我们经常对随输入的增大算法所消耗时间增大的变化率感兴趣。 只要得到总操作 数量和基本操作数量粗略的比例， 合理的计算就可以让我们对算法对于大输入要计算多久又 一个相当清晰的概念。 最后，这种工作量的度量带了很大的灵活性。尽管我们经常选择一个或最多两个操作， 我们可以包括一些开销巨大的操作， 极端的， 我们可以选择特定计算机的一套指令作为基本 操作。另一种极端情况，我们可以将“一次循环”作为基本操作。因此，通过多样的基本操 作的选择方法，我们可以在分析中改变精确和抽象的程度来适应我们的需要。 如果我们为一个问题选择一个基本操作， 然后发现算法指向操作的总数不于基本操作的 数目成比例， 怎么办？如果基本操作的开销很大怎么办？在极端情况下， 我们可能为一个特 定的问题选择了一种基本操作，然后我们发现解决这个问题的有些算法使用完全不同的操 作， 而根本不使用我们要统计的操作。 这时我们有两个选择。 我们可以放弃关注特定的操作 ， 转向统计循环的次数。或者，如果我们对选择的操作特别感兴趣，我们可以将我们的研究范 围限定在适用该操作的一类算法内。 对于使用与选择基本操作不同技术的其他算法， 应该个 别的处理。对于一个问题的一类算法，经常通过要处理的数据的基本操作来定义（译者：原 文 A class of algorithm for a problem is usually defined by specifying the operations that may be performed on the data.） 。 （选择基本操作正式的程度是多样的；本书中经常使用非正式的描 述。 ） 在这一节中，我们经常使用短语“算法所作工作的度量”。他可以用术语“一个算法的 复杂性”来代替。复杂性意味着做了多少工作，通过一些特殊的复杂性度量方式来度量，在 我们大多数的例子中是用的特定基本操作执行的数量。 注意， 这里复杂性与算法有多复杂多 棘手无关； 一个非常复杂的算法可能有很低的复杂性。 我们将使用术语 “复杂性”，“工作量” 和“所作基本操作的数量”，在本书中这几个术语都是可替换的。1.4.3 平均和最坏分析现在我们有了分析一个算法工作量的一般方法，我们需要可以简明展示分析结果的途 径。工作量不能用一个简单数值来描述，因为对于不同的输入执行的步数不一样。我们首先 观测到工作量依赖于输入量的大小。例如，使用同样的算法，按字母排序 1000 个名字需要- 28 -的操作肯定比按字母排序 100 个名字要多。 接一个 12 阶 12 元线性方程肯定解 2 阶 2 元线性 方程做的工作要多。其次，我们观察到，即使我们仅考虑一个固定的输入规模，操作执行的 数目还是可能依赖于你到底输入的是什么。 如果在数组中只有少数名字不按顺序、 在前面的 例子中的算法就只需要做很少的工作，但是如果数组十分混乱，就不得不做很多的工作。如 果大多数系数都是 0，解一个 12 阶线性方程也不需要很多工作。 第一个观察指出， 我们需要一种度量输入规模的标准。 选一个合理的输入规模的度量通 常是很容易的。这里有一些例子： 问题 在名字数组中查找 x 两个矩阵乘法 遍历二叉树 解系统的线性方程 一个关于图的问题 输入的规模 数组中名字的个数 矩阵的维数 树节点的数量 等式的数量，或未知数的数量，或者两者 图节点的数量，或边的数量，或者两者即使输入规模固定，比如 n，操作执行的数量还是依赖于到底输入了什么。那么到底如何表 示算法分析的结果呢？我们经常用最坏情况复杂性来描述算法的行为。 定义 1.10 最坏情况复杂性 令 Dn 是所考虑问题的规模为 n 的输入集合，I 是 Dn 的一个元素。令 t(I)，是对于输入 I 要执行的基本操作的数量。我们定义函数 WW (n) ? max{t ( I ) | I ? Dn }函数 W(n)叫做算法的最坏复杂性。W(n)是算法对于规模为 n 的输入所要 做基本操作的最大数量。 通常计算 W(n)是很复杂的。1.5 节介绍了一种当精确计算十分困难时常用的技术。最坏 复杂性是很有价值得， 他给出了算法所作工作量的上限。 最坏分析可以用于帮助估计一个算 法特定实现的时间限制。对于本书中出现的大多数算法，我们都将进行最坏分析。除了特别 指出，当我们说一个算法的工作量时，都是指最坏情况时的工作量。 似乎更有用、更自然的描述算法行为的方法是指出他的平均工作量；就是说，计算规模 为 n 的所有输入的基本操作执行的数量， 然后取平均。 实际中一些输入出现的频率要高于其 他输入，所以带权平均更有用。 定义 1.11 平均复杂性 令是输入 I 出现的概率。则算法的平均行为定义为A(n) ?I ?Dn? P ( I )t ( I )r我们通过分析算法来决定 t(I) ，但是 Pr ( I ) 不能通过分析计算。函数 Pr ( I ) 取决于经验 以及具体使用算法的应用，或者只能通过简单的假设（例如，所有情况等概率） 。如果Pr ( I ) 很复杂，计算平均行为将很困难。当然，如果 Pr ( I ) 依赖于使用算法的应用，函数 A- 29 -描述的算法的平均行为仅对该应用适用。 下面的例子展示了最坏和平均分析。 例 1.9 在无序数组中查找 问题：令 E 是包含 n 个元素的数组（关键字）， E[0],E[1]… E[n-1]， 其中元素是无序的。查找关键字为 K 的元素，如果 K 在数组中，返回索 引号；如果 K 不再数组中返回－1。（将在 1.6 节中研究元素是有序时的 情况。） 策略：依次将数组的元素与 K 比较，直到找到一个匹配的，或者到 达数组尾。如果 K 不再数组中返回－1，否则算法返回索引号。 有一大类过程和这个类似， 我们叫这些过程为普通查找例程。 通常他们的子程序要复杂 的多。 定义 1.12 普通查找例程普通查找例程是一个处理不确定数量数据的过程， 一直到数据处理完 或是得到目标。下面是大概的算法：如果没有数据了：失败。否则 处理一笔数据。 如果得到我们想要的：成功。否则继续处理剩余的数据。之所以叫普通查找例程，是因为例程经常执行诸如查找、移动元素、 增加删除元素之类的简单操作。 算法 1.1 顺序查找，无序的 输入：E、n、K，这里 E 是一个有 n 个元素的数组（索引号从 0，… n-1），K 是要查找的条目 。为了简化问题，我们假定 K 和 E 的元素都 是整数，和 n 一样。 输出：返回 ans，指示 K 在 E 中位置（如果 K 没有找到，返回－1）。 int seqSearch(int[] E, int n, int K) { 1 t ans, int in- 30 -2 3ans= -1; for( index=0; index&n; ++index) {4if(K= =E[index]) {5 6 } } 7ans=}（译者：实在不习惯不加{},都给加上了。） 基本操作：比较 x 和数组的元素。 最坏分析：显然 W(n)=n，最坏情况是在数组的最后一个元素才与 K 匹配的， 或者根本没有一个元素符合条件。这两种情况都将导致要比较 K 和所有 n 个元素。 平均行为分析： 我们将做一些简单的假设来分析第一个例子， 稍后再 以不同的假设分析比较复杂的第二个例子。 我们就假定数组中所有的元素 都不相同，则如果 K 在数组中他将只和其中一个元素相等。 对于我们的第一种情况，我们假设 K 在数组中，我们用“succ”来表 示这一事件，和 1.3.2 节中概率的术语保持一致。输入可以根据 K 到底再 那里出现来分类，所以有 n 个要考虑的输入。对于 0 ? i ? n ，令 I i 表示 K 出现在数组第 i 个位置的事件。令 t(I) 为输入 I 时算法进行比较的次数 （即程序中 K= =E[index]的次数）。显然对于 0 ? i ? n , t ( I i ) ? i ? 1 。因 此n ?1 n ?1 1 1 n(n ? 1) n ? 1 Asucc (n) ? ? Pr ( I i | succ)t ( I i ) ? ? ( )(i ? 1) ? ( ) ? n n 2 i?0 i ?0 n脚标“succ”表示，我们假定在本次计算中完成了查找。结果符合我 们平均的直觉，大约数组的一半将被查找。- 31 -现在让我们考虑事件 K 不在数组中的情况，我们称为“fail”。对于 这种情况只有一种输入，我们称为 I fail 。比较的次数 t ( I fail ) ? n ，所以A fail ? n 。最后，我们结合 K 在数组中和 K 不在数组中两种情况。令 q 是 K 在 数组中的概率。根据条件期望定律（Lemma 1.2）：1 1 1 A(n) ? Pr ( succ) Asucc (n) ? Pr ( fail ) A fail (n) ? q( (n ? 1)) ? (1 ? q)n ? n(1 ? q) ? q 2 2 2如果 q=1， 即 K 总在数组中， 则 A(n)=(n+1)/2， 和前面 一样 。 如 果 q=1/2， 即 50％的机会 K 不在数组中，则 A(n)=3n/4+1/4；大概要检查 3/4 的数组 元素。这是例 1.9 的结论。 例 1.9 展示了我们如何解释规模为 n 的输入集合 Dn 。我们仅考虑了影响算法行为的输 入，即 K 在不在数组中以及 K 出现的位置，而不是所有可能的名字和数组大小。 Dn 中的 一个元素 I 可以认为是一个 K 在指定位置出现的数组的集合（或等价类） 。则 t(I)是对于输 入 I 的基本操作执行的次数。 显然，造成算法有最坏行为的输入依赖算法本身，而不是问题。对于算法 1.1 当 K 在数 组的最后一个位置时，最坏情况发生。对于按逆序查找的算法（例如，从 index==n-1 开始）， 当 K 出现在数组最前面时发生最坏的情况。 （另一种最坏情况发生的条件是 K 不在数组中。 ） 最后，例 1.9 展示了在进行查找和排序的平均分析时经常用到的假设；所有的元素都是 不同的。 对不同元素的平均分析给出了对重复元素较少情况的的比较接近的平均行为。 如果 这里有很多重复元素，就很难对 K 第一次出现在数组的什么地方做出合理的假设。 例 1.10 矩阵乘法 问题：令 A=(aij)是一个 m×n 矩阵，B=(bij)是一个 n×p 矩阵，两者都 是实数矩阵。计算矩阵 C=AB。（这个问题在第十二章中大量讨论。在许 多情况下，我们假设矩阵是方阵，即 m=n，p=n。） 策略：根据矩阵积的定义使用下面的算法：n ?1cij ? ? aij bkjk ?00 ? i ? m,0 ? j ? p算法 1.2 矩阵乘法 输入：矩阵 A 和 B，整数 m,n,p，其中 A 是一个 m×n 矩阵，而 B 是 一个 n×P 矩阵。 输出：矩阵 C，m×p 矩阵。C 被传递进来，算法填充之。 matMulit( A,B,C, m, n, p)- 32 -{ for(i=0; i&m;++i) { for(j=0;j&p;++j) { cij=0; for(k=0;k;k&n;k++) cij+=aik*bkj } } } 基本操作：矩阵元素的乘法 分析：为了计算 C 的每一个元素，要做 n 次乘法。C 有 m*p 歌元素， 所以A(m, n, p) ? W (m, n, p) ? mnp对于 m=n=p 时，A(n)=W(n)=n3。这是例 1.10 的结论。 例 1.10 展示了有些算法只是执行指令，因此工作量不依赖于具体的输入细节；仅依赖 于输入的规模。这种情况下，最花和平均都是一样的。对于其他算法，就不一定了。 最坏和平均分析行为分析的概念是很有用的， 即使我们选择了一种很复杂的工作量的度 量（比如，执行时间） 。显然，工作量通常依赖于输入的规模和输入的特性，这使得不管选 择了什么度量的方式我们都要研究最坏和平均行为。1.4.4 空间使用一个程序使用的内存单元数量和执行程序所需要的时间一样， 依赖于具体的实现。 然而 ， 通过检查算法可以对空间的使用情况作出一些结论。一个程序需要存储空间来放置他的代 码、常量和程序使用的变量，以及输入的数据。还可能需要空间来操作数据，存储需要输出 的结果信息。输入数据本身可能也需要一些 form，通常也需要不少空间。 如果输入数据有一个自然的形式（比如，一个数组或矩阵） ，则我们撇开程序和输入， 分析还需要多少额外的空间。 如果额外空间的大小是一个于输入规模有关的常量， 则这样的 算法称为 in place。这个属于特指排序算法。 （in place 的一个不严格定义常用于，额外空间 不为为常数的但是仅和输入规模成对数关系， 原因是对数函数增长缓慢； 我们会在使用不严 格定义是特别指明。 ） 如果输入可以表示为变量的形式， 作为我们认为输入本身所需要的空间也是额外空间的 一部分。一般情况下，我们用“单元”的数量，而不对“单元”做严格的定义。你可以认为 单元足够大可以容纳一个数值或对象。 如果使用的空间依赖于特定的输入， 可以做最坏和平 均分析。- 33 -1.4.5 简明性通常，但不总是，最简洁最直接解决问题的方法不是最有效的。可是算法的简明性还是 一个需要的特性。这可以更简单的验证算法的正确性。当选择一个算法时，调试一个算法的 时间也是需要考虑的，但是程序经常被使用时，他的效率将是主要的选择依据。1.4.6 最优性不论我们多么聪明， 我们都不能将一类问题的算法性能提高的超过一个邻接点。 每一类 问题都有固有的复杂性， 就是说要解决问题需要做的工作量有一个最小值。 为了分析一个问 题的复杂性，与之对立的是我们前面讲到的分析算法的复杂性，我们选择一类算法（通常通 过算法允许执行的操作来决定）和一种复杂性的度量，例如基本操作执行的次数。之后我们 会问解决问题究竟要执行多少基本操作。 如果其中有一个算法执行基本操作的次数比别的算 法都少（最坏情况） ，我们说这个算法是最优的（最坏情况） 。注意当我们说这一类算法时， 并不意味着目前人们想到的这些算法。我们指所有可能的算法，包括海没有被发现的。 “最 优”不意味着“已知最好的”，他意味着“所有可能的最好的”。1.4.7 低限和问题复杂度 1.4.7然而我们怎么才能知道一个算法是最优的呢？我们是否必须分析所有可能的算法？ （包 括一些我们目前还没有想出来的？）幸运的是，不；我们可以从理论上证明要解决一个问题 执行基本操作数的低限。 然后任何算法执行的基本操作的数量都可以朝这个目标优化。 因此 ， 为了找到一个好的算法，或换个角度说为了解决一个问题： “解决一个问题必须做的工作有 多大？”， 我们必须要完成两个任务。 1. 设计一个看上去很有效率的算法 A。分析 A，找到在输入规模为 n 时，A 在最坏情况下 执行基本操作的数量的函数 WA(n)。 2. 找到一个函数 F，证明对于考虑的一类算法，在输入规模是 n 时，算法至少要执行 F(n) 步基本操作。 如果函数 WA(n)与 F(n)相等，则算法 A 是最优的(对于最坏情况)。如果不等，可能有更好的 算法或是有更好的低限。考虑，分析一个特定算法解决一个问题执行基本操作的上限数，以 及在条款 2 中讲到的给出解决问题基本操作数低限（最坏情况）的理论。在本书中，我们对 于那些最优算法已知的问题， 以及那些在所知的最低限和所知的最好算法之间仍有差距得问 题。下面是这两者简单的例子。 在最坏情况下算法低限的概念对于计算复杂性是十分重要的。 例 1.11 和 1.6 节研究的问 题以及第四章和第五章将帮助你理解低限的概念， 并展示一些建立低限的技术。 你必须紧记 “F 是一类算法的低限”的定义意味着属于这一类的所有算法，对于规模为 n 的所有输 入 ， 算法都至少执行 F(n)步基本操作。 例 1.11 查找数组中最大的元素 问题：在 n 个元素的数组中找到最大的元素。（假设类型为 float ； 当然也可以是其他类型。）- 34 -该类算法：算法可以比较合拷贝类型为 float 的数值，但是不能做其 他操作。 基本操作：比较数组的元素和其他 float 类型的数据。可以是存储在 其他数组中的或是存储变量中。 上限：假设数组 E 中存在要找到值。下面的算法找出最大值。 算法 1.3 查找最大值 输入：E，数组，索引号从 0,… n-1; n ? 1 ，n 是数组元素的数量。 输出：返回 max，E 中最大的元素。 int findMa(E, n) { max=E[0]; for( index=1; index&n; ++index) { if(max&E[index]) max=E[index]; } } 在 if(max&E[index])这一句比较数组的元素，他执行了 n-1 次。因此 n-1 是最坏情况下所作比较操作的上限值。有算法可以更少吗？ 低限：为了建立低限，我们假定数组中的元素都不相同。这个假设是 可行的，因为如果我们可以为这种输入（数组的元素都不同）在最坏情况 下建立低限，他也是考虑所有输入情况下最坏行为下的低限。 在 n 个元素都不同的数组中，n-1 个元素不是最大的。我们可以得出 结论，如果一个元素不是最大，当且仅当他必至少一个元素小。因而，n-1 个元素都必须在算法中通过比较来筛选掉。 每一次比较去掉一个元素， 所 以至少要做 n-1 次比较。也就是说，如果算法结束时还有两个或多个没有 被筛选掉的元素存在，就不能肯定他是不是最大。因此 F(n)=n-1 是要做 比较次数的低限。 结论：算法 1.3 是最优的，这是例 1.11 的结论。 在建立例 1.11 的低限中我们可能需要一些稍微不同的观点。 如果我们给出一个算法和 n 个元素的数组，于是算法终止并且在做少于 n-1 次比较之后给出了一个结果，则我们可以证 明对于某些形式的输入算法给出了错误的结果。如果不做多于 n-2 次的比较，就会有两个元- 35 -素永远不会被筛选掉； 也就是说无法知道其中一个是否比另一个小。 算法可以指定其中任意 一个为最大元素。我们可以简单的将另一个替换成一个比较大的数（如果必须）。既然所有 比较的结果都和前面的类似，算法给出和前面相同的结果，他将是错误的。（ 译者：此处没有搞明白，原文是“The algorithm can specify at most one of them as maximum. We can simply replace the other with a larger number(if necessary). Since the results of all comparisons done will be the same as before, the algorithm will give the same answer as before and it will wrong.”似乎说的是，将 n-2 替换成一个较小的数，会 得到和 n-1 一样的结论。）这个观点是逆否命题的一个证据（参见 1.3.3 节）。我们证明“如果 A 在任何情况下都 做少于 n-1 次比较，则 A 是不正确的。”通过逆否命题，我们可以得到结论“如果 A 是正 确的，则 A 在任何情况下都要至少要做 n-1 次比较。”他展示了一种对建立低限十分有效 的技术，即，如果算法不做足够的工作，就可以找到一种输入使算法得到错误的结果。 例 1.12 矩阵乘法 问题：令 A ? ( a ij ) ， B ? (bij ) 是两个 n×n 实数矩阵。计算矩阵 C ＝AB； 该类算法：算法可以执行实数的乘法，除法，加法和减法。 基本操作：乘法 上限：常用的算法（参见例 1.10）做 n 次乘法，因此至多需要 n 。3 3低限：有文献证明至少需要 n 次乘法。 结论： 没有办法根据这些信息确定常用的算法是不是最优的。 许多学 者在努力改善低限，证明至少需要 n 乘法，其他的正在寻找更好的算法。 到此为止，常用的算法 不是最优的；有算法可以达到近似 n2.376 22次乘法。这个算法是最优的吗？目前低限还没有进一步提高， 所以我们不知道是否 还有算法可以更低。 到现在为止， 我们都在讨论低限和最坏情况的行为。 平均行为如何呢？我们可以使用和 最坏行为一样的方法。选择一个看上去比较好的算法，位算法找到一个函数 A(n)，即在输 入规模为 n 时在平均行为下，算法要做 A(n)次基本操作。然后再证明这一类算法对于规模 n 的输入至少执行 G(n)次操作。如果 A=G，我们可以所算法的平均行为是最优的。如果不是， 继续找更好的算法或更好的低限（或者两者）。 对于许多问题分析执行操作的数量是很困难的。 通常， 如果一个算法执行操作的次数在 已知的最优执行次数范围之内（有时这个算法就是所知的最好的算法。），我们就认为这个 算法是最优的。在 1.5 节，我们将得出一种分析许多问题是否在已知的最优执行次数范围之 内，即使我们不能执行精确的分析。 我们可以使用与分析时间相同的方法来研究空间的使用。 分析一个特定算法使用空间数 量的上限， 在证明一个理论上的低限。 我们可以认为对一个问题的算法的时间和空间都是最 优的吗？这个问题的答案是，有时是。对于许多问题存在时间和空间的平衡。- 36 -1.4.8 实现和编程实现就是将一个算法转换成计算机程序。 算法可以通过与计算机程序设计语言类似的操 作变量和数据结构的构造来描述， 或者用非常抽象的、 高级的用自然语言解释解决抽象问题 的方法，不提到关于计算机的任何事物。因此实现可能是灵巧、直接的翻译工作，也可能是 非常困难的，需要程序员在选择数据结构上做很多判断。以后在适当的地方，我们将讨论在 一般情况下，实现如何选择数据结构，如何将以英语描述的算法变成程序。进行这样的的讨 论有两个原因。第一，这是生产一个好程序很自然而且重要的部分。第二，考虑实现细节对 于分析算法很必要的；在抽象对象（比如图，集合）上执行不同操作的时间依赖于对象是如 何表示的。例如，如果集合以链表表示，则连接两个集合只需要一次或两次操作。但是如果 集合以数组表示，则需要大量的操作――将一个集合的元素拷贝到另一个集合中。 狭义上讲， 实现或简单的编程， 意味着将一个算法描述细节和算法使用的数据结构转换 成一种特定计算机的程序。此时我们的分析是实现无关的（implementation-independent）； 换 句话说他们将独立与计算机和使用的程序设计语言，独立于算法或程序的小细节。 程序员也可以在分析算法时考虑特定计算机的信息。例如，如果不止统计一个操作，操 作可以根据执行时间建立权值； 或者估计一个程序到底要执行多少秒 （在最坏情况和平均情 况下） 。有时使用一些具体计算机的知识将得到一个新的分析结果。例如，如果计算机有一 些不寻常的、强力的可以被高效执行的指令，则可以研究使用这些指令的一类算法，将这些 指令作为操作统计。如果计算机只有一套很有限的指令集，使得实现基本操作很低效，则要 考虑不同的一类算法。然而一般的，如果实现无关的分析做的很好。则程序依赖分析将作为 一种补充。 当然考虑一种特定的实现时，也可以对算法的空间使用情况做细节分析。 任何关于问题输入的知识，都可以提高算法分析的精度。例如，如果输入仅限于所有可 能输入的一个子集，就可以只对这个子集作最坏分析。就像我们注意到的，一个好的平均行 为分析依赖于对不同输入发生概率的认识程度。1.5简单函数的渐进增长率我们的度量算法工作量的方法到底如何？我们对两个算法的比较有多精确？因为我们 不能计算算法每一个步骤的执行情况，所以我们的分析必然存在不精确的因素。 假设一个问题的算法作了 2n 次基本操作，因而大概共有 2cn 次，c 是某个常量， ，另一 个算法做 4.5n 次基本操作，或者共有 4.5c`n.。那个运行的更快？我们确实不知道。第一个 算法可能做了许多额外的工作； 就是说他的比例系数可能很高。 因而如果一个函数描述的两 个算法有不同的常量因子，他可能是区别两个算法无意义的尝试（除非我们提高分析的精 度） 。我们考虑在同一复杂性类中的算法。 假设一个问题的算法做 n32次乘法而另一个算法做 5n 。那一个算法更快呢？对于 n2比较小的情况，第一个较快，但是对于 n 很大的情况，第二个更快――即使他做更多开销的 操作。立方函数的增长率远大于平方函数，常数因子在 n 变的很大时影响不大。 就像在例子中暗示的， 我们希望找到一种比较简单函数的方法， 能忽略常数因子和小规 模输入的。这正是我们将要研究的渐进增长率、渐进阶、或简单的称为函数的阶。 他能合理的忽略常数因子和小