[問題] 一個很像binary search的演算法， …
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (2010/05/28 21:36)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/3 (看更多)
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)
推
05/28 21:41, , 1F
05/28 21:41, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12