算法分析导论, 593页pdf

这本书的目的是全面概述在算法的数学分析中使用的主要技术。涵盖的材料从经典的数学主题，包括离散数学，基本的真实分析，和组合学，以及从经典的计算机科学主题，包括算法和数据结构。重点是“平均情况”或“概率”分析，但也涵盖了“最坏情况”或“复杂性”分析所需的基本数学工具。我们假设读者对计算机科学和实际分析的基本概念有一定的熟悉。简而言之，读者应该既能写程序，又能证明定理。否则，这本书是自成一体的。

这本书是用来作为算法分析高级课程的教科书。它也可以用于计算机科学家的离散数学课程，因为它涵盖了离散数学的基本技术，以及组合学和重要的离散结构的基本性质，在计算机科学学生熟悉的背景下。传统的做法是在这类课程中有更广泛的覆盖面，但许多教师可能会发现，这里的方法是一种有用的方式，可以让学生参与到大量的材料中。这本书也可以用来向数学和应用数学的学生介绍与算法和数据结构相关的计算机科学原理。

尽管有大量关于算法数学分析的文献，但该领域的学生和研究人员尚未直接获得广泛使用的方法和模型的基本信息。本书旨在解决这种情况，汇集了大量的材料，旨在为读者提供该领域的挑战的欣赏和学习正在开发的先进工具以应对这些挑战所需的背景知识。补充的论文从文献，这本书可以作为基础的介绍性研究生课程的算法分析，或作为一个参考或基础的研究人员在数学或计算机科学谁想要获得这个领域的文献自学。

第 1 章：算法 分析考虑算法分析的一般动机以及研究算法性能特征的各种方法之间的关系。

第 2 章：递归关系 专注于各种类型的 递归关系的基本数学属性，这些递归关系在通过从程序的递归表示到描述其属性的函数的递归表示的直接映射来分析算法时经常出现。

第 3 章：生成函数 在算法的平均情况分析中介绍了一个核心概念：生成函数 ——作为我们研究对象的算法与发现其属性所必需的分析方法之间的必要且自然的联系。

第 4 章：渐近逼近 研究了推导问题的近似解或逼近精确解的方法，这使我们能够 在分析算法时对感兴趣的数量进行 简洁而精确的估计。

第 5 章：分析组合 学介绍了一种研究组合结构的现代方法，其中生成函数是研究的中心对象。这种方法是通过本书其余部分研究特定结构的基础。

第 6 章：树 研究了许多不同类型的 树的属性，以及在许多实际算法中隐含和显式出现的基本结构。我们的目标是提供对树组合分析的广泛文献结果的访问，同时为大量算法应用提供基础。

第 7 章：排列 调查了排列的组合属性（数字1到N的排序），并展示了它们如何以自然的方式与基本的和广泛使用的排序算法相关联。

第 8 章：字符串和尝试 研究 字符串、字符序列或从固定字母表中提取的字母的基本组合属性，并介绍处理字符串的算法，从计算理论核心的基本方法到实用的文本处理方法重要应用程序的主机。

第 9 章：单词和映射 涵盖单词的全局属性（ 来自M 字母字母表的 N 字母字符串），这些属性在经典组合学（因为它们模拟独立伯努利试验的序列）和经典应用算法（因为它们散列算法的模型输入序列）。本章还涵盖了随机映射 （ N个字母表中的N个字母单词），并讨论了与树和排列的关系。