※ 引述《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