作者mqazz1 (无法显示)
看板Prob_Solve
标题[问题] 一个很像binary search的演算法， …
时间Fri May 28 21:36:02 2010
suppose that you are go guess the price of a commodity without knowing its price in advance,
how fast can you guess its price,
assuming the real price of the commodity is n.
use less than O(n) comparisons.
如果这是运用到binary search的观念
我记得binary search好像是O(logn)
那我先从比n大的数开始开始猜
之後每次都取它的中间数猜下去..应该就可以在O(n)内猜到
可是题目一开始说 不知道商品的价格
那应该就没办法一开始就先猜到比n大的数..
请问这题可以运用到binary search的观念吗?
那我的想法应该要怎麽改进呢?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.118.189
※ 编辑: mqazz1 来自: 218.166.118.189 (05/28 21:37)
1F：推 FRAXIS:从1猜到n 复杂度就是O(n).. 05/28 21:41