＜アルゴリズムの基本③＞繰り返し処理（１）１〜Ｎまでの合計を求める

アルゴリズムの処理で最も多く利用するのが、繰り返し処理です。今回は繰り返し処理を使って1〜Nの合計を求めるアルゴリズムについてまとめました。

アルゴリズムの目的

擬似コードを用いて今回のアルゴリズムを表します。合計値を表す変数sumを準備し、それにインデックスidxを足す処理をｎ回繰り返しています。

Procedue SUM(n)
    sum ← 0
    idx ← 1
    while idx ≦ n do
          sum ← sum + idx
          idx ← idx + 1
    end-while
    return sum

Pythonのコード例を以下に示します。上記の擬似コードをそのまま置き換えただけです。

>>> def sum_1_to_n(n):
...     sum_ = 0
...     var = 1
...     while(var <= n):
...         sum_ += var
...         var += 1
...     return sum_


#1〜10までの合計
>>> sum_1_to_n(10)
55
#1〜100までの合計
>>> sum_1_to_n(100)
5050

Nを10^1〜10^8まで振って処理時間がどのように増加していくのかを見てみました。結果を以下のグラフに示します。横軸はデータ数、縦軸は処理時間です。両軸とも基底10の対数値をとっています。（コードはこちら）

1からＮの合計を求めるアルゴリズムの処理時間

グラフの傾きがおよそ１となるので、処理時間はデータ量にほぼ比例して増加しています。加算処理を単純にｎ回繰り返しているだけなので、当然といえば当然かもしれません。

今回は、アルゴリズムでよく使われる「繰り返し処理」を使って、１～Ｎまでの整数値の合計を求めるアルゴリズムについてまとめました。今後は様々なアルゴリズムを擬似コードで表現し、Pythonで実装することで理解を深めていきたいと思います。

（参考文献：杉浦賢、図解でかんたんアルゴリズム　情報処理のかなめとなる考え方が手に取るようにわかる、Softbank Creative）