在这种情况下排序更好吗？

Question

假设在笛卡尔坐标中有一组点，并且想要找到四个极值点，如x-min，y-min，x-max和y-max。

如果单独使用x-坐标和y-坐标对点进行排序，则需要O(n log )* 2。

要想在不排序的情况下找到四个端点，就需要O(n) * 4。(它必须从开始到结尾比较这些点)。

一旦我们对这些点进行排序，找到接下来的四个极值点就可以取O(1)了，不是吗？

但如果不进行排序，它将再次花费O(n) *4。还是O(n-4) *4？下一次O(n-8)*4，O(n-12) *4等等？

所以，如果我们想要递归地找到这四个端点，直到找不到点。对于排序需要O(n日志n)，但如果不排序，则需要多少时间？是O(n)吗？

在这种情况下，用排序递归地找到四个端点会更好吗？

Answer 1

一旦我们对这些点进行排序，找到接下来的四个极值点就可以取O(1)了，不是吗？

是。

但如果不进行排序，它将再次花费O(n) *4。还是O(n-4) *4？下一次O(n-8)*4，O(n-12) *4等等？

是。

所以，如果我们想要递归地找到这四个端点，直到找不到点。对于排序需要O(n日志n)，但如果不排序，则需要多少时间？是O(n)吗？

“递归”的意思可能是“迭代”。但否则，如果不进行排序，则需要O(n^2)。不要忘记，您需要找到n个顺序极值，这会使这种方法的复杂性乘以n。

在这种情况下，用排序递归地找到四个端点会更好吗？

的确如此，因为复杂性较低。

Answer 2

常数因子在大O复杂度表示法中并不重要。O(100000n)与O(n +/- 100000)相同，后者与O(n)相同。

递归地查找端点，直到找不到为止，将花费O(n^2)时间，因为对于ith (1 )极值点，您必须执行n - i + 1比较，即第一个端点的n比较，第二个端点的n - 1比较，这会给出总的n(n + 1)/2比较，这与O(n^2)和n^2相同是更大的因素。

另一方面，对点排序将花费O(n log n)时间(假设进行快速排序或合并排序)。如果必须使用不同的表示形式，按照顺序查找n极值点将需要O(n) (必须迭代排序数组一次)。在这两种情况下，时间复杂性将保持O(n log n)，因为它是更大的因素。

所以是的，排序是更有效的方法。

Answer 3

对于给定的轴，您应该能够在一次迭代(o(n))中找到max和min。

   int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int i : xAxisArray){
        if(i < min){
            min = i;
        }
        if(i > max){
            max = i;
        }
    }

因此，它将是o(n)*2。所以，您可以使用这个来代替排序，但这是只有当您必须这样做一次。

如果你需要对所有的点都这样做，排序就是方法。