時間の複雑ときJ + = SQRT（I）私は、この関数の（シータの面で）時間複雑見つける必要があり

Question

：

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）反復を行うので、（ni）/ sqrt（i）のi = 1からn-1までのシグマを計算する必要があります。どのようにそれを行うにはどのようなアイデア？

EDIT： sqrt（）がO（1）で実行されているとします。

Answer 1

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

追加：あなたの複雑なシリーズに関しては 、私はこれが正確であると確信しているが、それは我々が操作の順番を気に、私たちは気にするものではありません。だからあなたのシリーズがO（n^2）かK * n^2であることを示す必要があります。だからあなたはi + 2 * i + ...（n-1）* i + n * iを持ちます。私は定数であるので、それを除外してKで包み込み、1 + ... + nを残します。このステートメントは、nがn = =（n-1）、（n-1）〜=（n-2）と大きく（n-2）〜n =今ではゼロに近づくにつれてこれは成立しませんが、nは非常に大きいので、最初の百万語を落とすことができます。したがって、私たちは C *（n-k）* n + cのようないくつかの関数を残しています。ここで、C、k、およびcはすべて一定です。私たちは定数を気にしないので、nが成長するにつれて成長を気にするだけで、これらの定数をすべて落としてn^2を保存することができます。あるいは、あなたの系列がn^k * nによって束縛されていることを示すことができます。ここで、kはnが無限大に近づくにつれて1に近づきますが、通常は良い論理引数が良いです。 〜ベン