2

始める前にはっきりさせておきますが、これは宿題ではなく、試験のために勉強しています。以下の質問に対する解決策を示しました。建設的なフィードバックをお願いします。

前回の質問でフィードバックを残してくれた人に感謝します。以下に、答えがそうであると思う理由の詳細な解決策を示します。

O(n)表記で実行時間を求めます。

int y=0;
for(int j=1; j*j<=n; j++)// runs from 1->j=sqrt(n) times
    y++; //constant - c

したがって、実行時間はc x n^1/2 = O(n^1/2)

Q2.

int b=0;
for(int i=n; i>0; i--) //runs from n->1
    for(int j=0; j<i; j++) // runs from 0 to i
        b=b+5; //constant

内側のループの各値に対して、j (1,2...,n)定数 = を i 回実行しciます。-nc+(n-1)+...+2c+1c = c(n+..+2+1) = cn(n+1)/2 = O(n^2)実行時間。

Q3.

int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs 2n times, increments by 2
    y=y+i; //constant c

int s=0;
for(i=1; i<=j; i++) // not a nested for loop, therefore runs n times
    s++;

実行時間：O(n)

Q4.

int x=0; //constant
for(int i=1; i<=n; i=i*3) //runs log_3 (n) times
{ 
    if(i%2 != 0) // for values above will always be 1

    for(int j=0; j<i; j++) // runs from 0 to log_3(n)
        x++;
}

だから私たちは持っていますclog_3(n)xclog_3(n) = O(log_3(n))^2

4

2 に答える 2

1 
The loops can be thought of as two summations

Summation ( i from 1 to lg_3(n) ) * Summation (j = 0 to i-1) [1 operation]
= Summation (i = 1 to lg_3 (n) (i)
= 1 + 2 + 3....lg_3(n) terms
= lg_3(n) [ lg_3(n) + 1] /2
= O (lg_3(n)] ^2
于 2013-02-10T01:14:58.373 に答える
1

わかりました、最初の 3 つは間違いありません (すべて正しいと思います)。しかし、Q4には問題があります。

あなたの答えは少し間違っています。間違いなく、結果は ではありませんO(log_3(n))^2。ケースは内側のループにあり、正確に時間だけ進みますO(log_3(n))。そして、 from では0-log_3(n)なく from 0-m(mは明らかに と相関していiます)。

以上を踏まえると、正解は だと思いますO(mlog3(n))。しかし、誰かが私が間違っていると思うなら、私を訂正してください.

于 2012-06-20T03:37:17.107 に答える