《算法技术手册》一2.4.2 对数级算法的性能

简介: 本节书摘来华章计算机《算法技术手册》一书中的第2章 ,第2.4.2节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4.2 对数级算法的性能

酒保和顾客打了一个10 000 美元的赌。酒保说:“我会从1~1 000 000中挑选一个秘密数字,你有20次的机会来猜这个数字。每次猜完,我会告诉你结果是高了、低了,还是猜中了。如果你能在20个问题之内猜到我的秘密数字,我给你10 000美元,否则你给我10 000美元。”你会打这个赌吗?回答当然是应该打,因为你能够稳赢。表2-1给出了范围为1~8的示例场景。表中展示了如何通过一系列的询问,每次将候选数据缩减一半。
表2-1:在1~8之间猜数字的示例行为
2017_09_19_161341
酒保的每次回答都可以将数字范围缩减一半,直到剩下最后一个可能的数字。最后的情况会在1 + log2 (n)次询问之后出现,其中log2(x)是计算以2为底数的x的对数。向下取整函数x将数字x向下取整到小于等于x的最大整数。例如,如果酒保选择的数字在1~10,你需要猜测的次数为1 + log2 (10)= 1 + 3.32,即4次。如果需要进一步证实上述公式,可以假设酒保在两个数字中选择一个,那么你需要两次才能保证猜到该数字,即1 + log2 (2) = 1 + 1 = 2。需要注意的是,根据酒保的规则,你必须要说出你猜的数字。
这种方法在1 000 000个数字的时候也同样可行。事实上,例2-1所示的猜数算法能够对于任意范围[low, high]有效,并且在1 +log2 (high-low+1)次内猜测到隐藏的数字n。如果有1 000 000个数字,那么这个算法将在最多1 +log2 (1 000 000)= 1 + 19.93亖最多猜20次(最坏情况)就可以知道是哪个数字。
例2-1:在范围[low, high]之间猜数字的Java代码
// 当n确认在范围[low, high]时,计算需要猜测的次数
public static int turns (int n, int low, int high) {
int turns = 0;
// 如果还有潜在的数字需要猜测,则继续
while (high >= low) {

turns++;
int mid = (low + high)/2;
if (mid == n) {
   return turns;
} else if (mid < n) {
  low = mid + 1;
} else {
  high = mid -1;
}

}
return turns;
}
对数级算法是非常高效的,因为它们能够快速收敛得到解。这种算法的成功之处在于可以每次将问题的规模缩减一半。以上的猜数算法最多经过k = 1 + log2 (n)次迭代就可以得到解,在第i次(0在书中接下去的部分中,log(n)均指代以2为底的对数,因此我们会舍弃log2 (n)中的下标。
另外一个展现高效对数级算法的例子是使用二分(bisection)算法求一元方程的根,即求出满足连续型函数f(x) = 0的x。已知有两个初始值a和b,其中f(a)和f(b)正负符号相反,即一个是正数,另一个是负数。在每一步中,算法二分范围[a, b]并计算它的中间点c,以此来决定根所在的半区间。因此,每一轮都会使得c更加近似根值,并将误差值削减一半。
为了求f(x) = xsin(x)-5x -cos(x)的根,已知a = -1,b = 1。算法会逐渐收敛至f(x) = 0,x=-0.189302759即为方程的根(见表2-2)。
表2-2:二分法
2017_09_19_161641

相关文章
|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
7天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
8天前
|
算法
基于ADM自适应增量调制算法的matlab性能仿真
该文主要探讨基于MATLAB的ADM自适应增量调制算法仿真,对比ADM与DM算法。通过图表展示调制与解调效果,核心程序包括输入输出比较及SNR分析。ADM算法根据信号斜率动态调整量化步长,以适应信号变化。在MATLAB中实现ADM涉及定义输入信号、初始化参数、执行算法逻辑及性能评估。
|
9天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
12天前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
16 0
|
12天前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
13 0
|
14天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python。
|
15天前
|
存储 人工智能 算法
RAG技术的高级应用和算法
文章主要探讨了RAG技术的高级应用和算法,系统化地整理了各种方法。
|
15天前
|
机器学习/深度学习 数据采集 算法
基于机器学习的推荐算法构建技术详解
【6月更文挑战第4天】本文详述了构建基于机器学习的推荐算法,特别是协同过滤方法。从用户和物品相似性的角度,解释了用户-用户和物品-物品协同过滤的工作原理。涵盖了数据准备、预处理、特征工程、模型训练、评估优化及结果展示的构建流程。推荐算法在电商、视频和音乐平台广泛应用,未来将受益于大数据和AI技术的进步,提供更智能的推荐服务。

热门文章

最新文章