PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 一個很像binary search的演算法， …

看板Prob_Solve (計算數學 Problem Solving)作者miick (Mick)時間14年前 (2010/06/18 11:51)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串3/3 (看更多)

※ 引述《Hatred (yo)》之銘言： : ※ 引述《mqazz1 (無法顯示)》之銘言： : : 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的觀念嗎? : : 那我的想法應該要怎麼改進呢? : : 謝謝 : 其實我不是很懂題目的意思 :) : 我猜 price 應該是一正整數吧 (否則如果是任意實數, 好像會沒辦法找), : 可能可以這樣做: : 先猜 price 是 1, 看看是剛好/過高/過低, 假設 (例如) 現在是過低好了, 那就猜 2, : 假如還是過低, 我們就猜 4, 假設仍然過低, 我們就猜 8, 接著就是 16, 32, ... 一直 : 跑下去... : 這樣一直猜到過高為止, 只猜了 O(log n) 次; 第一次過高時, 所猜的數字應不大於 2n, : 所以之後就在 1 到 2n 之間用 binary search 再猜 O(log n) 次得到答案應該就行了. 差不多接近了 2^1一路猜到2^()k+1 1, 2, 4, 8 ... 2^k, 2^(k+1); 2^k<= n <=2^(k+1) 這邊要O(logn) 然後2^k到2^(k+1)之間再用二分法找n 數量是2^k個, 所以需要的時間是O(logk) 所以需要的時間總合是 O(logn+logk) <= O(2logn) < O(n) 故得證 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 222.156.254.82