计数一个有限集合与分析一个算法,都要求如实地处理“重复”。同一个委员会可以因成员排列顺序不同而被重复数多次;一个递归程序可以通过不同的调用多次求解同一个数学子问题。除以对称因子与共享重复子问题是两种不同的修正方式,但二者都始于准确识别:计算把什么视为不同的对象。
动机
设有八名学生可供担任三个职位。若职位是主席、秘书和司库,则选出三名不同学生并分配职位是有序选择。若只是组成一个三人委员会,则对成员重新排列并不产生新的委员会。两个问题涉及同样的人和同一个数字三,答案不同是因为所数的对象不同。
算法中的计数问题同样应当说明其对象是函数、子集、字符串还是执行过程。若一个哈希函数把十一个键映射到四个桶中,则碰撞不可避免。这并不意味着每个桶的大小相同,也不意味着某一对特定的键发生碰撞,更不意味着该哈希函数实现得不好。计数界所证明的,仅是其量词所陈述的内容。
递推式则带来另一种重复计算或遗漏计算的机会。归并排序做两次规模为原来一半的递归调用;二分查找只继续进入其中一半。两者的深度相近,但每层的工作量不同。画出递归树并对各层求和,可以使这一区别一目了然,并解释对数深度何时产生对数、线性或更大的总代价。
定义
定义 1.3.1
(函数及其类型)
函数 为其定义域 中的每个元素 恰好指派陪域 中的一个元素 。若相等的输出蕴含相等的输入,则称其为单射;若陪域中每个元素都作为某个输出出现,则称其为满射;两者同时成立则称为双射。像 可以比指定的陪域小。保持同一指派而改变陪域,可能改变该函数是否为满射。
定义 1.3.2
(阶乘与二项式系数)
对非负整数 ,定义 ,且 。对整数 ,以 表示 元集合的 元子集的个数。由 个互不相同的元素构成的有序列表记住了第一项、第二项及其后各项; 元子集则只记住成员关系。有放回抽样允许元素重复,因此其列表又是另一类对象。当 时,这个计数为零,我们定义 ;下文的阶乘公式仅用于 。
定义 1.3.3
(渐近记号)
对于正整数上最终非负的函数, 表示存在常数 和 ,使得对一切 都有 。当 时记 ;当两个界同时成立时记 。这些常数不依赖于 。这些是最终意义下的比较,因此有限多个较小的输入可以另行处理。对这类界而言,底数为不同固定常数(大于一)的对数之间只相差一个常数倍。
定义 1.3.4
(递推式与递归树)
递推式通过较小的自变量并配合初值来确定一个函数。对于代价递推式,每一项都必须对应算法的某个具体部分:递归调用、合并工作或初始化。递归树是一种记账工具,其结点是调用的出现。若程序不使用记忆化而做了两次调用,则即使两个结点的输入值相等,它们也代表两次执行。
定理/命题
定理 1.3.5
(有序分配与子集)
若 且 ,其中 ,则从 到 的单射个数为 ,并且
从空集到任一固定集合恰有一个函数。对 ,从 元集合到 元集合的全部函数共有 个;若 ,则该计数为零。
定理 1.3.6
(鸽巢原理给出最大纤维的下界)
若把 个对象分配到 个盒子中,则至少有一个盒子至少收到 个对象。特别地,从一个有限集合到一个元素更少的集合,不可能存在单射。
定理 1.3.7
(由各层求和得到的平衡递推式)
设 ,其中 ,并设 ,且对更大的此类输入有 ,其中常数 ,,。则当 2 的幂增大时,
这些结论只针对所述的平衡递推式。子问题规模不相等,或含有非多项式的额外工作时,需要重新分析。
证明思路
证明
(计算单射与子集)
要数单射的个数,先把定义域的元素按固定顺序排列。第一个元素有 种可能的像,下一个有 种,第 个有 种,因为单射性禁止使用之前已用过的像。它们的乘积为 。当 时乘积为空,等于一,反映了唯一的空指派。若允许重复,则每个定义域元素都有 种选择,对 得到 。
每个由 个互不相同元素构成的有序列表,在忽略顺序后决定一个 元子集。每个这样的子集恰有 种排列,因此这一“忘记顺序”映射的所有纤维大小均为 。按其底层子集对有序列表分类,再除以这个共同的纤维大小,即证明了二项式公式。纤维大小相等正是除法的依据;当不同对象有不同数量的描述时,一般不能随意用某个方便的数去除一个计数。
证明
(鸽巢界)
对于鸽巢界,令 。若每个盒子至多含 个对象,则总数至多为 ,这由定义性质 得出,与对象总数矛盾。 的情形无妨:每个盒子都含零个,符合所声称的下界零。当 时,该界给出某个盒子中至少有两个对象,与单射性矛盾。
证明
(按层对平衡递推式求和)
对于递推式,树的高度为 。在第 层有 个结点,每个的规模为 ,因此它们的非递归工作总量为 。共有 个叶子,每个的代价为 。当 为整数时,这确实是一棵调用树;当 不是整数时,同样的展开是一个代数恒等式。无论哪种解释,都有
令 。若 ,则对 ,几何和介于一与 之间。叶子项 ,因此总量为 。若 ,则和为 ,叶子项为 ;由于 ,当 增大时总量为 。
若 ,则和 对大的 为 。乘以 得 。叶子项具有同样的量级,证明完毕。请注意,叶子的代价参与了最终结果,而不是在分析中消失。
证明透视
深度并未计入所有调用
对数高度说明的是:沿单独一条从根到叶的链,一个输入可以被减半多少次。把一个结点的工作量乘以高度,只有在同时计入所有其他结点时才有效。层因子 提供了所缺少的重数。在平衡递推式中,几何比告诉我们工作量是集中在根附近、按层均匀分布,还是集中在叶子附近。
帕斯卡(Pascal)恒等式给出第二种子集计数:对 ,有 。固定一个元素。不含它的子集由第一项计数;含有它的子集在删去它之后,对应于其余集合的 元子集。两种情形不相交且穷尽。边界计数 随后支撑起一张动态规划表。不使用表的直接递归会反复计算相同的参数对;递推式正确与实现高效是两项不同的成就。
例题详解
例题 1.3.8
(三个职位还是一个委员会)
从八名学生中选出三名不同的学生分别担任主席、秘书和司库,共有 种可能。组成一个三人委员会则有 种,因为每个委员会有六种排列。若允许同一名学生担任多个职位,则职位分配共有 种。这些答案没有哪一个本质上更正确:它们数的是不同的指定对象。
例题 1.3.9
(强制碰撞究竟保证了什么)
十一个互不相同的键被映射到四个桶中。鸽巢界保证存在一个桶至少含 个键。负载 表明不可能有更大的普遍下界。该定理并不能事先指出是哪个桶,也不能指出哪一对键发生碰撞。它同样不蕴含每个桶至少有两个键:负载 也满足分配规则。
例题 1.3.10
(更大的分支因子改变代价)
对于二的幂上的 ,,第 层的代价为 ,并且有 个叶子。求和得 。当 时,中间代价为 ,,。树的高度为三,但其总工作量并非 。这里 ,该定理正确地给出 。
作为比较,一次规模减半、工作量为常数的递归调用有 ,因此代价是对数的。两次规模减半的调用并伴随线性的合并工作,有 ,因此代价为 ,如归并排序。四次规模减半的调用并伴随线性的合并工作,则给出上面的二次例子。只有在确认实际算法确实做了所述调用并产生所述局部代价之后,这些比较才有意义。
并非每个递推式都是平衡的。对于固定常数 与 ,设 和 ,展开得 。把减半型定理套用到这个递推式上,会悄悄改变算法本身。这种线性深度的模式描述的是,例如,一个递归划分过程反复只留下一个比之前小一的子问题,且每次调用的工作量为线性。平均情形的平衡直觉不能取代最坏情形的递推式。
从循环执行次数到增长界
给出成本界之前,要先说明输入规模和所计数的操作。设数组长为 ,下标从零开始。一个过程检查每对位置:对 ,依次取 ,比较两个位置上的元素。当 时,内层范围为空。令 只计元素比较次数; 时没有比较。
固定 后, 有 个取值。因此
最后的等式可这样证明:把这个和分别按升序和降序写出,逐项相加。每一对的和都是 ,共有 对,所以原和的两倍为 。 和 时比较次数均为零,公式仍成立。这个过程恰好把每一对不同位置计算一次:较小下标是 ,较大下标是 。两个位置的值相等,也不表示这两个位置相同。
对每个整数 ,有 ,所以
这些固定常数同时给出上界和下界,证明 。若每次访问的循环控制操作耗时为常数,初始化也需常数时间,那么附加的 工作不改变总运行时间的 增长。这里假定访问和比较元素均耗常数时间;例如元素是长字符串时,一次比较本身可能依赖字符串长度。
证明透视
嵌套循环需要求和,不能只猜次数
两层循环并不自动意味着内层循环体执行 次。这里内层长度依次是 ,并非每次都是 。精确求和同时提供上、下界。如果每个外层下标只对应一次内层迭代,次数就会是线性的。
例题 1.3.11
(搜索提前停止会带来什么变化?)
顺序搜索从左到右将目标与数组元素比较,找到第一个匹配就停止;如果没有匹配,则比较到末尾。长度为 的输入中,若第一个匹配在从一开始计数的位置 ,元素比较次数为 ;若目标不存在,次数为 。当 时,在所有数组和目标中,最好情况是一开始就匹配,次数为一;最坏情况是目标不存在,次数为 。因此最好情况的比较次数为 ,最坏情况为 。空数组的两种次数都是零。
最坏情况函数的上界也约束同规模的每一个具体输入;一个有利输入的成本却不能约束所有其他输入。讨论平均情况还必须指定输入的概率分布,最好和最坏情况都不能替代这个条件。
快速检查
(另一个过程取 ,对每个 再取 ,每次访问一次。共访问多少次,增长阶是什么?)
解答 · 答案
内层循环体执行 次,总数为 ; 时为零。当 时,它介于 和 之间,故为 。两段循环枚举的位置对并不相同:把第一段中每个严格非对角位置对的坐标交换,恰好得到第二段的严格非对角位置对。第二段还对每个 包含一个对角位置对,因此计数多 。
常见错误
常见错误
(定义域与陪域属于函数的一部分)
定义域和陪域是函数规格的一部分。从实数到实数的指派 不是满射,但同一指派到非负实数则是满射。它仍然不是单射,因为一与负一有相同的像。这些陈述并不矛盾,因为单射性与满射性问的是不同的问题。
常见错误
(把“选三个”读成与顺序无关)
不要把“选三个”这一说法当作顺序无关的证据。是否让被选对象担任不同的角色,取决于前后的任务。同样,重复可能被单射性禁止,也可能被输入模型允许;只有在明确这些选择之后,公式才有用。
反例模式
并非所有对称性都产生相同数量的描述
有序列表 、 和 描述的是同一个多重集,共有三种排列,而 有六种。因此,把所有长度为三的列表都除以 ,并不能正确地数出多重集的个数。子集公式之所以成立,是因为其元素互异的假设使每条纤维大小相同。
常见错误
(上界不等于精确的增长阶)
上界并不表示代价恰好是二次的,甚至不表示二次增长是必要的。线性函数同样是 。要得到 结论,需要匹配的下界,并且要说明分析针对的是最坏情形、平均情形还是某个受限的输入族。
总结
计数始于对象:任意函数、单射和子集有不同的重数。均匀的纤维大小为对有序计数做除法提供依据;当分配拥挤时,鸽巢原理给出最大纤维的界。递推式分析同样是数出所有调用的出现并对它们的工作求和。明确的初值、分支因子和代价模型,可以避免一个看似正确的公式描述了错误的问题。
练习
快速检查
(从一个四元集合到一个三元集合有多少个函数?其中有多少个是单射?请在不使用负阶乘的情况下解释这两个答案。)
解答 · 答案
四个输入中的每一个都有三种独立的指派选择,因此共有 个函数。单射不存在:四个互不相同的输入不可能在三个输出值上不发生碰撞。取 的单射公式不适用于 ;此时由鸽巢论证直接处理。
快速检查
(证明:在固定的带标号 个顶点的集合上,简单无向图的个数为 。)
解答 · 答案
简单无向边是由两个不同顶点构成的无序对,这样的对共有 个。每一对要么出现,要么不出现,且与其他对的选择相互独立。这在带标号的简单图与可能边集的子集之间建立了双射,从而得到所述的二的幂。假设已排除环和有向边。
快速检查
(计算 ,并就这一具体计数解释帕斯卡恒等式。)
解答 · 答案
该计数为 。固定十个元素中的一个。不含它的四元子集有 个,含有它的有 个。它们的不交并给出 。
快速检查
( 是否属于 ?是否属于 ?请由最终不等式论证这两个结论。)
解答 · 答案
对正整数 ,有 ,故 ,于是得到第一个上界。对于第二个, 无界:对于任何拟取的常数 ,整数 都违反 。因此不存在最终成立的线性上界。
练习 1.3.12
(分析 2 的幂上的 ,。给出精确表达式以及渐近界。)
核心
解答(3)
- 1
按层对工作量求和
在第 层有 个规模为 的结点,所以该层的代价为 。
- 2
加上各层与叶子
取 ,并有 片代价为一的叶子,则 ,与 相符。
- 3
读出增长阶
因此 ;根层的二次工作量已经给出下界。