在无限长的墙上找到一扇门
Finding a door in an infinitly long wall
假设您站在一堵巨大的墙前。
墙在你的左右两侧无限长。你知道某处有一扇门，你试图找到它到达另一边。
可惜现在是晚上，只能摸到眼前的那部分墙
你不知道门有多远，也不知道你要往哪个方向走，但你可以从你的起点开始计算你的步数。
你如何解决这个问题？
天真的方法是从起点开始，向右+1，检查，如果没有找到门，则转到起点，然后-1，再次检查。如果仍然没有门，你将不得不去开始并检查右边的 +2 等等......
这将导致 O(n^2) 步找到门（其中 n 是从起点到门的步数）。
有没有更好的方法？甚至在 O(n) 步内？
我什至不知道我应该问什么标签，如果您认为合适，请随意添加。
问题是你不知道该走哪条路，所以无论你想出什么办法，你都得回到原点，从另一条路开始。此外，你永远不能排除任何一个方向，直到你找到让你回到原点的门，使用任何足够大 n 的算法多次返回原点（我假设 n 是门的距离从原点）。
这意味着我们想尽可能少回去，但我们仍然不得不回去。解决办法不是只增加一步，而是增加两倍的距离。
为了简单而不损害渐近复杂性，我们将行驶距离 d 到某个点，然后返回，向另一个方向行驶相同的距离，最后再次返回。这只会为我们的复杂性提供常量 4，因此我们稍后可以忽略它。无论如何，当我谈论一次迭代时，它意味着所有这 4 条路线，即使你在上一次迭代中完成所有这些路线之前已经找到了门。
因此，在第一步中，您可以前往 2 号地块，然后前往 4 号地块，然后是 8、16 号地块，依此类推。
您将在第 k 次迭代中找到 2^k >= n > 2^(k-1) 处的门，这意味着 k >= log(n) > k-1。为简单起见，我们可以假设 n 是 2 的幂，因为对于计算而言，n 是例如 33 还是 64（或减去其中任何一个）并不重要，我们将在同一次迭代中找到所有这些。所以我们可以写成k = log(n).
您现在只是对几何序列的一部分求和，因此在第 k 次迭代之后您将总共走过 4 * 2*(2^k - 1)/(2 - 1) = 8 * (2^log(n) - 1) = 8 * (n - 1) = 8n - 8 = O(n)。
假设您站在一堵巨大的墙前。 墙在你的左右两侧无限长。你知道某处有一扇门，你试图找到它到达另一边。 可惜现在是晚上，只能摸到眼前的那部分墙
你不知道门有多远，也不知道你要往哪个方向走，但你可以从你的起点开始计算你的步数。
你如何解决这个问题？
天真的方法是从起点开始，向右+1，检查，如果没有找到门，则转到起点，然后-1，再次检查。如果仍然没有门，你将不得不去开始并检查右边的 +2 等等......
这将导致 O(n^2) 步找到门（其中 n 是从起点到门的步数）。
有没有更好的方法？甚至在 O(n) 步内？
我什至不知道我应该问什么标签，如果您认为合适，请随意添加。
问题是你不知道该走哪条路，所以无论你想出什么办法，你都得回到原点，从另一条路开始。此外，你永远不能排除任何一个方向，直到你找到让你回到原点的门，使用任何足够大 n 的算法多次返回原点（我假设 n 是门的距离从原点）。
这意味着我们想尽可能少回去，但我们仍然不得不回去。解决办法不是只增加一步，而是增加两倍的距离。
为了简单而不损害渐近复杂性，我们将行驶距离 d 到某个点，然后返回，向另一个方向行驶相同的距离，最后再次返回。这只会为我们的复杂性提供常量 4，因此我们稍后可以忽略它。无论如何，当我谈论一次迭代时，它意味着所有这 4 条路线，即使你在上一次迭代中完成所有这些路线之前已经找到了门。
因此，在第一步中，您可以前往 2 号地块，然后前往 4 号地块，然后是 8、16 号地块，依此类推。
您将在第 k 次迭代中找到 2^k >= n > 2^(k-1) 处的门，这意味着 k >= log(n) > k-1。为简单起见，我们可以假设 n 是 2 的幂，因为对于计算而言，n 是例如 33 还是 64（或减去其中任何一个）并不重要，我们将在同一次迭代中找到所有这些。所以我们可以写成k = log(n).
您现在只是对几何序列的一部分求和，因此在第 k 次迭代之后您将总共走过 4 * 2*(2^k - 1)/(2 - 1) = 8 * (2^log(n) - 1) = 8 * (n - 1) = 8n - 8 = O(n)。