《算法之美》:指导工作与生活的算法
2022-07-03 21:42:27 0 举报
AI智能生成
form豆瓣-内容简介:我们所有人的生活都受到有限空间和有限时间的限制,因此常常面临一系列难以抉择的问题。在一天或者一生的时光里,哪些事是我们应该做的,哪些是应该放弃的?我们对杂乱无序的容忍底线是什么?新的活动与熟悉并喜爱的活动之间如何平衡,才能取得令人愉快的结果?这些看似是人类特有的难题,其实不然,因为计算机也面临同样的问题,计算机科学家几十年来也一直在努力解决这些问题,而他们找到的解决方案可以给我们很多启发。 通过丰富的跨学科研究,作者指出,计算机算法也可以用来解答人类面临的这些问题。这本书告诉我们如何更有效地利用直觉、什么时候应该把选择权交给命运、无所适从的时候应该如何做出选择,以及如何有效地与他人保持联系。从找配偶到找停车位,从组织管理个人邮箱的收件箱到理解人类记忆的作用原理,这本书把计算机科学的智慧转化为人类生活的策略,引导我们做出明智的选择。
作者其他创作
大纲/内容
最优停止理论
“摸清情况再行动准则”,先收集一些数据吧,即所谓“观察期”
源于所谓“秘书问题”的37%法则
37%法则具有灵活性
表示数量
表示遴选过程持续的时间
阀值准则:利用37%法则,通过设定的临界点确定需求对象
见好就收:成功的概率/失败的概率=实施的次数
探索与利用
探索:收集信息;利用:利用所拥有的信息
探索价值降低
利用价值升高
赢留输变
“赢留”是探索与利用的平衡优化,而“输变”则没考虑到剩余时间
几何贴现
重现在、轻未来的概念
基廷斯指数
是一个近似估值,用一个数量使两者达成平衡并求这个数量的最大值
贬值
期望值
上限置信区间
在数据点的上下方添加误差条数,误差条越窄表明越精确
误差条线表明被测数量的真实值的合理范围
试验中的临床试验
剩余时间越多时,应多探索
剩余时间越少时,应多利用
排列
互联网中的搜索引擎其次是排序引擎
“大O”符号
讨论问题与程序运行时间的关系
常数时间O(1)
打扫房间的时间客人的数量没有任何关系
线性时间O(n)
食物传递一圈所需要的时间
平方时间O(n²)
与客人相互拥抱的次数
指数时间O(2的n次方)
每增加一个客人都会让工作加倍
阶乘时间O(n!)
通过洗牌为一副扑克牌排序
排序
冒泡排序
逐个移动n个量的位置,而且每次移动需要跨越n个位置
插入排序
逐个移动n个量,而且在插入之前还需将每个量与n个量进行比较
合并排序
把排序对象分成若干组,每组排序后再逐一合并,复杂度为平方对数时间
桶排序
把排序对象按照排序类别分成若干桶,每桶排序后即完成排序,复杂度达到线性时间
分组
插入排序
合并排序
噪声
排序对象的比较结果不确定性
健壮性
一个算法对不合理数据输入的反应能力和处理能力,也称容错性
竞争取代斗争
为了排序对象赋予一个标准的度量,不需要两两比较就可以为一群对象排好次序
缓存
最近最少使用(LRU)
将闲置时间最长的内容清理掉
表现出未卜先知 的效果
最优离线算法
前提是知道各种需求的先后顺序,制定数据结构,把完成整个序列的总时间降到最低
遗忘曲线
增加联系的次数会使记忆更久,随着时间的推移,能够准确回忆的内容会减少
经验暴政
信息检索耗费的精力可以检验知识的渊博
延迟发生的频率可以看出组织管理是否合理
有没有将最重要的东西放在大脑前台
时间调度理论
最早到期日原则
更好的减少最大延迟
最短加工时间
总是先做最快完成的任务
拖延作为一种解决方案
优先级反转
低优先级任务工作时被中断并触发调度器,产生中等优先级任务
优先级继承
当低优先级任务阻碍了高优先级任务时,此时低优先级任务上升为高优先级任务,继承被阻塞的优先级(原本的高优先级)
优先级约束
当某个任务在另一个任务完成前无法启动时的情况
中断合并
反应速度
反应的快慢
吞吐量
可以做多少
关联转换
上下文切换
贝叶斯法则
依赖于先验概率(前提)
对某一事物有一定的预估
大数据类型
小数据类型
计算公式:(w+1)/(n+2)
w为指定事件数;n为样本空间数
哥白尼原则
无先验概率信息(前提)
预测算法:将再持续已经存在的时间;总存在的时间长为已存在时长的2倍
先验预测的分布
幂律分布
先验的可能性有很宽广的尺度
分布在不同区域的数值相乘
相乘法则
正态分布
有一定的先验概率
使用分布的“自然”平均数作为指导
平均法则
厄兰分布
具有更大且更小不可能结束的事物,持续了存在了一段时间
相加法则
保护好自己的先验
当人们谈论一些感兴趣的事或者互联网、电视机械式的传播信息时
偏离了自己的经验统计
很难保持适当的先验分布
博弈论
递归
思想模拟正在模拟思想的思想
均衡策略
势均力敌,相互僵持的状态
陷入无限递归的困境达到均衡的状态
占优势策略
对对手所有可能策略的最佳反应,是强有力的策略
例:囚徒的困境-叛变
调和率
被用做衡量博弈中的合作(解决方案)和竞争(最大利己化)之间的差距
低调和率-无论好坏,系统本身就像它被精心管理的那样良好
高调和率,在谨慎地协调下,事情可能会最终变好,但如果没有某种形式的干预,就会陷入灾难
信息瀑布
在正确的环境下,一群行为完全理性、完全正确的行为者
盲目追崇公共信息流,并认为他人行为是有用的导向
网络
包交换
将它们的消息拆分放入一个个称为“数据包”的小碎片中,再将这些碎片合并到数据的公共流中
访问者说你好
服务器确认你好,并回复你好
访问者确认了这一点
指数退避算法
发送指令时出现的重复冲突次数越多,退避等待的时间越长
即重发的最大延迟长度呈现一种指数级的递增
和式增加积式减少算法
承载量正常时增加数量
承载量饱和时减少一半
缓存膨胀
超过了预期的承载量
尾部丢弃算法
每个在某一点之后到达的数据包都被简单的拒绝,并且有效地删除
通过延时以最大限度提高吞吐量
随机性
抽样
对随机样本进行仔细的检查,可能是一种用以理解太复杂而不能直接理解的东西最有效的方法。通过抽样来估计它的值
随机算法
重复观测快速接近确定性
爬山算法
因为通过搜索解决方案,发现有些方案更好,有些更糟,而你的目标是达到最高的山峰
对比方案的优劣势
对应方案的更好或更糟
局部最大值
如果想继续寻求改进,可能需要暂时恶化解决方案(前提)
对于某个问题时,不要变成全量的随机性,每次做决定时使用一点儿随机性
进化和创造力
一种常见的技术就是引入随机元素
松弛
约束松弛
把问题带回现实前先消除一些约束条件,让问题暂时变的更加容易处理,最后再将约束添加到问题中
最小生成树
持续松弛
将离散的或二进制的选择变成连续体,然后再向上或向下延展
拉格朗日松弛算法
把不可能的变成仅仅是惩罚,要学会扭曲规则的艺术
过度拟合(overfitting)
产生的原因
将重心放在我们能够测量的数据而不是真正重要的问题上
具体表现
单因子模型
表现为一条直线
双因素模型
表现为U型抛物线
九因素模型
表现在图标中的每一个点的串联
检查方法
交叉验证
使用二级数据来进行验证
评估模型是否给出合理的数据
如何概括没有见过的数据
解决方法
正则化
用来约束惩罚模型的复杂性
使优化误差的函数倾向于满足约束的梯度减少的方向
套索算法
把复杂性下行压力放到因素的总权重上,同时设定重要因素的权重降为零,而得到一个更为精炼的模型,保留了子集收缩的优点
早期停止
寻找单一的最重要的因素,而不是直接跳跃到多因素模型
0 条评论
下一页