[程序员的数学]notes——chapter 7

第7章 指数爆炸——如何解决复杂问题

 

什么是指数爆炸：数字急速增长

思考题：折纸问题

有倍数游戏的地方，就有指数爆炸。

 

二分法查找——利用指数爆炸进行查找：每判断1次就能筛选出近一半的查找对象（多判断1次就能从近2 倍的查找对象中找出目标数据）。

思考题：寻找犯人

二分法查找（binary search）：

在有序数据中找出目标数据时“总是判断目标数据所在范围内正中间数据”的方法。

 

对数（logarithm）——掌握指数爆炸的工具

对数：数字中0的个数（底、基数）；由约翰·奈皮尔（John Napire, 1550-1617）于1614年发现。

对数和乘方的关系：互逆

对数图表

指数法则和对数：将乘法转化为加法计算。

对数和计算尺

计算尺：使用对数进行乘方计算时的一种辅助工具。

 

密码——利用指数爆炸加密

暴力破解法（brute-force attack）

字长和安全性的关系

 

如何处理指数爆炸

理解问题空间的大小

4种处理方法：极力求解、变相求解、近视求解、概率求解