找到一个下界为nlogn算法

本文介绍了找到一个下界为nlogn算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

原来的问题是在这里讨论：Algorithm找到O特殊点K（N log n）的时间

The original problem was discussed in here: Algorithm to find special point k in O(n log n) time

简单，我们有一种算法，找出平面中一个点的集合是否具有对称性与否的中心。

Simply we have an algorithm that finds whether a set of points in the plane has a center of symmetry or not.

我不知道有没有办法来证明一个下界（nlogn）这个算法？我想我们需要使用该算法来解决simplier问题，如排序，元素的独特性，或者设置的独特性，因此，我们可以得出结论，如果我们能解决如元素的唯一性通过使用这种算法，它可以是至少nlogn

I wonder is there a way to prove a lower bound (nlogn) to this algorithm? I guess we need to use this algorithm to solve a simplier problem, such as sorting, element uniqueness, or set uniqueness, therefore we can conclude that if we can solve e.g. element uniqueness by using this algorithm, it can be at least nlogn.

这似乎是解决方案是与元素的独特性，但我无法想出一个办法来处理这​​个成对称算法的中心。

It seems like the solution is something to do with element uniqueness, but i couldn't figure out a way to manipulate this into center of symmetry algorithm.

推荐答案

请本文

我们的想法是，如果我们可以减少问题A到问题B，那么B是不超过一个更难。

The idea is if we can reduce problem A to problem B, then B is no harder than A.

这是说，如果问题B有下界Ω（nlogn），那么问题的一个保证相同的下限。

That said, if problem B has lower bound Ω（nlogn）, then problem A is guaranteed the same lower bound.

在本文中，笔者选择了以下比较平易近人的问题是B：给定的两组N个实数，我们要决定是否它们是相同的。

In the paper, the author picked the following relatively approachable problem to be B: given two sets of n real numbers, we wish to decide whether or not they are identical.

很显然，这个问题的介绍有下界Ω（nlogn）。下面是手头的作者如何降低我们的问题所引入的问题（A，B表示在以下范围内的两个真实套）：

It's obvious that this introduced problem has lower bound Ω（nlogn）. Here's how the author reduced our problem at hand to the introduced problem (A, B denote the two real sets in the following context):