n> 0の間、nは床（sqrt（n）） - 1になることができますか？

Question

完全な疑問が

我々は機能を持っているはずである

void foo(int n){ 
    int i = n; 
    while(i > 0){ 
    //do an O(n) operation 
    //do some O(1) operations 
    i = sqrt(i) - 1; 
    } 
} 

私は漸近的境界を見つけることがありますが、私は私が把握するまでループが実際に実行される回数ことはできません。私が推測しているのは、平方根を含む別の集計ですが、どのように開始するのか分かりません。

Answer 1

ループが何回実行されるのかを確認する必要があります。

i < 2の場合、ループは最大で2回実行されます。

したがって、< 4の場合、ループはたかだか3回実行されます。

したがって、の場合、ループは最大4回実行されます。

したがって、256の場合、ループは最大5回実行されます。

...

など

あなたは私回< 2 ^（2^m）の場合、ループはほとんどの（M + 2）で実行されることを参照してください。

これは、iがnで開始するので、それが実行される回数の順序は、ログ（ログ（N））、

であることを意味します。

したがって全体の複雑さはO(n*log(log(n))です。ペタルとして

（Oの数は、（1）各反復の動作が一定であればだ。）

Answer 2

同じO（N Nログログ）が、ここでは、いくつかのシャープな境界です。もしI =フロア（SQRT（I））-1、

N < 1は、それはゼロ時間
N <2²は、それがループした場合に最大で1時間
もしN <（2²+1）²ループ場合=5²、N <場合には最大で2倍
ループ（5²+1）²=26²、N <（26²+1）場合には、最大で3回
ループ²=677²、それは最大で4回ループ

On-Line Encyclopedia of Integer Sequencesによれば、このシーケンス（1,2,5,26,677、...）は1.22 ^（2^k）に漸近する[また、k番目の数字は、 f個の高さのバイナリツリーで最大でk]。したがって、数nの場合、ループの数はO（log log n）であり、アルゴリズムはO（n log log n）です。