1

次の問題があります。

  1. 次のコードでは、理由とともに、関数の時間計算量を示します。

  2. 同じタスクを実行するが、時間の複雑さが桁違いに改善される関数を作成します。(時間または空間の) 複雑さが大きい関数は評価されません。

コード：

int something(int[] a) {
    for (int i = 0; i < n; i++)
        if (a[i] % 2 == 0) {
             temp = a[i];
             for(int j = i; j > 0; j--)
                a[j] = a[j-1];
             a[0] = temp;
        }
}

私はtemp = a[i]、最悪の場合の代入は の時間で行わnれるため、 の時間複雑度nがそれに割り当てられ、a[j] = a[j-1]実行n(n+1)/2時間であるため、 の時間複雑度の値がそれに割り当てられ、それらを合計すると の時間複雑度が返され、を削除すると考えています定数はと の複雑さにつながります。(n2+n)/2n+0.5n2+0.5n2n+n2n2

桁違いの改善の場合:

int something(int[] a) {
    String answer = "";
    for (int i = 0; i < n; i++) {
       if (a[i] % 2 == 0) answer = a[i] + answer;
       else answer = answer + a[i];
    }
    for (int i = 0; i < n; i++)
       a[i] = answer.charAt(i);
}

最初の for ループ内のコードはn回実行され、2 番目の for ループn時間では、合計すると の時間複雑度の数値が得られ2nます。

これは正しいです？それとも私は何か間違ったことをしていますか？

4

1 に答える 1

0

あなたの機能は、リストの先頭にすべての偶数を配置し、次に奇数を配置することだと思います。

最初の関数の複雑さは、指定したとおりO(n 2 )です。

しかし、2 番目の関数の場合、追加に使用される演算子が定数時間操作として実装されている場合、複雑さはO(n)です。+通常、append 演算子+は、隠れた複雑さのない一定時間の操作として実装されます。したがって、2 番目の操作にはO(n)時間がかかると結論付けることができます。

于 2013-05-10T18:13:17.777 に答える