アルゴリズムとは？具体例で徹底理解【プログラミング初心者に贈る】

アルゴリズムとは、行動や計算などの手順・考え方のことです。日常でも、コンピューターの計算においても、どのようなアルゴリズムを用いるかによって完了までにかかる時間などが大きく変わります。そのため、アルゴリズムの改良はどんな分野であっても非常に重要なテーマです。このページでは、アルゴリズムという言葉の意味を確認しつつ、プログラミングでアルゴリズムがどう使われているのかも見ていきます。

このページでは、

を解説しています。

アルゴリズムとは

例えば、以下の問題を考えてみましょう。

この問題を解決するための手順が、アルゴリズムです。まず思いつくのは、全てのコインの重さを1つ1つ量っていくことでしょう。

アルゴリズム①：全てのコインの重さを1つ1つ量っていく

確かにこの方法で確実に答えが求まります。ただ、最初の方に金の入ったコインが見つかれば良いものの、場合によっては時間がかかりすぎます。そこで、別のアルゴリズムを考えてみます。

アルゴリズム②：コインを半分に分け合計の重さを量る

金の入ったコインだけがぴったり15g、他は全てぴったり10gなので、5gの端数が現れたほうに金の入ったコインがあることになります。こうすることで、1回量るごとに候補が半分になっていきます。

このように、アルゴリズムは工夫することによって大幅に時間を短縮できることがあります。ただ、どのようなアルゴリズムが良いかを一概にいうことはできません。例えば、はかりが15gまでしか量れないものだったら、アルゴリズム②は使えませんし、コインが全部で数枚だったらアルゴリズム①でも十分です。アルゴリズムは状況によって柔軟に変えていくことが必要です。

プログラミングでの例

次に、プログラミングの中で使われるアルゴリズムを見ていきます。特にプログラミングでは、実際のコード（命令文）の背景にある手順・考え方、もしくはその発想のことをアルゴリズムと捉えると分かりやすいでしょう。

今回は、数の平方根（ルート）を求めるアルゴリズムを2つ紹介します。√3（＝1.73…）の値を、誤差0.01以内で求めます。プログラムはScratch風の日本語とPythonの両方で示します。

反復法

アルゴリズム（発想）：0から0.01ずつ2乗していく。初めて3以上になった値を答えとする。

プログラム（日本語）：

プログラム（python）：

x = 0
while x**2 <= 3:
   x = x+0.01
print(x)

上記のコードを追っていくと、こうなります：

このアルゴリズムでは、2乗を求める計算を175回行う必要があります。考え方は単純ですが数が大きくなるほど、また精度を高くするほど計算にかかる時間はものすごいスピードで増えていきます。

二分法

アルゴリズム（発想）：答えがある範囲を半分ずつに絞っていく。範囲の幅が0.01以下になったらその下限を答えとする。

プログラム（日本語）：

プログラム（python）：

a = 0
b = 3
while b-a > 0.01:
   c = (a+b)/2
   if c**2 > 3:
      b = c
   else:
      a = c
print(a)

上記のコードを追っていくと、こうなります：

このアルゴリズムでは、2乗を求める計算は9回で済みました。また、範囲の中間を求める計算は2乗に比べて非常に速くできます。よって、考え方はやや複雑ですが計算にかかる時間はかなり少なくなります。

このように答えがある範囲を半分ずつに絞っていく方法を二分探索といい、非常に様々な場面で活用されているアルゴリズムのひとつです。

おまけ：ニュートン法

アルゴリズム（発想）：微分法を応用して平方根を求める。

プログラム（python）：

x = 3
while abs(3-x**2) > 0.01:
  x = (x**2+3)/(2*x)
print(x)

上記のコードを追っていくと、こうなります：

このアルゴリズムでは、驚異的なことに計算が3回で済みました。この方法は、答えの収束が非常に速いことで知られています。

3行まとめ

このページでは、アルゴリズムについて解説しました。まとめると以下の通りです。

皆様の参考になれば幸いです。

当サイトでは教養としての情報科学を体系的に紹介しています。以下から当サイトの記事一覧をご覧いただけます。