如何使用回答是和否的预言机对 N 个元素的数组（其中每个整数属于集合 {1,2,3,,,k}）进行排序？
数组有 n 个元素，每个元素都是集合 {1,2,3,,,,k} 中的整数。有一个预言机可以以“是”或“否”来回答有关数组的任何问题。您只能访问预言机，而不能访问数组。证明数组最多可以通过 O(klog(n)) 查询进行排序。
An array has n elements and each element is an integer from the set {1,2,3,,,,k}. There is an oracle that answers anything about the array in yes or no. You only have access to the oracle and not the array. Show that the array can sorted by at most O(klog(n)) queries.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
由于您知道数组中所有可能的值，因此只需找到每个可能值的频率即可。然后输出正确的 1 的数量、正确的 2 的数量等。
您可以在
Theta(k log n)查询中实现此目的，所有形式：的频率x大于c？”这相当于对每个
k频率进行二分搜索。由于每个元素的频率都是[0, n]中的整数，因此您最多可以使用log_2(n+1)+1个查询来执行二分搜索。Since you know all of the possible values in the array, it suffices to find the frequency of each possible value. Then output the correct number of 1's, the correct number of 2's, etc.
You can achieve this in
Theta(k log n)queries, all of the form:xgreater thanc?"This amounts to doing a binary search for each of the
kfrequencies. Since the frequency of each element is an integer in[0, n], you can do this binary search with at mostlog_2(n+1)+1queries.