2 アルゴリズムとデータ構造
これからの授業では，アルゴリズムとデータ構造について学ぶ．アルゴリズムやデータ構 造の実際を学ぶ前に，これらの言葉について簡単に説明しておく．2.1 アルゴリズムとはなにか
1年生の時に，「アルゴリズムとは、問題を解く手順である」と学習したはずである．参 考文献[1]には以下のように書かれており，より正確であろう．アルゴリズム(algorithm， 算法ということもある)は， 問題を解くための手順 を定めたものである．この手順は，どのような操作をどのような順序で行うかを，曖昧な 点の残らないようにきちんと定めたものでなければならない．
手順を明確に定めてあれば，計算機をその手順通り動かして問題を解かせることができ る．アルゴリズムという概念自身は計算機と無関係に成立するが，ふつうは計算機に問 題を解かせるための手順を示す．これから，諸君は計算機で問題を解く手順を学習するのである．問題の解き方はいろいろ あるけれども，効率の良いアルゴリズムを学習することになる．そして，初めてプログラ ムを作成する基礎が出来上がる．
効率とは何かという問題が生じるが，それは大体
- 計算の早い方が良いアルゴリズムである．
- 使用するメモリーがすくない方が良いアルゴリズムである．
良いアルゴリズムは，経験を通して身につけるものであるが，基本的なものによく研究さ れている．そこで，本講義では非常に基本的なアルゴリズムを学習して，将来の応用力を身 につけてもらいたい．基礎がわかっていないと，応用は絶対に不可能である．
2.2 データ構造とはなにか
データ構造(data structure)とは，データのメモリー上の表現方法のことを言う．ただ， アセンブラ言語を除いて，直接メモリーのアドレスを指定して，データを操作するような ことはない．変数や配列，あるいは構造体というものを通して，データを操作することに なる．早いアルゴリズムを実現しようとすると，データの表現方法が重要になる．たとえば， 100個の相異なる整数があって，ある値と一致するものを探すとする．このデータをふつ うの変数に入れたならば，プログラムは大変だし，それの探索(サーチ)の方法も難しいだろう． 配列に入れたならば，ある程度サーチは簡単になる．しかし，データを小さい順に整頓す ればサーチはより簡単になるだろう．データが100個程度ならば，整列の御利益はそんな に大きくないが，100万個くらいになると，かなりのスピードの差が生じる．値を小さい 順に並べるというデータ構造にすると，格段にサーチのスピードアップが図れるのである．
このように，データを並び替えるだけで，サーチのスピードアップが図れるのであるが， 並び替えの時間がかかることを忘れてはならない．ただの1回しか，サーチを行わないの であれば，並び替えの時間だけ無駄に終わることになる．その場合は，並び替えを行わな いで，配列の端から探索する方が良いだろう．このように問題に応じて，なにが良いか を考えなくてはならない．
探索の回数が多くなると，並び替えを行ったデータ構造の方が有利であることは，明らか であろう．アルファベット順に並んでいない辞書は，使えないであろう．ただし，1回し か単語を探さないのであれば，単語をアルファベット順に並べる方が大変である．
データの並び替えにも手間がかかるのは言うまでもない．これよりも，さらに重要なこと
は，整列されたデータ構造の場合，データの追加にも手間がかかるのである．これらのバ
ランスを考えて，データ構造を構築しなくてはならない．この手間のことをコスト(cost:
費用)と表現することもある．データがバラバラに並んだ配列と，小さい順(昇順)に並ん
だデータ構造を比較すると，それぞれのコストは，表1のようにな
る．
問題解決のためのトータルのコストが最小の場合，もっとも良いのアルゴリズムであるし
データ構造でもある．そして，最後にはコストの評価が問題となる．これは，大体計算回
数と同じようなものと考えて良い．ただ，正確にこれを評価するには非常に難しい．実際
には，いろいろなデータでプログラムをテストして，その実行時間を計るのがもっとも正
確な方法と思われる．いつも，プログラムを作ってテストするわけにはいかないので，大
体のコストの計算方法も，ここでは学習の範囲である．ただ，これについては，諸君の数
学の知識では，まだ理解できないことも多いので，あまり難しいことは言わないように心
がける．
ホームページ: Yamamoto's laboratory
著者: 山本昌志 Yamamoto Masashi
平成17年10月27日