電脳ヨーグルト

プログラミングの備忘録と私生活を

アルゴリズムとはなにかをざっくり解説します。

f:id:at25250410:20180417092852p:plain

アルゴリズムってよく聞くけどなんなの?みたいな人に向けての記事です。

アルゴリズムは以下のように定義されています。

アルゴリズム

与えられた問題の正しい答えを求めるための'うまいやり方'であり、一般に文章やプログラミング言語で記述される。

 まぁいまいちピンときませんよね。そこで具体例をもとにみてみます。

 

例えば料理におけるアルゴリズムに相当するものとして料理レシピや料理本などがあり、記述されている手順通りに料理を作ればおいしい料理を作ることができます。

同じ料理を作るにしても自己流だとあまり美味しくないし、プロのレシピに従えば美味しく作れます。ある料理を作るにしても沢山の手法があり、その手法それぞれをアルゴリズムと言います。

 

そしてどのアルゴリズムが良くて、どれが悪いのかを私たちにわかり易くしたものに「アルゴリズムの評価基準」というものがあります。

アルゴリズムの評価基準もケースによっていろいろなものが存在します。料理だったらよりおいしい料理ができる調理方法のほうが良いアルゴリズムになるわけです。

 

プログラムの世界においては良いアルゴリズムとはずばり'速く計算が実行できるアルゴリズムのほうが優れている'という評価基準です。

 

同じ結果が出力されるプログラムでも、コードの書き方によって実行時間は大きく異なります。

このアルゴリズムの実行時間を時間計算量とよび、最も早く実行できるアルゴリズムの時間計算量を最良時間計算量、最も遅い実行時間のアルゴリズムの時間計算量を最悪時間計算量と呼びます。

 

では次に3つの時間計算量が異なるアルゴリズムを比較してアルゴリズムを評価してみます。

 

具体例(3つのアルゴリズム)

アルゴリズムの時間計算量

アルゴリズムA 10n^2 + 100n + 10000 主要項(10n^2)

アルゴリズムB n^4 + n ^3 - n 主要項(n^4)

アルゴリズムC 100n^3 主要項(100n^3)

 

正直これじゃあどのアルゴリズムの時間計算量が大きいのか比較のしようがなくて分からないですよね。

 

そこでオーダ記法とよばれるものを用いることで簡単に比較できるようにします。

 

オーダ記法の定義はちょっと分かり辛くなるので省略します。

 

オーダ記法はアルゴリズムの時間計算量の中で主要項(nを無限大に近づけたときにその関数の中で最も大きくなる項)を見つけます。

そして主要項の係数を取り除いたものが、オーダ記法を用いたアルゴリズムの時間計算量になります。

 

オーダ記法を用いたアルゴリズムの時間計算量

アルゴリズムA O(n^2) 主要項(10n^2)

アルゴリズムB O(n^4) 主要項(n^4)

アルゴリズムC O(n^3) 主要項(100n^3)

 

このようにオーダ記法を用いると、アルゴリズムAが最も実行時間が速く良いアルゴリズムで、反対にアルゴリズムBは一番遅くあまりよくないアルゴリズムだと可視化できます。

 

ざっくりいうとこんな感じです。