时间复杂度是 sqrt(n) 但我们是如何获得它的呢？
Time comlexity is sqrt(n) but how did we obtained it?
在算法设计和分析的第一步中，我正在阅读 Kleinberg 和 Tardos 的《算法设计》一书，我发现 Question/Case 您可以在页面下方找到
解决方案确实是 f(n) = sqrt(n)。我的顾虑是：
1- 为什么我仍然觉得 log(n) 更可接受。即使据说我们将使用更多的罐子/试验，我仍然无法理解 sqrt(n) 的加值。
2- 我们从哪里得到 sqrt(n) 的？使用 k 罐子（试验）我可以想到 n/k 增量但是然后 lim n→∞ f(n) /n 朝向无穷大是 1/k 这不是 0。我觉得 n 中的 '2' ^1/2 与 k = 2 密切相关，如果是的话如何。
谢谢。
Case: Assume that a factory is doing some stress-testing on various
models of glass jars to determine the height from which they can be
dropped and still not break. The setup for this experiment, on a
particular type of jar, is as follows. You have a ladder with n rungs,
and you want to find the highest rung from which you can drop a copy
of the jar and not have it break. We call this the highest safe rung.
It might be natural to try binary search: drop a jar from the middle
rung, see if it breaks, and then recursively try from rung n/4 or 3n/4
depending on the outcome. But this has the drawback that you could
break a lot of jars in finding the answer. If your primary goal were
to conserve jars, on the other hand, you could try the following
strategy. Start by dropping a jar from the first rung, then the second
rung, and so forth, climbing one higher each time until the jar
breaks. In this way, you only need a single jar—at the moment it
breaks, you have the correct answer—but you may have to drop it n
times. So here is
the trade-off: it seems you can perform fewer drops if you’re willing
to break more jars. To understand better how this trade- off works at
a quantitative level, let’s consider how to run this experiment given
a fixed “budget” of k ≥ 1 jars. In other words, you have to determine
the correct answer—the highest safe rung—and can use at most k jars in
doing so. Now, please solve these two questions:
- Suppose you are given a budget of k = 2 jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at
most f(n) times, for some function f(n) that grows slower than
linearly. (In other words, it should be the case that lim n→∞ f(n)/n =
0.)
log(n)是最好的时间，但是需要log(n)个罐子。
如果我们受限于2个jar，我们可以应用sqrt-strategy。
将第一个罐子从某个高度放下，形成 增加 差异的序列。
对于差异1,2,3,4...，我们有高度序列1,3,6,10,15,21... （所谓的三角形数）。当第一个罐子坏了，我们从previous height+1开始，从第1步开始，直到第二个罐子坏掉。
如果第一个罐子在 15 处破损，我们使用 11, 12, 13, 14 丢弃第二个罐子。
这样的策略给出了O(sqrt(n))次下降，因为三角数公式是n~T(k)=k*(k+1)/2，所以要达到n以上的高度，我们应该使用大约k ~= sqrt(n)次尝试，并且更少比第二个罐子的 k 次试用。
在算法设计和分析的第一步中，我正在阅读 Kleinberg 和 Tardos 的《算法设计》一书，我发现 Question/Case 您可以在页面下方找到 解决方案确实是 f(n) = sqrt(n)。我的顾虑是：
1- 为什么我仍然觉得 log(n) 更可接受。即使据说我们将使用更多的罐子/试验，我仍然无法理解 sqrt(n) 的加值。
2- 我们从哪里得到 sqrt(n) 的？使用 k 罐子（试验）我可以想到 n/k 增量但是然后 lim n→∞ f(n) /n 朝向无穷大是 1/k 这不是 0。我觉得 n 中的 '2' ^1/2 与 k = 2 密切相关，如果是的话如何。
谢谢。
Case: Assume that a factory is doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung. It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung n/4 or 3n/4 depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer. If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it n times. So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of k ≥ 1 jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most k jars in doing so. Now, please solve these two questions:
- Suppose you are given a budget of k = 2 jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most f(n) times, for some function f(n) that grows slower than linearly. (In other words, it should be the case that lim n→∞ f(n)/n = 0.)
log(n)是最好的时间，但是需要log(n)个罐子。
如果我们受限于2个jar，我们可以应用sqrt-strategy。
将第一个罐子从某个高度放下，形成 增加 差异的序列。
对于差异1,2,3,4...，我们有高度序列1,3,6,10,15,21... （所谓的三角形数）。当第一个罐子坏了，我们从previous height+1开始，从第1步开始，直到第二个罐子坏掉。
如果第一个罐子在 15 处破损，我们使用 11, 12, 13, 14 丢弃第二个罐子。
这样的策略给出了O(sqrt(n))次下降，因为三角数公式是n~T(k)=k*(k+1)/2，所以要达到n以上的高度，我们应该使用大约k ~= sqrt(n)次尝试，并且更少比第二个罐子的 k 次试用。