java - 在java中最有效地计算数组的最大值/最小值

Question

我考虑了两种计算数组最大值/最小值的方法。

首先:

public class Extrema {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    double[] arr = new double[] { -0.11112, -0.07654, -0.03902, 0.0,
            0.03902, 0.07654, 0.11112, 0.14142, 0.1663, 0.18478, 0.19616 };
    double max = Double.NEGATIVE_INFINITY;
    // Find out maximum value
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
}

}

第二种方法是对数组进行预排序，然后将 arr[0] 作为最小值，将数组的最后一个条目作为最大值。

据我所知，最快的排序算法是 0(n log n)。第一种方法的循环将花费 0(n) 时间。但是有 n 次比较和最坏的 n 次写操作。由于 Java 中的时间测量并不是真正可信的，因此有必要将这个问题形式化......我更喜欢第一种方法..对吗？特别是如果我需要两个极值并因此需要 <=n² 写入操作。有多少方法调用相同的数组预排序才有意义？此致，简

Answer 1

首先，给定足够大的输入，时间测量是足够可靠的。

其次，在您的示例代码中，比较和写入操作都无关紧要。大多数时间将花在访问内存中的大型数组(整个问题仅与包含数百万个元素的大型数组相关)并将其移动到 CPU 缓存上。

第三，如果你想要两个极值，最好只通过你的数组一次来获得它们。这对应于 2*n 比较(与 n^2 无关)并且仍然主要通过访问内存中的数组数据来控制。

如果多次需要同一个数组的最大值/最小值，直接存储即可，不要每次都计算。除非您需要在另一个地方对您的数组进行排序(或者您可以对它进行一次预排序并在每次运行程序时重新执行)，否则排序以获得最小值/最大值是没有意义的。