アルゴリズムとは何でしょうか？
「アルゴリズム？」
日常生活を送るなかで聞くことが少ない言葉です。
実際に、何かの物体を指し示しているものでもありません。
じゃあ、いったい何者なのでしょうか？
詳しく見ていきましょう。
アルゴリズムは目に見える物体ではない
「アルゴリズム」
この言葉は、専門用語として見られがちです。
なぜなら、プログラミングを仕事とするプログラマーの方に馴染みのある概念だからです。
プログラミングを作るときには、プログラミング言語ごとに構文が割り振られています。
ｉｆ文やｆｏｒ文は聞いたことのある人がいるでしょう。
アルゴリズムもこれらと関連して存在しています。
アルゴリズムを構文として見るならば、すべてのプログラミング言語において適応可能な構文と位置付けられます。
すなわち、アルゴリズムはプログラミングの核となる技術です。
そのため、プログラマーがどのようなプログラミングを行うのかを決定づける役割を果たします。
では、プログラマーでない人にとっては必要のない情報でしょうか？
「いいえ、違います」
アルゴリズムは、簡単に言ってしまうなら、数学的なパズルゲームのようなものだと断言します。
幅広い分野で様々な問題解決の基本となります。
アルゴリズムを学ぶメリット
アルゴリズムを学ぶことで、私たちは様々な恩恵を得ることができます。
まず、社会生活をしていくうえで問題が生じたときに、どのように解決していくかを明確にできます。
すると、解決法が明確なので問題を迅速に解決できるうえに、問題解決の経験値が貯まります。
さらに、貯まった経験値を活用して、あらゆる方面に知識を得ることができます。
そうして、得られた知識をもとに新しい分野へ挑戦するときの強力な足掛かりになります。
「想像してください」
あなたが生きていくのに必要なものを買いそろえるとき、あなたは頭の中で何かしら情報を処理しているはずです。
過去や現在の情報を参照しながら未来の予測を行って、物品を選別し個数を決定しています。
自分自身が買い物をしているロボットだと想定するなら、プログラミングで動いていることになります。
ということは、アルゴリズムは人間の生活にとって、重要な概念であると説明付けられます。
アルゴリズムの例を考えてみよう
アルゴリズムを用いる例として、学校の授業の成り立ちについて考えてみましょう。
学校においては、クラスの生徒たちがより勉強意欲を持って授業に取り組めるように、［授業の順番と内容］が決められています。
以降では授業の順番と内容を決める流れを、アルゴリズムと見立てて話を進めます。
関連する例を挙げていくのに、ふたつの似通ったアルゴリズムを紹介します。
- ［アルゴリズムＡ］
先生Ａは、各生徒が授業の内容を理解できたかテストの点数で判断します。
授業の順番と内容を決めるために必要な情報は、テストの点数です。 - ［アルゴリズムＢ］
先生Ｂは、各生徒が授業の内容を理解できたかテストの点数以外の情報も含めて判断します。
授業の順番と内容を決めるために必要な情報は、テストの点数とアンケートの結果です。
［アルゴリズムＡ］と［アルゴリズムＢ］
見て分かるように、ふたつのアルゴリズムでは目的達成のための必要な情報が違います。
情報をどのように料理するか
必要な情報を得られたら、その情報をどのように料理するかが重要になってきます。
ここで言う「どのように料理するか」が重要であり、情報技術の世界ではアルゴリズムと定義付けすることができます。
授業の例に話を戻します。
授業の順番と内容を決めるためには、生徒の理解度を測定する必要があります。
各生徒が授業の内容を理解できたか判断するために
- テストの点数を使うなら、０～１００点までの数字を使って判断します。
- アンケートの結果を使うなら、各生徒の意見をもとに判断します。
今回の例は、あくまでひとつの例なので、アルゴリズムＡとアルゴリズムＢ以外にもたくさんのアルゴリズムがあるでしょう。
また、本来ならば目的となる事もたくさんあります。
しかし、アルゴリズムの定義は変わりません。
アルゴリズムとは何なのか？
授業の例を参考として、以下にアルゴリズムの意味を再定義します。
「ある目的を達成するために必要な情報について何をもとに判断するか？」＝［算法体系］
※算法体系（さんぽうたいけい）とは「算術の方法を体系化する」との意味を持つ造語です。
アルゴリズムの定義を整理する
言葉としては
『幅広い分野で様々な問題解決の基本となるもの』
『新しい分野へ挑戦するときの強力な足掛かり』
『人間の生活にとって、重要な概念であると説明付けられる』
などの説明をしてきました。
しかし、本質はひとつだけです。
それは、前の項目でもお伝えした以下の内容です。
「ある目的を達成するために必要な情報について何をもとに判断するか？」＝［算法体系］
アルゴリズムの計算量とは？
アルゴリズムの世界では［計算量］といった指標が存在します。
計算量は数値や文字式で表すことができます。
算法体系を細かく分けたとき、数値や文字式で表現するために計算量を使います。
計算量の例を考えてみよう
引き続きアルゴリズムの説明で用いた授業の例を参考にします。
なかでも、アルゴリズムＡをとりあげます。
- ［アルゴリズムＡ］
先生Ａは、各生徒が授業の内容を理解できたかテストの点数で判断します。
授業の順番と内容を決めるために必要な情報は、テストの点数です。
具体的にテストの採点をするときには、各問題の解答に対して配点していく必要があります。
例えば、テストの問題が１０問あるとするなら、１０回の配点が必要になります。
ということは算法体系は１０回に分けられます。
この場合には計算量は１０になります。
さらに、この１０問それぞれに小問題が３問ずつあり、小問題に配点する場合はどうでしょうか？
そうなると、１０回×３問の合計３０回の配点が必要になります。
ということは算法体系は３０回に分けられます。
この場合には計算量は３０になります。
このように、計算量は算法体系の能力を表現する手段であり、特に同じことをくり返す場合に役立ちます。
なぜなら、計算量１０と３０を見比べたとき、同じ計算の３度くり返しだと分かるからです。
文字式に使われる文字 「n」
計算量は文字式で表すことができます。
まずは、どういった文字を使うのかを知る必要があります。
計算量を文字式で表すときには、よく
自然数とは１から始まる正の整数のことです。
１，２，３，４，５…と無限に続きます。
計算量として用いる場合には自然数ではなく「変数」として扱われます。
※アルゴリズムの世界では変数として
授業の例で文字式を作ろう
では、さっそく計算量を文字式で表してみましょう。
と言いたいところなのですが、アルゴリズムＡの計算量は文字式にできません。
それは、テストの問題数と小問数が固定されているために、変数を使う場面がないからです。
そこで、小問数が何個になるか分からない場合［アルゴリズムＤ］を考えてみましょう。
アルゴリズムＤの計算量はいくつになるでしょうか？
アルゴリズムＤの小問数は不明なので、変数で表すことができます。
具体的には、
このようにして、計算量を文字式で表すことができます。
文字式が判明していれば、変数がいかなる数値の場合にも対応できます。
ここまでの説明で登場した計算過程は算数の基本なので、知識としては厚みに欠けますが、アルゴリズムの計算量を知るために順を追って理解しておくことを推奨します。
計算量の求め方
ここから先の項目では、計算量の成り立ちから見ていき、その種類と求め方を解説します。
計算量に用いられる指標
まず、計算量には［時間計算量］と［空間計算量］があります。
それぞれの意味は
- 時間計算量：データの比較，データの交換，関数の呼び出し
- 空間計算量：補助空間，空間の複雑さ
※補助空間→処理データを保持する空間
※空間の複雑さ→初期データの入出力に使う空間
ほとんどの場合で［時間＞空間］なので空間計算量は無視できます。
そのため、計算対象を選ぶには、時間計算量に該当する候補の中で最も大きい物をとりあげることになります。
［最善，最悪，平均］の計算量を求める
計算対象を選んだ後、詳しい数量（数値や文字式）を調べていくことを「計算量を求める」と言い、それには３つの種類があります。
- 最善：最も得意とするデータの並びを処理する場合
- 最悪：最も不得意とするデータの並びを処理する場合
- 平均：全パターンの計算量を見積もり平均を求める
※「平均」では各入力に対する厳密な答えを得られない場合があります。
別の言い方をすると
- 最善：計算量が一番少なくなる場合
- 最悪：計算量が一番多くなる場合
- 平均：無数のデータを扱ったときの平均の計算量
おさらいすると、計算量とは細分化された算法体系を表現したものでした。
さらに、算法体系とは「ある目的を達成するために必要な情報について何をもとに判断するか？」という意味でした。
その意味では、算法体系がより小さいほど目的達成が容易になります。
すなわち、アルゴリズムの計算量は少ない方が良いのです。
なぜなら、資源は有限であり、時間や空間に制約がある世界において、より速くより小さいものが求められるからです。
そのための指標が最善の計算量です。
また、最悪の計算量や平均の計算量でもって、アルゴリズムの適用能力を調べることができます。
慣習的に、３種類の計算量を調べることになっています。
アルゴリズムの中で数値処理が得意なものがあれば、文字処理が得意なものもあります。
何を処理するかの条件やアルゴリズム構造の違いによって、計算速度に違いが生じるので、計算量のぶれ幅を調べるために種類の違いを設けています。
実際記法で計算量を求める
３つの種類の計算量を求めるには具体的な記述方法が必要です。そこで、まずは実際記法を用います。
実際記法： 計算量の式を各入力に対する厳密な答えを求められるような文字式として記述する
計算量を数字から変数の表現に変換することを「一般化する」と呼び、一般化して出来た文字式を「一般式」と呼びます。
例えば、果物を３個持っている人が２人いる場合には
算数的には比例関係を表しています。
「一方がｎ倍されたとき、もう一方もｎ倍される」
ただし、必ずしも文字式にできるとは限りません。
繰り返さない処理や、あらかじめ計算量が決まっていたり、予測できるような場合には、数値で表現します。
※計算量の表現方法として［数値，数字式，文字式］で区別しています。数値は上記のようなもので、数字式は文字式に変換することが出来る形との捉え方です。
計算量の一般化
計算量を文字式によって一般化する場合の具体的な表記方法は２種類あります。
-
T(n): n -
T(f(n)): n f(n)
※一般化をするときは
※
※
実際記法の記述例
漸近記法で計算量を求める
実際記法とは異なる記述方法として、漸近記法（ランダウ記法）を用いることが可能です。
漸近記法で求めた計算量のことを漸近計算量と呼びます。
「計算量を求める」と言った場合には、この漸近計算量を求めることを最終目的としています。
なぜなら、アルゴリズムのおおよその計算量目安が分かるからです。
漸近記法では、計算量
例えば、実際記法での計算量が
他の計算量の場合も例として一覧にすると
| 実際記法 | 漸近記法 |
|---|---|
※漸近記法では変数ｎにかかる係数は無視できますが、
漸近記法の具体的な表記方法は３種類あります。
-
O(f(n)): n f(n) -
Ω(f(n)): n f(n) -
θ(f(n)): n f(n)
※漸近記法というと基本的に
※
漸近記法を含めた計算量の記述例
漸近計算量は
漸近計算量は
まとめ
計算量を求める最終的な目的は、漸近記法によって計算量を求めること、すなわち漸近計算量を求めることです。
漸近計算量を求めるためには、実際記法によって計算量を求める必要があります。実際記法で３種類になることから、芋づる式に漸近計算量も３種類になります。
実際記法によって計算量を求めるときには［最善，最悪，平均］の３種類があります。アルゴリズムの観点から言えば最善の計算量を、いかに減らしていけるかが重要です。また、最悪や平均の計算量もアルゴリズムの力を推し測る材料となるため必要です。
実際記法によって計算量を求めるとき、その計算対象について細かく区別すると［時間，空間］の違いがありますが、基本的に時間の方を使います。
時間の中にも３種類あり、これは各アルゴリズムによって違いが出るため、アルゴリズムごとに個別で記載します。
計算量とは、細分化された算法体系を表現したものです。
算法体系とは、算術の方法を体系化するという意味の造語です。
アルゴリズムとは、算法体系のことです。
その定義は以下のようなものです。
「ある目的を達成するために必要な情報について何をもとに判断するか？」
各アルゴリズムを説明するにあたって用いる文章構成
-
このアルゴリズムで出来ること
アルゴリズムで達成可能な目的を記載するところです。 -
動作順序
アルゴリズムの動作の流れを番号順に切り分けて記載するところです。
あわせて動作の概要を図示します。 -
計算対象選別
アルゴリズムの計算量として指標に該当するものがあるか調べて、もっとも大きくなるものを計算対象とすることを明示します。 -
変数定義
アルゴリズムの計算量を表現するのに用いる変数を定義するところです。
あわせて変数同士の相互関係を図示します。 -
一般化
計算量の一般化を行い一般式を記載するところです。
※文字式で一般化できないか、その必要がない場合には省略したり［数値，図表，不等式］を用いることがあります。
Discussion
この記事の作成にあたり、参考にしたサイトのリンクを掲載します。