time - 以下の時間計算量

Question

int i=1,s=1;
while(s<=n)
{
i++;
s=s+i;
}

これの時間計算量は O(root(n)) です。私はそれを理解していません。シリーズは 1+2+...+k のようになるためです。助けてください。

score 2 · Accepted Answer

ループを実行させますx。sこれで、が未満である限り、ループが実行されnます。

我々は持っています：

1回目の反復
s = s + 1
後: 2回目の反復後:
s = s + 1 + 2

x回の反復が続くと、最終的には次のようになります

1 + 2 ... + x <= n

=>(x * (x + 1)) / 2 <= n

=> O(x^2)<= n

=> x= O (root(n))

score 1 · Accepted Answer

s(k) = 1 + 2 + 3 + ... k = (k + 1) * k / 2

s(k) >= n少なくともkステップが必要です。n = (k + 1) * k / 2、したがってk = -1/2 +- sqrt(1 + 4 * n)/2;

定数と係数を無視し、O(-1/2 + sqrt(1+4n)/2) = O(sqrt(n))

score 0 · Accepted Answer

これは合計を計算し、s(k)=1+2+...+kで停止しs(k) > nます。

であるため、がを超えるs(k)=k*(k+1)/2ために必要な反復回数はです。s(k)nO(sqrt(n))

3 に答える 3