1

at(n) ∈ Θ(n^3/2) ランタイムでコードスニペットを作成する必要がある演習を解決しようとしています。

再帰、加算、減算、整数の 2 による除算、for ループ、if ステートメント、<、>、==、および if ステートメントと return ステートメントを使用できます。

t(n) ∈ Θ(n^3) のランタイムを取得するには、3 つの for ループを使用するだけで済みます。また、if ステートメントを使用すると、ランタイムが対数になるこのルールがあったと思います。t(n) ∈ Θ(n^3/2) のランタイムを取得する方法については、まったく考えがありません。

どなたかアドバイスいただけると本当に嬉しいです。ありがとう ：）

4

1 に答える 1

2

これは、 O(N^3/2)で行われる2 からNまでのすべての数値の約数を見つけるためのコード スニペットです。

    for(int i=2;i<=N;i++)
    {
        for(j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                printf("another non-trivial divisor pair for %d is %d,%d",i,j,i/j); 
            }
        }
    }

外側のループはO(N)で、内側はO(N^1/2)です。

于 2015-01-14T09:16:22.987 に答える