两个掉蛋拼图变体：unknown/infinite 层
Two egg dropping puzzle variation: unknown/infinite floors
前言
这个问题的灵感来自上周关于 SO 的一个类似问题，在弄清楚真正的问题是什么之前就被删除了。我认为这个变体是一个很好的问题，我想与大家分享。
双蛋问题
可以找到详细的定义和解决方案 here，但我将添加一个快速摘要：
定义
You are given two eggs, and access to a k-storey building. Both eggs
are identical. The aim is to find out the highest floor f* from which an
egg will not break when dropped out of a window from that floor. If an
egg is dropped and does not break, it is undamaged and can be dropped
again. However, once an egg is broken, that’s it for that egg. What is the fastes (least amount of drops) way to find f*?
解决方案
想法是从地板上掉下第一个鸡蛋 sqrt(k), 2*sqrt(k), 3*sqrt(k)... k。如果鸡蛋在 i*sqrt(k) 层破裂，请使用第二个鸡蛋测试 (i-1)*sqrt(k) 和 i*sqrt(k)-1 之间的剩余楼层。总体而言，这将导致最多 2*sqrt(k) 下降，因此复杂度将为 O(sqrt(k)).
为了完整起见：有一种方法在最坏的情况下丢包更少（可以找到详细信息here），但是其复杂度与O(sqrt(k))
相同
问题：infinite/unknown 层的两个鸡蛋问题
现在假设您没有关于楼层数的信息 k 或 k 是无限的。是否有可能发现 f* 比仅在 O(f*) 中测试每个楼层更有效？
换句话说：是否有高效方法来丢掉两个运行时复杂度独立于k但只取决于答案f*的鸡蛋]?
有一个复杂度为 O(sqrt(f*)) 的简单方法。让你的第 n 步向上 n 层，即检查第 1、3 (1 + 2)、6 (1 + 2 + 3) 层等。这样在第 n 步你将在 n*(n+ 1)/2 层，您将在 n = O(sqrt(f*)) 步中到达 f*。
那么对于第二个鸡蛋，您需要在第 1 阶段的最后一步基础上进行 n 步，这将增加另一个 O(sqrt(f*))。
如果 O(sqrt(k)) 对于已知的 k 是最优的，那么这个方法在复杂度方面也必须是最优的。
两个鸡蛋的无限问题的次优解决方案是使用序列 1, 2^2, 3^3,... ,i^2,... 并从第一个鸡蛋保留的最后一个值开始第二条边。因此，如果第一个边缘保持在 n^2，那么下一个边缘将最多进行 2*n + 1 - 1（从第一个边缘减去 1）测试，以在最坏的情况下给出 3 * n 的总数 n = sqrt(m).
前言
这个问题的灵感来自上周关于 SO 的一个类似问题，在弄清楚真正的问题是什么之前就被删除了。我认为这个变体是一个很好的问题，我想与大家分享。
双蛋问题
可以找到详细的定义和解决方案 here，但我将添加一个快速摘要：
定义
You are given two eggs, and access to a
k-storey building. Both eggs are identical. The aim is to find out the highest floorf*from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg. What is the fastes (least amount of drops) way to findf*?
解决方案
想法是从地板上掉下第一个鸡蛋 sqrt(k), 2*sqrt(k), 3*sqrt(k)... k。如果鸡蛋在 i*sqrt(k) 层破裂，请使用第二个鸡蛋测试 (i-1)*sqrt(k) 和 i*sqrt(k)-1 之间的剩余楼层。总体而言，这将导致最多 2*sqrt(k) 下降，因此复杂度将为 O(sqrt(k)).
为了完整起见：有一种方法在最坏的情况下丢包更少（可以找到详细信息here），但是其复杂度与O(sqrt(k))
问题：infinite/unknown 层的两个鸡蛋问题
现在假设您没有关于楼层数的信息 k 或 k 是无限的。是否有可能发现 f* 比仅在 O(f*) 中测试每个楼层更有效？
换句话说：是否有高效方法来丢掉两个运行时复杂度独立于k但只取决于答案f*的鸡蛋]?
有一个复杂度为 O(sqrt(f*)) 的简单方法。让你的第 n 步向上 n 层，即检查第 1、3 (1 + 2)、6 (1 + 2 + 3) 层等。这样在第 n 步你将在 n*(n+ 1)/2 层，您将在 n = O(sqrt(f*)) 步中到达 f*。
那么对于第二个鸡蛋，您需要在第 1 阶段的最后一步基础上进行 n 步，这将增加另一个 O(sqrt(f*))。
如果 O(sqrt(k)) 对于已知的 k 是最优的，那么这个方法在复杂度方面也必须是最优的。
两个鸡蛋的无限问题的次优解决方案是使用序列 1, 2^2, 3^3,... ,i^2,... 并从第一个鸡蛋保留的最后一个值开始第二条边。因此，如果第一个边缘保持在 n^2，那么下一个边缘将最多进行 2*n + 1 - 1（从第一个边缘减去 1）测试，以在最坏的情况下给出 3 * n 的总数 n = sqrt(m).