门在无限墙算法

Question

题:

墙上的门 你正面向一个两个方向无限延伸的墙.墙上有一扇门,但你既不知道多远,也不知道哪个方向.只有当你就在它旁边时才能看到门.设计一种算法,通过步行最多O(n)步骤到达门,其中n是您的初始位置和门之间的步数(未知).

书中答案:

这里的关键思想是每次从初始位置指数地离开时左右走路.一个简单的实现这个想法的是做,直到达到门以下内容:对于i = 0,1,...,使2 ^我步到右边,返回到初始位置,使2 ^我步到左侧,并再次回到初始位置.让2 ^(K-1) <N≤2 ^ķ.此算法找到门所需的步数可在上面估算如下:

因此,算法所做的步骤数量为O(n).(注意:用更好的算法改善乘法常数并不困难.

我迷路的地方:

当它达到总和时,我迷路了.有人可以向我解释这笔钱的工作原理吗？就像为什么他们将2 ^k和2 ⁱ乘以4和3？为什么他们将它与<7·2 ^k进行比较？它是如何等于14·2 ^(k-1),与<14n相比较.我想我得到的事实是n = 2 ^(k-1)这可以解释总和的最后一个但是有很多问题.

Answer 1

4用于计算表示完整搜索的完整步骤的数量.所以我们说我们在i = 1.

我们从x = 0开始.我们去2 ^ 1 = 2.那是2步.然后回到0.另外2个步骤.然后到-2,然后回到0.总共8个步骤,或4 x 2 ^ 1

4 x 2 ^ i =不成功搜索中我们返回原点以开始更大搜索的步数,因为我们只能向左和向右遍历,而不是传送

该kth迭代是当我们发现我们的门.最坏的情况是当门在n左边时n = 2 ^ k步.

那么当我们进入这个迭代时会发生什么？

我们从x = 0开始,我们向右移动2 ^ k,然后返回0,然后向左移动到-2 ^ k.完全遍历3 x 2 ^ k步骤.

至于为什么它与7*2 ^ k进行比较,我们知道ith搜索术语是2 ^ (k - 1)或之前的一切.根据我们之前关于k - 1vs的定义,我们可以用7n替换7*2 ^ kk

我们也可以使用2^k = 2 x 2^(k-1)抽象中的事实.

每@AbcAeffchen 2^(k?1) < n应该,这样你就可以替代2^(k?1)的n,并得到14*2^(k?1) < 14n