猜测一个无界的整数

Question

如果我对你说:

"我想的是0到n之间的数字,我会告诉你你的猜测是高还是低",然后你会立即进行二分搜索.

如果我删除上限怎么办？即我正在考虑一个正整数,你需要猜测它.

一种可能的方法是让你猜测2,4,8,......,直到你猜到某些k为2**k而我说"较低".然后您可以应用二进制搜索.

有更快的方法吗？

编辑:

显然,任何解决方案都需要花费时间与目标数量的大小成比例.如果我通过Ackermann功能查询格雷厄姆的数字,我们将等待你所追求的任何策略.

我也可以提供这个算法:从1开始依次猜测每个整数.

它保证在有限的时间内完成,但它显然比我的"2力量"策略更糟糕.如果我能找到更糟糕的算法(并且知道它更糟),那么也许我可以找到更好的算法？

例如,代替2的幂,也许我可以使用10的幂.然后我找到log_10(n)步骤的上限,而不是log_2(n)步骤.但我必须寻找更大的空间.说k = ceil(log_10(n)).然后我需要log_2(10**k - 10**(k-1))我的二进制搜索的步骤,我想这是关于10+log_2(k).对于2的幂,我在log_2(log_2(n))搜索阶段大致有步骤.哪个胜利？

如果我向上搜索n**n怎么办？还是其他一些序列？奖品是否适用于能够找到增长最快的序列的人？这是答案的问题吗？

谢谢你的想法.我向你们提出道歉,我建议我从MAX_INT或2**32-1开始,因为我显然已经偏离了实用性的界限.

最终编辑:

大家好,

谢谢你的回复.我接受了Norman Ramsey(以及评论者onebyone)的回答,我理解为以下论点:对于目标数n,任何策略必须能够区分(至少)0..n之间的数字,这意味着你需要(至少)O(log(n))比较.

然而,你们的一些人也指出,问题首先没有明确定义,因为在均匀概率分布下不可能选择"随机正整数"(或者说,统一概率分布不能存在于无限集).一旦我给你一个非均匀分布,你可以把它分成两半并正常应用二进制搜索.

当我四处走动时,这是一个我经常思考的问题,所以我很高兴有两个确凿的答案.

Answer 1

如果确实没有上限,并且所有数字一直到无穷大同样可能,那么没有最佳方法可以做到这一点.对于任何有限猜测G,该数字低于G的概率为零,并且它的概率高于1 - 因此没有有限猜测具有高于该数字的期望.

对约翰编辑的回应:

通过相同的推理,10的幂预期优于2的幂(只有有限数量的可能的N,其中2的幂更好,而无穷的数量,其中10的幂更好),20的幂可以被证明比10的力量更好.

所以基本上,是的,奖励进入增长最快的序列(并且对于相同的序列,最高起点) - 对于任何给定的序列,可以证明更快的增长序列将在无限多的情况下获胜.因为对于你命名的任何序列,我可以命名一个增长更快的序列,对于你命名的任何整数,我可以命名一个更高,没有答案无法改进.(并且最终给出正确答案的每个算法都具有无限的预期猜测数量).

Answer 2

人们(从未研究过概率)倾向于认为"从1到N选择一个数字"意味着"每个人的概率相等",并且他们根据他们对概率的直观理解行事.

然后,当你说"选择任何正整数"时,他们仍然认为这意味着"每个人的概率相等".

这当然是不可能的 - 不存在具有正整数域的离散概率分布,其中对于所有n,m,p(n)== p(m).

因此,选择号码的人必须使用其他一些概率分布.如果您对该发行版有任何了解,那么您必须将您的猜测方案建立在该知识上,以便获得"最快"的解决方案.

计算给定猜测方案"快"的唯一方法是计算其预期的猜测次数以找到答案.您只能通过假设目标数量的概率分布来实现此目的.例如,如果他们以概率(1/2)^ n选择了n,那么我认为你最好的猜测方案是"1","2","3",......(平均2个猜测).我还没有证明这一点,也许是其他一些猜测.当然,猜测应该从小开始,慢慢增长.如果他们选择概率为1的4和所有其他概率为0的数字,那么你的最佳猜测方案是"4"(平均1次猜测).如果他们选择了1到1万亿的统一分布数,那么你应该进行二分搜索(平均大约40个猜测).

我说是定义"快"的唯一方法 - 你可以看看最糟糕的情况.你必须在目标上假定一个界限,以防止所有方案具有完全相同的速度,即"不受最坏情况限制".但是您不必假设分布,并且在此定义下"最快"算法的答案是显而易见的 - 从您选择的边界开始的二进制搜索.所以我不确定这个定义是非常有趣的......

在实践中,你不知道分布,但可以根据拾取器是人类以及人类能够构思的数量这一事实做出一些有根据的猜测.正如有人所说,如果他们选择的数字是格雷厄姆数字的阿克曼函数,那么你可能遇到了麻烦.但是如果你知道他们能够用数字表示他们选择的数字,那么这实际上就是他们可以选择的数字的上限.但它仍然取决于他们可能用于生成和记录数字的技术,因此您最了解的是数字在每个特定量级的概率.

Answer 3

最坏的情况是，您可以使用您描述的方法及时找到答案大小的对数。您可以使用阿克曼函数来比对数时间更快地找到上限，但是猜测的数字和前一个猜测之间的二分搜索将需要间隔大小的对数时间，该时间（如果猜测增长非常快）接近于答案大小的对数。

尝试证明没有更快的算法（例如，O(log log n) ）会很有趣，但我不知道该怎么做。