1

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

第一的：

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] 作为最小值，将 te 数组的最后一个条目作为最大值。

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

4

3 回答 3

2

首先，给定足够大的输入，时间测量就足够真实了。

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

第三，如果你想要两个极值，最好只在通过你的阵列一次时得到它们。这对应于 2*n 比较（与 n^2 无关），并且仍然主要通过访问内存中的数组数据来主导。

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

于 2013-06-12T13:16:48.580 回答
1

第一种方法具有计算复杂性O(n)，而第二种方法O(n*log(n))正如您所说。但请记住，渐近复杂度忽略了常数因素，因此很容易出现线性算法实际上比线性算法慢的情况n*log(n)。但是，在您的特定情况下，您不能比简单的迭代更好，这实际上是最好的解决方案。

仍然可能有趣的是，有一种线性算法可以在基于 qsort 分区的序列中找到第 k 个元素。该算法内置在 C++ 的 stl 中。如果有兴趣可以看看这里。

如果数组永远不会改变并且您有很多查询，那么第一种方法至少可以和第二种方法一样快 - 只需缓存在第一个查询中找到的值。

于 2013-06-12T13:12:31.150 回答
0

只是一个想法 ..

无论您选择哪种搜索算法，您都可以随时利用多线程。比如说 array size = 10 ，你可以产生两个线程 1. thread-1 会在数组的前半部分进行搜索，2. Thread-2 会在数组的后半部分进行搜索 3. 最后你比较这两个线程的结果以决定结果。

如果您选择考虑多线程来加快搜索速度，则必须考虑几个因素，例如最佳线程数（因为线程数过多会导致大部分时间花在上下文切换上）、堆栈可用性等。

于 2013-06-13T08:46:16.087 回答