内部から作業を開始します。 print("")
の反復が実行されているどのように多くの
for(k = 2; k <= n; k = k^2)
print("")
:最も内側のループを考えてみましょうか?最初は、n
が一定であることに注意してください。 k
はどのような値のシーケンスを想定していますか?
iter | k
--------
1 | 2
2 | 4
3 | 16
4 | 256
いくつかの点で、数式が見つかります。私は推測を使用してiter = log(log(k)) + 1
を得ることを証明します。値がすでにn
より大きい場合、ループは次の反復を実行しないため、n
に対して実行された反復の合計数はfloor(log(log(n)) + 1)
です。これを確認するためにいくつかの値を付けて確認することができます。 n = 2
については、正しい1回の反復が得られます。 n = 5
については、2つを取得します。等々。
次のレベルはi + 1
回です。ここで、i
は0からn
まで変化します。したがって、合計1, 2, ..., n + 1
を計算する必要があります。これは、最外ループと中間ループの合計反復回数を返します。この合計は(n + 1)(n + 2)/2
です。内部ループのコストを乗算して合計コストを得るには、(n + 1)(n + 2)(log(log(n)) + 1)/2
を計算する必要がありますスニペットの展開の中で最も急成長している用語はn^2 log(log(n))
であり、一般的に漸近的な複雑さとして与えられるものである。
SOは宿題のためのものではありません。あなたが試したものを投稿してください – Knu8
done ........... –