0

2つのアルゴリズムはΘ（n ^ 2）の同じシータ特性を持っていますか？

int sum = 0;
for (int i = 0; i < n; i++ )
    for (int j = 0; j < n * n; j++ )
        sum++;

int sum = 0;
for ( int i = 0; i < n; i++)
    for ( int j = 0; j < i; j++)
        sum++;

そうでない場合、これはこの特性がΘ（n ^ 3）ではないことを意味しますか？

int sum = 0;
for ( int i = 0; i < n; i++)
    for ( int j = 0; j < i * i; j++ )
        for ( int k = 0; k < j; k++ )
            sum++;
4

1 に答える 1

2

@ダン、最初のものは本当にではj < n * nなく意味がありましたj < nか？だとすると、最初の時間計算量は Θ(n^3) ですね。

という意味であればj < n、最初の 2 つは両方とも Θ(n^2) であると思います: 最初のステップは n^2 ステップ、2 番目のステップは 1 + 2 + ... + n = n(n+1)/ 2 これは Θ(n^2) です。

3つ目はΘ(n^4)だと思うのですが、証明が難しいです。間違いなく O(n^4) です。

于 2010-09-29T02:56:47.400 に答える