algorithm - ステップが立方根の観点から定義されている再帰の複雑さを見つける方法は?

Question

T(1) = 1

T(n) = T(n^1/3) + 1

どうすれば解決できますか？「解く」とは、O(nlogn) ecc.

置換方法を推測できませんでした。反復法ではどこにも行かず、マスター定理を適用できません。

ここに到着しましたが、よくわかりません:

T(n) = T(n^(1/3^k))) +k

私とアドバイスをお願いできますか？

Answer 1

これが再帰関数の場合、私が理解したのは T(n)= T(integerpart(cubicsquare(n)) +1 ;

この場合 ：

S=0;
if (n>=1){
S++;
N= n;
while  (N>1){
N=integerpart(N^1/3);
S++;
}

}
T(n)= S ;

これは、T(n) が単純な関数であることを意味します: 整数に制限され、ケメ間隔の幅は 2^(3^k) - 2^(3^(k-1)) です。

ご覧のとおり、最初の間隔は if n in ]1,8[ T(n)=2; です。n が [8,252[ ,T(n)=3... の場合、t(2^(3^k)) = k+1 ; 次に t(n) ~O(ln(ln(n))/ln(3)) (スイート 2^3^k を考慮)