0

私は私の大きなoの計算をブラッシュアップしようとしています. すべてのアイテムを 'i' 2 スペースの右側にシフトする関数がある場合、次のような数式があります。

(n -1) + (n - 2) + (n - 3) ... (n - n)

最初の反復で (x-1) 項目、2 番目の (x-2) 項目などを移動する必要がある場合... メソッド:

int[] s = {1,2,3,4, , }

public static char[] moveStringDownTwoSpaces(char[] s){
    for(int j = 0; j < s.length; j++){

    for(int i = s.length-3; i > j; i--){
        s[i+2] = s[i];
    }
    return s;
    }
}

これが O(n^2) であることはわかっていますが、これを変換する背後にある数学がよくわかりません。

(n -1) + (n - 2) + (n - 3) ... (n - n)

これに

O(n^2)

n = 5 (文字列の長さは 5) の場合、私の考えでは...

(5-1) + (5-2) + (5-3) + (5-4) + (5-5) = 5(5 - ???)

これは

(n-1) + (n-2) + (n-3) + (n-4) + (n-5) = n(n - ???)

これにより、5*5 = 25 (n^2) が得られます。しかし、???とは何ですか？式の変数に何を入れたらよいかわかりません。私がこれを正しい方法で行っているかどうかさえわかりません。AKA私は数学を行う方法を忘れました:(

4

2 に答える 2

3 
(n -1) + (n - 2) + (n - 3) ... (n - n)

次のように書き換えるだけです。

1 + 2 + 3 + ....+ (n-1)

これは次のようになります: (n(n+1)/2 - n).

であることがわかりますO(n^2)。

@hvd で指摘されているように、returnステートメントをループの外に置くことができます。

于 2012-09-29T17:37:28.783 に答える
0

Big-O 表記は正確な上限ではありません。それは漸近的な上限です。多くの場合、アルゴリズムは O(n^2) のように見えますが、償却分析では線形の順序の複雑さが示される場合があります。

于 2012-09-29T17:42:18.920 に答える