当前位置:首页 > 开发 > IT生活 > 正文

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

发表于: 2014-01-13   作者:tvmovie   来源:转载   浏览:
摘要: 第7章 指数爆炸——如何解决复杂问题   什么是指数爆炸:数字急速增长 思考题:折纸问题 有倍数游戏的地方,就有指数爆炸。   二分法查找——利用指数爆炸进行查找:每判断1次就能筛选出近一半的查找对象(多判断1次就能从近2 倍的查找对象中找出目标数据)。 思考题:寻找犯人 二分法查找(binary search): 在有序数据中找出目标数据时“总是判断目标数据

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

 

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

思考题:折纸问题

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

 

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

思考题:寻找犯人

二分法查找(binary search):

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

 

对数(logarithm)——掌握指数爆炸的工具

对数:数字中0的个数(底、基数);由约翰·奈皮尔(John Napire, 1550-1617)于1614年发现。

对数和乘方的关系:互逆

对数图表

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

对数和计算尺

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

 

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

暴力破解法(brute-force attack)

字长和安全性的关系

 

如何处理指数爆炸

理解问题空间的大小

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

 

 

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号