算法之道

前言

第一篇 算法基础篇

第1章 从无有到无穷

1.1 意念与现实

1.2 什么是算法

1.3 算法的表示

1.4 算法之魂

1.5 如何比较速度

1.6 算法与计算机的关系

1.7 算法的范畴

1.8 为什么学习算法

思考题

第2章 计数与渐近

2.1 算法的分析

2.2 计数：算法分析的核心

2.3 算法设计

2.4 算法效率表示

2.5 渐近分析

2.6 O表示

2.7 最好、最坏、平均

2.8 O的另一类定义

2.9 O的性质

2.10 要更快的计算机还是要更快的算法

思考题

第3章 分治与递归

3.1 分而治之为上策

3.2 分治策略

3.3 递归表达式求解

3.4 分治策略举例1：乘方运算

3.5 生命不能承受之重：矩阵乘法

3.6 魔鬼序列：斐波那契序列

3.7 VLSI 布线

3.8 多项式乘法

3.9 分治就在潜意识深处

思考题

第二篇 算法设计篇

第4章 动态规划思想

4.1 什么是动态规划

4.2 流水装配线问题

4.3 最长公共子序列

4.4 最长公共子序列变种

4.5 记忆递归法

4.6 空间效率改善

4.7 最优二叉搜索树

4.8 最优子结构与重叠子问题

4.9 动态规划与静态规划的关系

4.10 动态规划与静态规划的相互转换

思考题

第5章 贪婪选择思想

5.1 仅有动态规划是不够的

5.2 什么是贪婪

5.3 背包问题

5.4 贪婪选择属性

5.5 教室规划问题

5.6 最小生成树

5.7 Prim算法

5.8 霍夫曼树和霍夫曼编码

5.9 贪婪选择属性

5.10 标准分治、动态规划和贪婪选择的比较

思考题

第6章 随机化思想

第三篇 算法分析篇

第7章 概率分析

第8章 摊销分析

第9章 竞争分析

第四篇 经典算法篇

第10章 排序和次序

第11章 搜索与哈希

第12章 最短路径

第五篇 难解与无解篇

第13章 可解与不可解

第14章 NP完全问题

第15章 无解与近似

结语 算法之道

附录 算法随想

参考文献

揭橥算法之道，求开智慧之门逻辑演绎、生活归纳、趣味交织、入木三分地揭示算法的奥妙。新的角度、新的分析、新的境界、耳目一新地阐述算法的精华。《算法之道》以全新的角度揭示算法的奥秘，内容囊括了所有重要的算法战略和有独特代表性的算法问题。《算法之道》对算法的基本设计与分析战略、高级设计战略、高级分析战略、经典算法问题、难解与近似算法问题进行了深入的讨论。书中选取的每个算法都在某个方面具有独特性，能够彰显算法的精髓。《算法之道》隐含7个悖论和7个奥秘。如果能够发现一二，你将获得奇妙的感受。《算法之道》有如下几个特点：启示：深入探讨算法背后的逻辑，对算法的剖析达到前所未有的境界。独特：同样的算法、相似的问题，选取不同的角度，帮助读者理解到新的高度。简洁：摈弃臃肿繁琐的内容堆砌，精选代表性的算法问题来彰显算法的普遍逻辑。新颖：不同一般的章节组织使条理更为清晰，在内容上引入部分清新的概念和定义。幽默：以讲故事的形式将算法的精华娓娓道来，易于理解和消化。 本书追求的目标是算法背后的逻辑，是一本启示书，而不是一本包罗万象的算法大全。因此，本书甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。本书将算法的讨论分为五大部分：算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。本书既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。