ループ変数が指数関数的に「拡大または縮小」する場合のループの時間計算量

このような場合、ループの時間計算量は O(log(log(n))) になります。次のケースでは、問題のさまざまな側面を分析します。 ケース 1 : CPP for (int i = 2; i <=n; i = pow(i k)) { // some O(1) expressions or statements } In this case i takes values 2 2^k(2^k)^k= 2^k²(2^k²)^k= 2^k³...2^k^{^{ログ_k(ログ(n))}}。最後の項は n 以下でなければならず、2 になります。^k^{^{ログ_k(ログ(n))}}= 2^ログ(n)= n これは最後の項の値と完全に一致します。したがって、合計ログがあります_k(log(n)) 多くの反復があり、各反復の実行には一定の時間がかかるため、合計の時間計算量は O(log(log(n))) になります。 ケース 2 : CPP

// func() is any constant root function for (int i = n; i > 1; i = func(i))  {   // some O(1) expressions or statements }

In this case i takes values n n^1/k(n^1/k)^1/k= n^1/k²n^1/k³...n^{1/k^{ログ_k(ログ(n))}}合計ログがあります_k(log(n)) 回の反復であり、各反復には O(1) 時間がかかるため、合計の時間計算量は O(log(log(n))) になります。さまざまなタイプのループの分析については、以下の記事を参照してください。 https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ クイズの作成