fc2ブログ



アルゴリズムとは

2006.03.03 22:04  はじめに

アルゴリズムとは「算法」「演算手順」などと直訳することができますが、広い意味では、「あることを達成するための手順」のことです。日常生活の例をとっても、朝起きて→着替えて→朝食を食べて→歯を磨いて→自転車で学校へ行く、という一連の行動も一種のアルゴリズムと考えることができます。一般的にコンピュータの世界ではデータ処理、数値演算、シミュレーションなどの問題を解決するための考え方や手法の事をアルゴリズムと言います。

さらに厳密に言えば、アルゴリズムとは「明確に定義された有限個の規則の集まりであって、有限回適用することにより"問題"を解くもの」です。世の中に存在する問題に応じて、アルゴリズムは無限に存在します。

問題とアルゴリズムの例:

アルゴリズムとは何かを具体的な問題の例を通して考えてみます。

問題:10人分の生徒の名前と身長が記録されたデータを読み込んで、その中で身長が高い順に3人の名前を出力して下さい。類題

このような単純で中途半端な問題にも以下のようにいくつか解法が考えられます。

アルゴリズム1
  1. 10人の中から身長が一番高い人を探して名前を出力する。
  2. 10人の中から(1)ですでに選ばれた人以外から身長が一番高い人を探して名前を出力する。
  3. 10人の中から(1)(2)ですでに選ばれた人以外から身長が一番高い人を探して名前を出力する。

アルゴリズム2
  1. データを身長が高い順に整列する
  2. データの最初の3人の名前を順番に出力する。

もちろんこれらはプログラムとして実装できるアルゴリズムです。この例では、データを整列する計算効率を考えればアルゴリズム1の方が優れているます。一方もしデータを整列するためのアルゴリズムを簡単に書けるまたは信頼できるプログラムが使えるのであれば、アルゴリズム2の方がプログラムが分かり易く簡潔になりかつエラーを出さずに実装できるかもしれません。

このように、与えられた問題には様々な解法が存在します。その解法がアルゴリズムであって問題の定義や性質、さらにプログラムで使うデータ構造などに応じて考えなければなりません。以下の一般化した問題は、どのようなアルゴリズムで解けるかを考えてみると良いかもしれません。

n 個の整数が与えられ、その中で値が大きい順にm 個出力して下さい。ただしn < 1000000、m < 1000 とします。
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ