原来的问题在这里讨论：在 O(n log n) 时间内找到特殊点 k 的算法 https://stackoverflow.com/questions/7626813/algorithm-to-find-special-point-k-in-on-log-n-time
简而言之，我们有一个算法可以确定平面上的一组点是否具有对称中心。
我想知道有没有办法证明这个算法的下界（nlogn）？我想我们需要使用这个算法来解决更简单的问题，例如排序、元素唯一性或集合唯一性，因此我们可以得出结论，如果我们可以解决例如通过使用该算法，元素唯一性至少可以为nlogn。
似乎解决方案与元素唯一性有关，但我无法找到一种方法将其操纵为对称中心算法。
Check 这张纸 http://www.ri.cmu.edu/publication_view.html?pub_id=112
这个想法是，如果我们可以将问题 A 简化为问题 B，那么 B 并不比 A 难。
也就是说，如果问题 B 有下界 Ω（nlogn），那么问题 A 就保证有相同的下界。
在论文中，作者选择了以下相对容易实现的问题作为B：给定两组n个实数，我们希望确定它们是否相同。
显然，这个引入的问题有下界Ω（nlogn）。以下是作者如何将我们手头的问题简化为引入的问题（A、B 表示以下上下文中的两个实数集）：
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
