
二重ループの実行回数を数える
解き方
内側の繰返し回数が外側の変数に依存する問題では、各回の回数を足します。積で計算できるのは、内側の回数が毎回同じ場合です。
手順を追う例
countを0に初期化し、iを1からnまで増やします。各iについてjを1からiまで増やし、その都度countを1増やします。n=3なら加算回数は1+2+3です。
確認問題【オリジナル】
n=5のときcountはいくつになりますか。一般のnに対する式も答えてください。
答えと解説
15です。各iの加算回数を足すと1+2+3+4+5=15になります。一般にはn(n+1)÷2です。nが大きくなると主要な項はnの2乗に比例するため、処理回数の増え方はO(n²)と表します。