アルゴリズムの処理で最も多く利用するのが、繰り返し処理です。今回は繰り返し処理を使って1〜Nの合計を求めるアルゴリズムについてまとめました。
アルゴリズムの目的
- 繰り返し処理を用いて1〜Nまでの整数値の合計を求める
擬似コード例
擬似コードを用いて今回のアルゴリズムを表します。合計値を表す変数sumを準備し、それにインデックスidxを足す処理をn回繰り返しています。
Pythonコード例
Pythonのコード例を以下に示します。上記の擬似コードをそのまま置き換えただけです。
出力例
処理時間
Nを10^1〜10^8まで振って処理時間がどのように増加していくのかを見てみました。結果を以下のグラフに示します。横軸はデータ数、縦軸は処理時間です。両軸とも基底10の対数値をとっています。(コードはこちら)
グラフの傾きがおよそ1となるので、処理時間はデータ量にほぼ比例して増加しています。加算処理を単純にn回繰り返しているだけなので、当然といえば当然かもしれません。
まとめ
今回は、アルゴリズムでよく使われる「繰り返し処理」を使って、1~Nまでの整数値の合計を求めるアルゴリズムについてまとめました。今後は様々なアルゴリズムを擬似コードで表現し、Pythonで実装することで理解を深めていきたいと思います。
(参考文献:杉浦賢、図解でかんたんアルゴリズム 情報処理のかなめとなる考え方が手に取るようにわかる、Softbank Creative)
コメント