3

これが私が書いた SelectionSort ルーチンです。次の複雑さの分析は正しいですか?

public static void selectionSort(int[] numbers) {

    // Iterate over each cell starting from the last one and working backwards
    for (int i = numbers.length - 1; i >=1; i--)
    {
        // Always set the max pos to 0 at the start of each iteration
        int maxPos = 0;

        // Start at cell 1 and iterate up to the second last cell
        for (int j = 1; j < i; j++)
        {
            // If the number in the current cell is larger than the one in maxPos,
            // set a new maxPos
            if (numbers[j] > numbers[maxPos])
            {
                maxPos = j;
            }
        }

        // We now have the position of the maximum number. If the maximum number is greater
        // than the number in the current cell swap them
        if (numbers[maxPos] > numbers[i])
        {
            int temp = numbers[i];
            numbers[i] = numbers[maxPos];
            numbers[maxPos] = temp;
        }
    }
}

複雑性分析

外側のループ (比較と代入): 2 つの操作を n 回実行 = 2n の操作

maxPos の割り当て: n ops

内側のループ (比較と割り当て): 2 つの ops が 2n^2 回実行される = 2n² ops

配列要素の比較 (2 つの配列参照と比較): 3n² ops

新しい maxPos の割り当て: n² ops

配列要素の比較 (2 つの配列参照と比較): 3n² ops

割り当てと配列参照: 2n² ops

割り当てと 2 つの配列参照: 3n² ops

割り当てと配列参照: 2n² ops

プリミティブ操作の総数

2n + n + 2n² + 3n² + n^2 + 3n² + 2n² + 3n² + 2n² = 16n² + 3n

Big Oh(n²) につながる

それは正しいように見えますか？特に内側のループとその中のものに関しては...

4

2 に答える 2

2

はい、O(N 2 ) は正しいです。

編集：「第一原理から」という限り、彼らが何を望んでいるかを正確に推測するのは少し難しいですが、彼らは（本質的に）証明（または少なくとも兆候）の順序で何かを探していると思います) big-O の基本的な定義が満たされていること:

次のような正の定数cとn 0が存在します。

すべての n ≥ n 0に対して 0 ≤ f(n) ≤ cg(n) 。

したがって、16N 2 +3N を見つけた後の次のステップは、n 0と cの正しい値を見つけることです。少なくとも一見すると、c は 16、nは0、-3 のように見えます (これはおそらく 0 として扱われ、負の数の要素は実際には意味を持ちません)。

于 2012-05-02T17:11:25.583 に答える
1

一般に、実際の操作を合計することは無意味です (そして正しくありません)。操作にはさまざまな数のプロセッサ サイクルが必要であり、そのうちのいくつかはメモリから値を逆参照するため、より多くの時間がかかります。さらに、コンパイラがコードを最適化するため、さらに複雑になります。キャッシュの局所性などのようなものがあるため、その下ですべてがどのように機能するかを本当に、本当によく知っていない限り、リンゴとオレンジを合計していることになります。「j < i」、「j++」、および「numbers[i] = numbers[maxPos]」を、それらが等しいかのように単純に合計することはできず、そうする必要はありません-複雑さのために分析では、一定時間ブロックは一定時間ブロックです。低レベルのコード最適化を行っていません。

複雑さは確かに N^2 ですが、係数は無意味です。

于 2012-05-02T18:33:29.447 に答える