上一节我们介绍了随机字符串和模式匹配的期望时间。本节中我们来看看一个具体的计算问题。问题如果你希望一个随机比特串中出现32个连续零的概率达到50%那么这个串应该有多长请根据本讲内容计算这个数字。以下是解题思路这是一个典型的“等待时间”问题可以使用本讲中分析模式首次出现时间的方法。核心是计算在随机比特流中首次出现连续32个零所需的期望比特数。你可以构建一个状态机或使用递推关系来求解。随机打字机与目标短语接下来我们探讨一个更有趣的问题它涉及更复杂的模式。问题假设一只猴子在一台有32个字符的键盘上随机打字。在它打出完整短语“the quick brown fox jumps over the lazy dog”之前期望需要打出的字符数是多少以下是需要考虑的要点此问题与上一个问题类似但目标模式更长且字符集更大。模式内部可能存在重复的子串例如“the”出现了两次这会影响分析。你可以尝试将短语视为一个整体模式计算其首次出现的期望时间。领导者选举算法分析验证最后我们通过一个简化的递推式来回顾领导者选举算法的分析。问题请逐步推导领导者选举算法中轮数的简化递推关系并观察其主导项的形式。以下是分析步骤回顾算法确定决定总轮数的关键参数和事件。建立描述剩余候选者数量变化的递推关系。求解递推式并识别决定算法渐近行为的主导项。实验与验证理论需要实践的检验。以下是两个你可以进行的实验以验证本讲中的数学结论。实验一随机Trie树形状绘制一些随机Trie树。例如生成10个包含100个节点的随机Trie树并将它们的形状与随机二叉搜索树或随机卡特兰树进行比较。实验二随机Trie树性能对随机Trie树运行实验尝试验证其运行时间的分析结果。目标是得到与教材中类似的图表以证明运行时间确实非常接近n log n。总结与进一步学习https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/9a534b310f48831ed84bf306e8d3cce3_2.pnghttps://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/9a534b310f48831ed84bf306e8d3cce3_3.png本节课中我们一起学习了如何将概率分析应用于几个经典问题计算特定模式出现的期望等待时间以及验证复杂算法的递推分析。为了深化理解建议你完成教材第8章的习题并动手进行上述实验。通过解决这些具体问题你将能更好地掌握字符串处理算法尤其是Trie树背后的数学原理。037词与映射https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/baa51a642bf311de4f2d53b067244d5c_0.png在本节课中我们将学习组合数学中的“词”与“映射”概念。这是结束我们课程学习的合适主题因为它将我们之前讨论过的许多内容联系在一起。我们将主要处理标记对象因此会用到指数生成函数。虽然课程中无法涵盖书本中的所有例子但我们会探讨解析组合学中的一些技术及其在算法分析中的应用。什么是“词”首先我们来明确组合数学意义上“词”的含义。为此我们先回顾几个相关的组合对象。例如我们讨论过包含N位的二进制字符串的数量。字符串是0和1的序列。使用符号方法和普通生成函数我们证明其数量为2^N。这可以推广到从包含M个字符的字母表中抽取的字符串数量。在这种情况下它是M个字符之一的序列其生成函数为1 / (1 - Mz)因此数量为M^n。那么这与“词”有何关系我们稍后会讲到。现在让我们看看标记对象。大小为n的标记集合有多少个实际上对于任意大小n只有一个标记集合。我们不考虑顺序的重要性所以只有一个集合并且我们标记所有对象。如果我们想取n个对象的标记集合的有序对会得到什么对于两个对象你可以有{1}然后{2}或者{2}然后{1}或者空集和两个对象或者两个对象和空集。在这种情况下集合的顺序是重要的标记对象可以以这些不同的方式落入集合中。因此对于n个对象有8种不同的有序对标记集合。答案就是2^n这与二进制字符串的数量相同我们稍后会看到这种关系是如何建立的。如果不是对而是M个集合的序列呢长度为M的、包含n个对象的标记集合序列有多少个我们用“瓮”这个词来指代一个可以容纳标记对象的容器。从这个角度看经典的理解方式是“球与瓮”问题。我们实际上讨论的是将n个球投入M个瓮的不同方式数量。从符号方法到计数上一节我们回顾了基本概念本节我们来看看如何通过符号方法得到这些计数结果。这只是对第5讲内容的复习。对于标记对象的组合类我们可以执行一些基本操作不相交副本、取有序对、以所有可能方式重新标记。然后指数生成函数上的相应操作使我们能够从构造直接得到生成函数。对于标记对象我们将其扩展到长度为K的序列或任意长度的序列生成函数上给出相应的变换。对于集合我们除以K!。因此从一个类中取对象集合的生成函数是e^(该类的生成函数)。还有循环等。这些是我们用于标记对象的基本操作现在我们将用它们来研究球与瓮问题或“词”的问题。组合定义与生成函数在组合数学中我们将一个“词”定义为包含n个对象的M个瓮的序列。它是将n个球投入M个瓮的配置方式数量。我们使用生成函数它由M参数化即序列中瓮的数量。生成函数是所有可能对象即球的配置方式的Z^(对象大小) / (对象大小)!之和。通常这汇总起来就得到了将n个球投入M个瓮的方式数量。例如这是9个球投入5个瓮的一种可能结果。它对应于九个事物的五个子集的序列。我们也可以直接写出子集。这些都是表示同一组合对象的不同方式。但从符号方法来看要找出这个生成函数或有多少种不同的方式很简单它是一个长度为M的对象集合序列仅此而已。这意味着生成函数方程立即是(e^Z)^M或e^(MZ)。因此不同配置的数量是n!乘以Z^n的系数即M^n。这个M^n与从包含M个字符的字母表中抽取的、长度为n的字符串数量相同。实际上词和字符串之间存在一一对应关系。字符串是我们上次讨论的、从M字符字母表中抽取的n个字符的序列。对于字符串中的每个字符有M种可能性因此有M^n个不同的字符串。词是包含n个对象的标记集合的序列也有M^n个词。那么对应关系是什么很简单我们看第二个集合例如它对应于字符串中第二个字符出现的位置。就这么简单。没有三所以第三个集合是空的。一在位置7所以第一个集合包含7。五在位置5、6和9。四在位置2和4。这只是一个一一对应关系词告诉我们字符在字符串中出现的位置。在词中如果你看第K个集合对于词中的每个i字符串中的第i个字符是K。反之如果你看字符串如果字符串中的第i个字符是K那么你将i放入词中的第K个集合。所以词只是字母在字符串中出现位置的索引。这就是对应关系。这非常熟悉我们之前处理过字符串现在我们将处理词并且有这种一一对应关系。这只是另一种看待方式。对于二进制字符串将八个二进制字符串视为词第一个表示所有三个字符都是零没有一最后一个表示没有零所有三个字符都是一依此类推。区别是什么没有区别只是观点不同。上一讲我们看字符串时关心的是字符序列以及序列中相邻字符之间的关系寻找字符串中的模式等。这次我们感兴趣的是索引集合很重要的应用例如有多少个零、多少个一等。但本质上它们是同一个对象。对于字符串我们使用普通生成函数来枚举。对于词我们将使用指数生成函数。这是观点和分析变体所用技术的差异。总结本节课中我们一起学习了组合数学中的“词”概念。我们回顾了字符串作为未标记对象使用普通生成函数枚举典型字符串是字符序列生成函数为1/(1-Mz)数量为M^n。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/baa51a642bf311de4f2d53b067244d5c_2.png对于词我们将其视为标记对象并使用指数生成函数。我们看到了不同的表示方式当进行序列操作时我们进行星积并以所有可能方式重新标记。不同词的数量是e^(MZ)但我们得到了相同的结果。在本讲中我们将主要关注球与瓮的表示方式。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/baa51a642bf311de4f2d53b067244d5c_4.png这是一个关于组合数学中“词”的简要介绍。038生日问题 https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/873b25ab7274a1eb57a76e0465e59741_0.png在本节课中我们将学习一个经典的组合问题——生日问题。我们将使用解析组合学的方法来分析它并计算出在随机情况下平均需要询问多少人才能找到两个生日相同的人。生日问题概述生日问题是一个著名的概率论问题。假设有一群人我们逐一询问每个人的生日。问题是平均需要询问多少人才能找到两个生日相同的人直觉上可能需要很多人但通过数学分析我们会发现这个数字比想象中小得多。建模为“球与瓮”问题我们可以将这个问题建模为一个“球与瓮”模型。假设有M个瓮对应一年中的365天每个“球”对应一个人被随机放入一个瓮中对应其生日。问题是平均需要放入多少个球才能出现某个瓮中有两个球的情况使用符号方法分析为了分析这个问题我们首先需要定义“生日序列”。生日序列的定义一个生日序列是一个长度为n的单词或序列其中每个字符对应一个瓮最多出现一次。换句话说在序列中没有重复的字符。生日序列的构造构造生日序列很简单我们有M个瓮每个瓮要么是空的要么恰好有一个球。因此整个序列就是这M种状态的一个排列。使用符号方法这直接转化为指数生成函数EGF。每个瓮的状态空或有球的EGF是(1 z)。由于有M个独立的瓮整个生日序列类的EGF就是每个瓮EGF的乘积。因此生日序列的指数生成函数公式为B(z) (1 z)^M计数序列从生成函数中我们可以提取系数来计数长度为n的生日序列数量。z^n项的系数乘以n!即为我们所需的数量。具体计算如下(1z)^M中z^n项的系数是C(M, n)即组合数M choose n。因此长度为n的生日序列数量是n! * C(M, n)。这可以简化为M! / (M-n)!或者等价地M * (M-1) * ... * (M-n1)。公式长度为n且无重复字符的序列数量为P(M, n) M! / (M-n)!解决生日问题有了无重复序列的计数我们就可以解决原始的生日问题了。无重复的概率在随机情况下所有可能的M^n个长度为n的序列是等概率的。因此前n个人生日各不相同的概率等于无重复序列的数量除以总序列数。公式前n次询问无重复生日的概率为P(无重复) [M! / (M-n)!] / M^n另一种理解是这个概率也等于“第一次出现重复生日的询问位置T大于n”的概率即P(T n)。计算首次重复的期望位置我们关心的是首次出现重复的期望询问次数E[T]。根据期望值的定义它可以表示为所有P(T n)的和n从0到M-1因为最晚在第M次一定会出现重复。公式首次重复位置的期望值为E[T] Σ_{n0}^{M-1} P(T n) Σ_{n0}^{M-1} [M! / ((M-n)! * M^n)]这个求和式与我们在课程中讨论过的 Ramanujan Q 函数有关。通过渐近分析或使用积分近似可以得到一个简洁的结果。核心结果公式当M较大时首次重复的期望位置近似为E[T] ≈ √(πM / 2)应用到实际生日问题现在我们将这个结果应用到最初的生日问题上。一年有M 365天。计算过程如下E[T] ≈ √(π * 365 / 2) ≈ √(573.25) ≈ 23.94因此平均只需要询问大约 24 个人就能找到两个生日相同的人。这个数字远小于通常的直觉183 或 365。总结https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/873b25ab7274a1eb57a76e0465e59741_2.png本节课中我们一起学习了生日问题及其解析组合学解法。问题建模我们将寻找相同生日的问题转化为“球与瓮”模型中寻找首次碰撞的问题。符号方法我们定义了“生日序列”并利用符号方法推导出其指数生成函数B(z) (1z)^M。概率计算我们计算了前n次询问无重复生日的概率P(T n) M! / ((M-n)! * M^n)。期望值通过对所有无重复概率求和并利用渐近分析我们得到了首次出现重复的期望位置公式E[T] ≈ √(πM / 2)。实际应用代入M365我们得出平均只需询问约24 人就能找到生日相同的两人。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/873b25ab7274a1eb57a76e0465e59741_4.png这个结果展示了概率的反直觉性以及解析组合学在解决此类问题上的强大能力。039赠券收集问题 https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/50fe9ef5e8215585048f0f792dd94564_0.png在本节课中我们将学习一个经典的概率与组合问题——赠券收集问题。我们将探讨其定义、经典概率分析以及如何使用解析组合学的方法来研究它。问题定义 赠券收集问题描述了一个常见场景假设有M种不同的赠券或卡片、生日等每次随机获得一种。问题是平均需要收集多少次才能集齐所有M种不同的赠券这类似于向M个瓮中随机投球需要投多少次才能确保每个瓮中至少有一个球。或者掷一个M面的骰子需要掷多少次才能看到所有M个面。经典概率分析 上一节我们定义了问题本节中我们来看看如何使用经典概率论计算平均收集次数。首先假设我们已经收集了k种不同的赠券。获得第k1种新赠券的概率是(M - k) / M。因此为了获得下一种新赠券所需的尝试次数服从参数为p (M - k) / M的几何分布。其期望值为1/p M / (M - k)。以下是计算总期望次数的步骤从k 0尚未收集任何赠券开始。获得第k1种新赠券的期望尝试次数是M / (M - k)。要集齐所有M种赠券需要将获得第1种、第2种…直到第M种新赠券的期望次数相加。因此总期望次数E[T]为E[T] Σ (k0 到 M-1) [ M / (M - k) ] M * Σ (j1 到 M) [ 1 / j ] M * H_M其中H_M是第M个调和数。当M较大时H_M近似于ln M γγ 为欧拉常数。所以平均收集次数渐近于M ln M。例如对于一个20面的骰子M20平均需要掷20 * ln(20) ≈ 60次才能看到所有面。解析组合学方法 虽然经典方法能轻松得出平均值但如果我们想研究分布、方差或更复杂的变化形式就需要解析组合学提供的结构。我们首先定义“赠券收集序列”它是一个长度为n的序列使用了字母表中所有M个字母且每个字母至少出现一次。指数生成函数 (EGF) 构建我们可以将赠券收集序列视为一个由M个“非空集合”构成的序列每个集合对应一个字母的出现位置。在标记组合结构中这对应于C SEQ_M( SET_{≥1}(Z) )其指数生成函数为C(z) (e^z - 1)^M系数[z^n] C(z)给出了长度为n的赠券收集序列的数量再除以M^n即可得到随机序列是赠券收集序列的概率。然而直接提取系数会得到一个交替和对于渐近分析并不方便。普通生成函数 (OGF) 与等待时间另一种更有效的方法是定义一个新类W_{M,k}它是使用恰好k种不同字母的M字并且最后一个字母只出现一次。这有助于分析收集到第k种赠券的等待时间。以下是其组合构造最后一个字母是已出现的k种字母之一。或者最后一个字母是一种全新的字母第k1种。这个构造直接转化为生成函数方程。通过计算相应的概率生成函数对其求导并在z1处求值我们可以得到收集到第k种赠券的平均等待时间最终也能推导出相同的总和公式M * H_M。应用与扩展 赠券收集问题在现实世界和计算机科学中有许多应用。实际应用示例收集卡片估算集齐一套M张不同卡片需要购买的卡包数量。软件测试随机访问内存页面进行测试。若要确保测试覆盖所有M个页面平均需要约M ln M次随机访问。例如对于M1,000,000大约需要1,000,000 * ln(1,000,000) ≈ 14.5M步。组合学扩展我们讨论的“赠券收集序列”在组合学中称为M-满射 (M-surjection)即使用了所有M个字母的序列。一个更一般的概念是满射 (surjection)它指使用了某个字母表不一定是全部但无遗漏的序列即使用的字母集合是连续的{1, 2, ..., k}对于某个k。其组合构造为S SEQ( SET_{≥1}(Z) )对应的指数生成函数为S(z) 1 / (1 - (e^z - 1)) 1 / (2 - e^z)分析这个生成函数可以得到长度为n的满射数量的渐近估计约为n! / (2 * (ln 2)^{n1})。这展示了解析组合学在处理此类复杂结构时的威力。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/50fe9ef5e8215585048f0f792dd94564_2.png总结 本节课中我们一起学习了赠券收集问题。问题核心随机收集M种不同物品集齐所有种类所需的平均次数约为M ln M。两种方法我们回顾了简洁的经典概率推导也介绍了更具一般性的解析组合学方法后者为分析更复杂的性质如方差、分布奠定了基础。广泛应用从趣味游戏到计算机系统测试该问题模型都有着重要的实用价值。组合扩展我们看到了如何将其自然扩展为“满射”这一组合对象并通过生成函数进行研究。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/50fe9ef5e8215585048f0f792dd94564_4.png下一节我们将继续探讨解析组合学在计算机科学中的其他应用。040哈希表 ️https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/8a42d604ec36f45949ac823605546965_0.png在本节课中我们将学习哈希表的基本原理及其背后的概率模型分析。哈希表是计算机科学中一种高效的数据结构其性能分析紧密关联于我们之前讨论过的“球与瓮”模型。我们将探讨两种主要的哈希冲突解决策略分离链接法和线性探测法并分析它们的性能。上一节我们介绍了“球与瓮”模型及其在组合数学中的经典应用。本节中我们来看看如何将这个模型应用于哈希表的分析。哈希表的核心思想是使用一个哈希函数将键映射到一个固定范围内的索引值例如0到M-1。这类似于将N个球键随机地放入M个瓮哈希表的槽位中。我们假设哈希函数满足均匀哈希假设即每个键被独立、均匀地映射到M个槽位中的任何一个。以下是两种主要的冲突解决策略分离链接法在分离链接法中每个哈希表的槽位瓮都维护一个链表。所有哈希到同一位置的键球都被放入对应的链表中。以下是该方法的实现示意图哈希表索引: 0 - [键A, 键B] 哈希表索引: 1 - [键C] 哈希表索引: 2 - [空] ... 哈希表索引: M-1 - [键Z]搜索一个键时我们需要遍历其所在槽位的链表。因此我们关心链表的平均长度以及链表长度过长的概率。平均链表长度显然是N/M记作α。更关键的是我们需要知道链表长度远超平均值的概率。这可以通过经典的占位分布来分析。对于一个给定的槽位其包含k个键的概率服从二项分布P(槽位有k个球) C(N, k) * (1/M)^k * (1 - 1/M)^(N-k)当N/M α固定且k较小时这个分布可以用泊松分布很好地近似P(槽位有k个球) ≈ e^(-α) * (α^k) / k!利用这个近似和斯特林公式进行推导可以证明当α取一个适中的值例如10时链表长度超过5α的概率是极其微小的例如10^-15量级。这为程序员提供了性能保证。线性探测法在线性探测法中哈希表是一个简单的数组每个槽位只能存放一个键。当发生冲突即两个键哈希到同一位置时算法会顺序地向后或向前扫描直到找到一个空槽位。以下是该方法的操作示例插入键X哈希到位置2: [空, 空, X, 空, ...] 插入键Y也哈希到位置2: 位置2已满扫描到位置3 - [空, 空, X, Y, ...]分析线性探测法的平均搜索成本更为复杂。唐纳德·克努特在约50年前首次给出了精确解。他证明在均匀哈希假设下成功查找一个键所需的平均探测次数为平均探测次数 Σ (k0) [ (N/M) * ((N-1)/M) * ... * ((M - k 1)/M) ]这个结果是一个里程碑。它表明如果保持哈希表的负载因子α N/M不超过1/2那么平均探测次数将大约为2次这是一个非常实用的结果。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/8a42d604ec36f45949ac823605546965_2.png关于线性探测还有一个有趣的故事。尽管其平均性能的公式看似简洁类似于生日问题或赠券收集问题但使用我们课程中介绍的符号方法等现代分析工具来重新推导它却曾是一个长期挑战。这个问题最终引向了与随机图、赌徒破产问题等领域的深刻联系并由一种称为“艾里定律”的分布所描述。这说明了算法分析领域的深度与魅力。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/8a42d604ec36f45949ac823605546965_4.png本节课中我们一起学习了哈希表的两种基本实现分离链接法和线性探测法。我们看到了“球与瓮”这一经典概率模型如何为分析哈希表性能提供强大的工具。对于分离链接法我们利用占位分布和泊松近似分析了其最坏情况概率对于线性探测法我们介绍了克努特给出的经典平均性能分析结果。这些分析为设计高效、可靠的哈希表提供了理论基础。041映射https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/81a83ffa2651c76624f786f2e9fff7f9_0.png概述在本节课中我们将要学习一种称为“映射”的组合结构。映射与许多我们已研究过的内容相关并且是解析组合学中的一个典型范例。我们将从简单的凯莱树开始逐步深入到更复杂的结构如映射中的连通分量并探讨其在实际应用中的意义。凯莱树 上一节我们介绍了映射的基本概念本节中我们来看看一个更简单的相关结构凯莱树。凯莱树是一种带标签、有根、无序的树。带标签意味着所有节点都有标签有根意味着有一个特定的根节点无序意味着我们不关心根节点子节点的顺序。对于三个节点的凯莱树共有九种不同的结构。例如节点标签为1, 2, 3的树其根节点可以是其中任何一个但根节点子树的顺序不重要。凯莱树的数量公式是一个经典结果凯莱树数量 n^(n-1)这个结果并非显而易见我们将使用一种称为拉格朗日反演的技术来推导它。拉格朗日反演定理 为了分析凯莱树和更复杂的映射结构我们需要一个强大的数学工具拉格朗日反演定理。拉格朗日反演是计算函数反演的一种经典方法。它是一个重要的定理在解析组合学中常作为从生成函数提取系数的“转换定理”。定理描述如下设生成函数G(z)满足方程z f(G(z))其中f(0)0且f(0)≠0。那么G(z)中z^n的系数G_n为G_n (1/n) * [u^(n-1)] ( (u / f(u))^n )符号[u^(n-1)]表示提取u^(n-1)项的系数。更一般的形式是对于任意函数H(u)H(G(z))中z^n的系数为[z^n] H(G(z)) (1/n) * [u^(n-1)] ( H(u) * (u / f(u))^n )我们将在后续分析中直接应用这个定理。应用分析凯莱树 现在让我们应用拉格朗日反演定理来分析凯莱树。凯莱树的类对应于带标签、有根、无序的树。使用符号方法其构造是一棵树是一个根节点连接到一个树的集合顺序无关。这直接翻译成指数生成函数方程C(z) z * e^{C(z)}这个函数被称为凯莱函数。我们可以将其重写为z C(z) / e^{C(z)}。这与拉格朗日反演的形式z f(G(z))相符其中f(u) u / e^u。根据定理C(z)中z^n的系数C_n为C_n (1/n) * [u^(n-1)] ( e^{u*n} )计算e^{u*n}中u^(n-1)的系数我们得到n^(n-1) / (n-1)!。因此n个节点的凯莱树数量为n^(n-1)这与我们之前提到的公式一致。映射的连通分量 上一节我们分析了孤立的树本节中我们来看看映射的核心结构连通分量。一个映射的连通分量是一个“树的环”cycle of trees。也就是说从任何节点出发沿着箭头函数值前进最终都会进入一个循环。整个连通分量由一个环和挂在环节点上的树凯莱树组成。以下是使用符号方法和拉格朗日反演分析连通分量数量的步骤构造一个连通分量是凯莱树构成的环。生成函数根据符号方法环的构造对应于log(1/(1 - C(z)))其中C(z)是凯莱树的EGF。应用拉格朗日反演我们有f(u) u / e^u来自凯莱函数并且我们关心的函数是H(u) log(1/(1 - u))。使用定理的扩展形式我们可以提取系数。结果经过计算包含n个节点的映射中连通分量的数量公式为连通分量数量 ≈ n^n * sqrt(π / (2n))因此一个随机映射是连通的概率约为sqrt(2π/n)。这个分析展示了如何将符号方法与拉格朗日反演结合来研究复杂组合结构的性质。完整映射与路径长度 ️现在我们来看完整的映射以及其中一个关键参数路径长度。一个完整的映射是连通分量的集合。因此其生成函数是1 / (1 - C(z))。应用拉格朗日反演可以验证n个节点上的映射总数确实是n^n这与直接计数每个节点有n种选择的结果一致。路径长度是一个有趣的概念。对于映射中的一个给定起点不断应用该映射函数即x - f(x)直到值首次重复所经历的步数称为该起点的路径长度。在映射中从任何点出发最终都会进入一个环路径长度就是进入环之前走过的“尾巴”长度。计算路径长度有一个著名的“弗洛伊德判圈算法”龟兔赛跑算法它不需要额外存储空间维护两个变量A和B初始值相同。每次迭代A前进一步计算一次fB前进两步计算两次f。当A和B的值相等时说明它们相遇于环中。相遇时的迭代次数与路径长度相关。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/81a83ffa2651c76624f786f2e9fff7f9_2.png对于一个随机映射平均路径长度的渐近公式是平均路径长度 ≈ sqrt(πn / 2)实际应用波拉德ρ因数分解算法 映射的研究并非纯理论它在密码学和算法中有直接应用一个著名的例子是波拉德ρ因数分解算法。该算法用于分解大整数N其核心思想是选择一个随机二次函数f(x) (x^2 c) mod N和一个随机起始值x0。使用弗洛伊德判圈算法迭代计算序列x_{i1} f(x_i)寻找值重复的循环。当找到满足gcd(|x_i - x_j|, N) 1的一对值(x_i, x_j)时就找到了N的一个非平凡因子。为什么映射分析与此相关算法中迭代的函数f(x)行为类似于一个随机映射。虽然f(x)是确定性的但由于模运算和随机起始值其轨迹在统计上可被建模为随机映射。根据我们对随机映射的分析其平均路径长度约为sqrt(πN / 2)。因此波拉德算法期望在约sqrt(N)量级的步数内找到一个因子这比试除法需要O(N)步快得多。这个例子生动地说明了对映射等组合结构的数学分析能够直接指导高效算法的设计与性能预测。总结本节课中我们一起学习了映射的基本定义一个从n个元素到自身的函数对应一个有向图结构。凯莱树作为映射的基础构件其数量由公式n^(n-1)给出。拉格朗日反演定理一个从生成函数提取系数的强大工具我们用它分析了凯莱树和映射的生成函数。映射的分解映射可分解为连通分量每个连通分量是“树的环”。路径长度在映射中迭代函数直到出现循环的步数其平均值为sqrt(πn / 2)。实际应用以波拉德ρ因数分解算法为例展示了映射分析在算法设计和密码学中的重要作用。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/81a83ffa2651c76624f786f2e9fff7f9_4.png映射是一个迷人的组合结构它将简单的概念一个序列与丰富的图论性质、深刻的解析方法以及实际的计算应用紧密联系在一起。042习题与总结 https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/7e7a5ca02c53a22fde3f839bde8a2cb8_0.png在本节课中我们将回顾并完成《算法分析》中关于解析组合学第一部分的习题与总结。我们将通过几个具体的练习来检验对本章内容的理解并回顾所学的核心技术与概念。习题练习以下是几个可用于检验你对本章内容理解的练习题。生日悖论计算 第一个练习是一个计算题。假设你是一位多疑的教授拥有一个很大的班级。你需要计算班级需要有多大才能有99%的把握确定当你询问班上所有人时能找到两个生日相同的人这是一个有趣的计算问题。组合定理证明 下一个练习是一个组合问题。它实际上是线性探查算法linear probing的克努特Knuth分析基础并将我们在本章中涉及的一些与凯莱树Cayley trees相关的计算联系了起来。这个证明实际上比看起来要简单。它旨在证明由AL提出的二项式定理的一个推广形式。完成这个计算是很有价值的。随机映射的概率问题 第三个练习在书中没有但应该被包含在内因此我将其编号为99。这个练习要求证明对于一个大小为n的随机映射其不包含任何单元素环即没有任何元素映射到自身的概率是多少令人惊讶的是结果证明是1/e这与排列中的错排问题derangement problem结果相同。这两者之间并没有明显的必然联系但结果确实相同。这是一个值得你仔细研究的好练习。课程总结与后续建议https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/7e7a5ca02c53a22fde3f839bde8a2cb8_2.png上一节我们介绍了几道检验理解的习题本节我们来对解析组合学第一部分进行总结。至此我们完成了解析组合学第一部分的内容。我们对基本技术进行了相当全面的概述介绍了解析组合学并展示了它如何应用于研究基本的组合结构如树、排列、字符串、单词和映射。我们建议你完成以下步骤以巩固学习阅读教材的相关部分。运行实证测试以验证克努特分析是否有效你会发现它确实有效。查看映射的性质并检查相关分析是否同样有效。尝试完成上述练习并写下解答。我们希望许多同学对我们所探讨的问题足够感兴趣从而报名参加即将开始的解析组合学第二部分课程。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/prct-algo-anls/img/7e7a5ca02c53a22fde3f839bde8a2cb8_4.png本节课中我们一起学习了如何通过具体习题应用解析组合学知识并回顾了第一部分涵盖的核心技术与结构。感谢你的学习。