1

配列の最大値/最小値を計算するための 2 つのアプローチを検討します。

初め：

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];
        }
    }
}

}

2 番目のアプローチは、配列を事前に並べ替えてから、arr[0] を最小値として取得し、配列の最後のエントリを最大値として取得することです。

私が知っているように、最速のソートアルゴリズムは 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 に答える