- 论坛徽章:
- 0
|
本帖最后由 xyfree 于 2010-02-28 04:43 编辑
1. 你面对一堵左右无限延伸的墙；
2. 该墙有且只有1扇门，它在离你 n 步远的地方；
3. 你不知道 n 的大小，也不知道门在你左边还是右边；
4. 你一次能够向左或者向右走一步，你只有走到门所在的位置才能出去。
请设计一个O(n)的算法，找到这扇门。
请问在最坏情况下，你这个O(n)算法的常数系数最小是多少？也就是说，在最坏情况下，你找到门需要走的步数
S <= K*n+C, K和C都是常数，求最小的K。
emacsnw 发表于 2006-01-18 03:41 ![]()
假定墙的长度为L ，L 趋近于无穷时，墙在我的左边和和在我右边的概率是相等的。（这一步的证明过程忘了）
因此，一般情况下，每回合尝试若干次并回归出发点后，左右两方相等步长的区域内的墙都已经尝试过的话，
都能够把问题的状态归纳为出发前的状况，算法可以继续有效演算。
这个算法的时间复杂度对于总次数是O(n)的，证明过程如下:
设在第r回合尝试中，根据不同的回合，尝试向左或向右次数为t，有t(r)。
则该回合尝试中所走的总次数 s(r) = 2t(r) + 2t(r) = 4t(r) （向左走t次，然后向右走2t次，再向左走t次回到起点）
到门之前总的尝试走的次数可以表示为 s(0) + s(1) + s(2) + ... + s(k)，记为 S
其中k必然小于等于n，因为即使最保守的策略，t=r，在第r回合中也只需走n次即可找到门。
于是，总的次数可以表示为不定积分 S =∫s(r)dr = s(0) + s(1) + s(2) + ... + s(k)
对于固定的策略来说，t(r) 是一个 m次多项式，
即 t 对 r 的函数必然可以表示为 t = k[0]× r^m + k[1]× r^(m-1) + ... +k[m] 的形式
不难求得
∫s(r)dr = 4(k[0]× r^(m-1) + k[1]× r^(m-2) + ... + k[m-1])r
= t(k[0]× r^(m-1) + k1× r^(m-2) + ... + k[m-1])
因为找到门的时候，r是确定的常数，即(k[0]× r^(m-1) + k1× r^(m-2) + ... + k[m-1])是一个常数c
所以，找到门的时候尝试的次数 S(t) = ct
于是，算法的时间复杂度函数呈O(n) 形式。命题得证。
前面算法合理的前提是，墙无限长，因此门在我左边或者右边的概率是相等的
并且因为算法的每一步尝试，即针对不同步长的尝试失败之后，我回到原来的位置，这时候不改变概率。
在某种策略下，在第r回合当我尝试往左边和右边各走t次的时候，我找到这个门的概率是 t/n。
因为实际上门在未知方向的n步之外，但我在左右两个方向上各只尝试了t次。
把向某个方向走t次看做是一次独立试验，如果门在这个方向上，那我走n步的时候必然发生目标事件。
概率就等于样本除以总量得到某一次尝试就找到门的概率是t/n。
这样在这种策略下，经过若干回合尝试，终于找到了门。
因为在最坏的情况下最终必然找到了门，就可以表示为当r和n都趋向于无穷大的时候，找到门的概率是1。
所以有以下极限
lim[ r->∞, n->∞] s(0)/n + ( s(1)-s(0) )/n + ( s(2)-s(1) )/n + ... + ( s(r)-s(r-1) )/n = 1
结果是 lim[ r->∞, n->∞] s(r)/n = 1。
------------------------- 下面证实是错的 ----------------- 悲剧了
因为 s(r) = 4t(r)
所以尝试找门的策略应该是 t=r，这样可以满足上面的式子
就是说，改变每回合尝试向某个方向走的次数时，都只比上一次增加1次，就是向左和向右各增加一次。
即有 k = 4, m = 1
由c = (k[0]× r^(m-1) + k1× r^(m-2) + ... + k[m-1]) 得 c = 4
因为 S(t) = ct，
所以 S = 4n |
|
免费注册
楼主: emacsnw
发表于 2010-02-27 11:44
发表于 2010-02-27 19:06
