<アルゴリズムの基本③> 繰り返し処理(1) 1〜Nまでの合計を求める

アルゴリズム その他

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

アルゴリズムの目的

  • 繰り返し処理を用いて1〜Nまでの整数値の合計を求める

擬似コード例

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

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

Pythonコード例

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からNの合計を求めるアルゴリズムの処理時間

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

まとめ

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

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

Learn more...

書籍でもう少し詳しく学びたい場合はこちらもどうぞ。筆者もかなり参考にさせてもらっています!

シェアする
ひびきをフォローする
Hbk project

コメント