【PG初心者向け】アルゴリズムのすすめ

アルゴリズムとは

アルゴリズムって聞いたことありますか？

Wikipediaより引用すると、

アルゴリズム（英: algorithm [ˈælgəˌrɪðəm]）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。

現在では「これらによって『計算可能なもの』を計算する手続き」をアルゴリズムと呼ぶ。

Wikipedia 「アルゴリズム」

私が生徒に説明するときには、解法と呼んでいます。

中学・高校数学でのアルゴリズム

中学・高校数学を想像してみてください。
例えば、２次方程式ax^2 + bx + c = 0 (a,b,cは定数)の解を求めたいときはどうすれば良いでしょうか。
解の公式に代入して計算をしてみます。
x = ( -b ± √(b^2 - 4ac)  ) / 2a
となりますよね。
この、
ax^2 + bx + c = 0 (a,b,cは定数)の解を求めたいときに
解の公式にa,b,cを代入して計算する
というのが、２次方程式の解法すなわちアルゴリズムというわけです。

先人の知恵

今は中学・高校数学で例えを出しましたが、他にも数学で使われるものは様々ありますし、コンピュータに関するもの（特にプログラミング）で用いられるアルゴリズムは多々あります。
これまでの研究者たちが発見・発明したアルゴリズムは、先人の知恵であり、車輪の再発明とならぬよう、アルゴリズムを勉強したり調べながら使うことというのは、大事なのです。
計算効率の大幅な向上、バグの防止、安全性の向上、消費リソースの減少、想定外の自体への対処など、様々な工夫が取り入れられていますので、そこから勉強できることは大きいです。

良いアルゴリズムとは

先程述べた様に、アルゴリズムには様々な工夫がされており、何が良いのかはアルゴリズムの特徴を確認しましょう。
特に重要な部分は、計算時間の短縮です。
計算時間の短縮をすることで、膨大な計算を行うときの計算時間が大幅に変わっていきます。

ソーティングアルゴリズム

アルゴリズムについてもう少し知りたい方はお読みください。

ソーティングとは並べ替えのことです。数列があったときに、これを大きさの順に並べ替えるためのアルゴリズムのことをソーティングアルゴリズムといい、アルゴリズム論では頻出のものです。
どんなものがあるかというと、
バブルソート、選択ソート、ヒープソート、マージソート、クイックソートなどなど...
アルゴリズムの計算時間で優劣をつける際には、最良ケース、平均、最悪ケースの計算量を用います。
例えばバブルソートの最悪ケース計算量は　O(n^2)　という様に書くのですが、
これは要素の個数がn個のときのバブルソートでの計算量の増え方が n^2のグラフの形に近くなることを表しています。
一方クイックソートではどうなるでしょうか。
最悪ケースはO(n^2)とバブルソートと同じなのですが、
平均がO(n\log n)と、大体の他のソートと比較して速いです。
（しかしながら確実に速いわけではありませんし、他のソートの良い点もありますので現在このソートのみが使われているというわけではありません。）

最後に

さまざまなアルゴリズムを勉強することで、思考力のトレーニングにもなりますし、それぞれのアルゴリズムを自分が使うプログラミング言語で書いてみることで、プログラミングの練習にもなります。
ぜひ勉強されると、今後のプログラミング力向上間違いなしです！😊