3

この関数の時間複雑度 (シータに関して) を見つける必要があります。

int x = 0; 
for (int i=1; i < n ; i++) { 
  for (double j=i; j <= n ; j+=sqrt(i)) { 
    ++x; 
  } 
}

外側のループは n-1 回の繰り返しを行い、内側のループは (ni)/sqrt(i) 回の繰り返しを行うことがわかっているので、i=1 から (ni)/sqrt(i) の n-1 までのシグマを計算する必要があります。それを行う方法はありますか？

編集: sqrt() が O(1) で実行されると仮定します。

4

1 に答える 1

0

シグマとシータの意味はわかりませんが、sqrtは定数時間の演算であるため、基本的に大きなO表記、つまりj + = sqrt（i）では問題になりません。j +=iと同じです。j +=1;と同じです。また、（nk）nよりはるかに小さいkの場合は〜=n。これは、nが大きくなると、niはちょうどnになることを意味します。したがって、（ni）* sqrt（）= n * 1=nです。そして、これを外側のループに対してn回行うので、n^2です。

添加： あなたの複雑なシリーズに関しては、これは正確であると確信していますが、それは私たちが気にしていることではなく、操作の順序を気にします。したがって、シリーズがO（n ^ 2）またはK * n^2であることを示す必要があります。つまり、i + 2 * i + ...（n-1）* i + n*iになります。ここで、iは定数なので、因数分解してKでラップし、1 + ...+nのままにします。このステートメントはnによって支配されます。つまり、nが大きくなるとn〜=（n-1）、および（n-1）〜=（n-2）は、（n-2）〜=nを意味します。ゼロに近づくと、これは当てはまりませんが、nが非常に大きいため、最初の100万項を削除できます。したがって、C *（nk）* n+cのような関数が残ります。ここで、C、k、およびcはすべて定数です。定数は気にしないので、nが大きくなるにつれて成長を気にするだけで、これらの定数をすべて削除して、n^2を保存できます。または、シリーズがn^k * nで囲まれていることを示すことができます。ここで、nが無限大に近づくとkは1になりますが、通常は適切な論理引数の方が適しています。〜ベン

于 2012-04-13T21:17:31.397 に答える