algorithm - このブロックのシータ表記を見つけるにはどうすればよいですか?

Question

ブロックは次のとおりです。

    i=2  
    while(i<n){  
        i=i*i;  
        x=x+1;  
    }  

x=x+1 が実行される回数のシータ表記を見つける必要があります。いくつかのサンプル値を含むテーブルを作成しましたが、そこから先に進む方法がわかりません。ここに私のサンプル値があります:

(n) - (# times looped)  
  3 - 1  
  5 - 2  
 20 - 3  
400 - 4

Answer 1

これについて考える1つの方法は、ループ内のiの値をトレースすることです。最初の反復の前の値は2= ²¹です。2回目の反復の後、4 =22になり^ます。3回目の反復の後、16 = ²⁴になります。4回目の反復の後、256 =28になり^ます。5回目以降は、65,536 =216^です。

ご覧のとおり、ループをk回繰り返した後、iの値は22kに^なります。これは、反復回数が（おおよそ）kの最小値に対応し、次のようになることを意味します。

22k≥n ^{_ _} _

両側の対数を2回取ると、次のようになります。

22k≥n ^{_ _} _

2k≥log2n ^_ _ _{_} _

k≥log2log2 n _{_} _ _{_}

したがって、ループの反復回数はおおよそlog 2 _log2nです。したがって、ループはO（log log n）回実行されます。より正確には、ループは、k回の反復が経過するまでループが停止しないため、Θ（log log n）回実行されます。

お役に立てれば！