请教一道看似简单，却不平凡的算法题！

emacsnw

请教我面试某公司时碰到的一道算法题：

1. 你面对一堵左右无限延伸的墙；
2. 该墙有且只有1扇门，它在离你 n 步远的地方；
3. 你不知道 n 的大小，也不知道门在你左边还是右边；
4. 你一次能够向左或者向右走一步，你只有走到门所在的位置才能出去。
请设计一个O(n)的算法，找到这扇门。
请问在最坏情况下，你这个O(n)算法的常数系数最小是多少？也就是说，在最坏情况下，你找到门需要走的步数
S <= K*n+C, K和C都是常数，求最小的K。

欢迎大家讨论。

soul_of_moon

请参考清华出版社出版的数据结构

yzc2002

走法很简单,但复杂度估计比较繁

[ 本帖最后由 yzc2002 于 2006-1-18 09:49 编辑 ]

doni

每次是上一次的2倍

如果用1.618倍,会不会好一些,当然计算出的步数要取整的

emacsnw

你怎么证明是每次2倍，而不是3倍或者1.4倍最优？这样只是提出这是一种O(N)的算法，但没有证明这样最优吧？

AndyFastow

原帖由 emacsnw 于 2006-1-18 13:43 发表
你怎么证明是每次2倍，而不是3倍或者1.4倍最优？这样只是提出这是一种O(N)的算法，但没有证明这样最优吧？

题目没有问设计的O(n)如何最佳，而是要你设计一个O(n) 的算法。

emacsnw

原帖由 AndyFastow 于 2006-1-17 22:56 发表


题目没有问设计的O(n)如何最佳，而是要你设计一个O(n) 的算法。

有问O(n)算法系数K最小多少。

yzc2002

可以得出k最小为4:

peidright

这道题目，一般性的证明感觉有点难度

liexusong

不知道怎么做啊！