一个人站在一维线的原点。他正试图到达一个方向上距离k步之遥的点。方向未知，距离也未知。如何在 O（k） 步骤中完成此操作。
我知道答案可能是显而易见的，但我似乎无法弄清楚。谢谢。
蛙可以跳（一次一个垫）到1，-1,2，-2,4，-4,8，-8,16，-16等。也就是说，青蛙朝一个方向跳跃，直到她到达一个距离中心从未有过的 2 次方的垫子，然后开始向另一个方向跳回去。
如果魔术垫距离中心N，则跳总数最多为4（1+2+4+...+2^ceil（lg N））。这是4（2^（1+ceil（lg N））-1），小于16N。
青蛙不能只朝一个方向走，否则它可能会错过神奇的睡莲垫; 所以它必须朝两个方向走。
青蛙只能在一个方向上走这么远，然后才不得不检查另一个方向;为了覆盖整个睡莲垫条，它需要来回走动。
在一次尝试中，他将尝试在距离起点不到 x 的距离处查看所有睡莲垫。他会向前跳x跳，2x后跳，再向前x，用4x跳覆盖2x睡莲垫。
尝试 1，然后是 2 中的一个，然后是 3 等中的一个将导致啤酒花过多，在O(n²)啤酒花中仅覆盖n睡莲垫。
但是，如果尝试的距离是指数级数，则在找到魔术睡莲垫之前，他将进行失败的尝试次数是有限制的。如果他尝试 1，然后是 2，然后是 4，然后是 8 等（2^n ，也适用于更大的基地），他会在 O(n) 跳中覆盖n睡莲垫。
O（n） 定义为最大时间复杂度或完成上限。 如果您连续有 n 个睡莲垫，则直通遍历最多需要 O（n），因为每个睡莲垫都会访问一次。唯一的问题是，如果青蛙被放置在行中间的某个地方（而不是一端），并且行是无限的。 在这种情况下，您需要确定遍历该行的方向（左或右），并且您有可能永远找不到神奇的睡莲垫。 此外，无限行意味着n接近无穷大（所以O（n）可能是一个无限长的时间段！ 如果青蛙从向两个方向扩展的无限行集的中间开始，我看不到答案。如果青蛙从无限行集的一端开始，则通过在同一方向一次跳一个睡莲垫来实现 O（n）。
我能找到的唯一解决方案是朝随机方向走 n 步，如果你最终没有到达魔垫，请转身走 2n 步。 所以最坏的情况是 3n 步。3n 与 n 成正比 - 它线性增长。 所以O（n）。