考虑一个相当普遍的问题——我正在考虑一个整数，你能在 O(log n) 时间内猜出它吗，因为我会用“高”、“低”或“就是那个!”来回答你的猜测。 - 我遇到了一个让我难过的细微变化的问题:
I am thinking of a positive real number between 1 and N. Guess my number to within one decimal place in O(log log log N) time.
我尝试通过猜测 10N 而不是 N 来解决这个问题，但这仍然不会给我 O(log log log N) 运行时间。欢迎就此提出任何和所有意见。
谢谢
最佳答案
假设“一位小数以内”表示一位有效数字，则在 1 和 n 之间有 O(log(n)) 种可能的猜测。 1, 2, 3, ..., 10, 20, 30, ..., 100, 200, 300, ... 对这些可能性进行二分搜索将在 O(log(log(n)) 中产生正确答案时间。为了便于编码，这可以改为对数量级进行二进制搜索，然后对第一个数字进行二进制搜索。但是，从信息理论上讲，不可能使用 O(log(log(log( n))) 猜测以确定 O(log(n)) 种可能性之一。
示例:我正在考虑 1 到 10000 之间的数字。
是100吗？更高。 是1000吗？降低。 现在我们知道数量级了。
是500吗？更高。 是700吗？更高。 是800吗？更高。 是 900。
关于algorithm - 二进制搜索来猜测实数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20874964/