最大時間計算量を求める問題なので、この下の解説を読んでも全く意味が分からないのですが、どなたか分かり

最大時間計算量を求める問題なので、この下の解説を読んでも全く意味が分からないのですが、どなたか分かりやすく説明してくださる方いませんでしょうか？？

No.1 ベストアンサー 回答者： 青鉄 回答日時： 2018/06/28 08:02

説明といっても解説文のとおりですよ。

この問題はfor文の動きが理解できているか、がポイントかと思います。

for文は、その行の実行中に終了条件を満たしたかを判断するため、i=2でスタートしても結局n回実行されるところが注意点です。（解説のとおり）

で解説に書いてあることを項目にして整理すると、

・1行目は一回だけの実行（ループ内に入ってないから）
・2行目は、for文で繰り返されます。(n回)
・3行目もfor文の中なので繰り返されます。(n-1回)
・4行目もfor文の中なので繰り返されます。(n-1回)
・7行目は一回だけの実行（ループ内に入ってないから）

で、上から順番に足して1+(n)+(n-1)+(n-1)+1 = 3nです。

あと、動きを掴むために、D(1)=1, D(2)=2, D(3)=3、D(4)=4、n=4と具体的な数値を入れてみて、何回ループされるかプログラムを追ってみるといいでしょう。

質問では、質問者さんがつまづいているポイントが分からないので、もしそういうことではない、というなら、分からないポイントを教えてください。

この回答へのお礼

おはようございます、わざわざご丁寧な説明ありがとうございます！分からない点が、例えば、for文などのそもそもの意味(初期化式など)が分からなくて調べたら合点がいきました。
分からない点があれば是非またお願いします。ありがとうございます。

お礼日時：2018/06/29 10:42