基本情報技術者：アルゴリズム

アルゴリズムとは？

アルゴリズムはコンピュータに与える計算の手順を示したものです。

変数とは？

変数はデータを格納する箱です。変数はデータの種類によって、文字列、論理値などデータの型を宣言する必要があります。宣言の方法はプログラム言語によって異なります。

フローチャートとは？

端子、処理、判断、ループ端などの記号を用いてアルゴリズムを表現したものをフローチャートと呼びます。

疑似言語とは？

フローチャートを書くのが面倒臭ければ、疑似言語を用います。疑似言語は線や矢印で表現します。

配列とは？

配列は同じデータ型の要素が集まったデータ構造のことを指します。配列には一次配列、二次配列などがあります。データが入った箱を指定やると、データを取り出すｋとおができます。

リスト構造とは？

リストはデータ部とポイント部で構成されたデータ構造です。ポインタ部にはデータのアドレス（格納場所）が入っています。

リスト構造にはポインタの指す方向によって単方向リストと双方向リスト、環状リストがあります。

• 単方向リスト：次のデータへのポインタを１つだけ持っている。
• 双方向リスト：次のデータへのポインタと、前のデータのポインタを持っている。
• 環状リスト：ポインタによってデータが環状に連結している。

配列とリストの違い

どちらもデータの順番と値を格納していますが、以下のような違いがあります。

キューとスタック

キューは格納した順序でデータを取り出すことができるデータ構造です。「先入れ先出し（FIFO）」と呼び、最初に格納したデータは最初に取り出すことができます。キューにデータを格納することをエンキュー、キューからデータを取り出すことをデキューと呼びます。

スタックは格納した順序とは逆の順序でデータを取り出すことができます。「後入れ先出し（LIFO)」と呼び、最後に格納したデータは最初に取り出すことができます。データをスタックに格納することをプッシュ、スタックから取り出すことをポップと呼びます。

木構造（ツリー構造）

木構造は階層の上から下位に節点を作成し、それを辿ることでデータを取り出すことができる構造です。節をノード、枝をブランチ、最下位の節をリーフと呼びます。ツリー構造には完全2分木、2分探索木、ヒープ木などがあります。

• 完全二分木：根から葉までの深さが全て等しいツリーです。
• 二分探索木：左の子＜親＜右の子の構造を持ったツリーです。左の子は右の子よりも全て値が小さいため、情報を値の大きさで整理することができます。
• ヒープ木：親の値が親＞子、または子＜親の関係を持つツリーです。データを整理するのに利用されます。

データの整列

整列はあるデータを昇順・降順に並び替えることをいいます。ソートとも言います。昇順とは値の小さいものから大きいものへと並び替えることで、降順とはその逆です。

基本交換法と比較回数

隣り合う要素を比較して、順番通りに並び変える方法です。比較回数は、まずN個の要素に対して（N-1）回の比較を行い、次に(N-1）個の要素に対して（N-2）回の比較を行います…これを繰り返し、最終的に1回繰り返します。つまり、比較回数の合計は次の通りになります。

これに、逆から書いた式を足すと次のようになります。

Nは(N-1)個存在しているため、Nの合計はN(N-1)です。先ほど、同じ式を2個足したので、比較回数はN(N-1)/2となります。

実際の数値を入れて考えてみましょう。数値の個数Nを5とします。すると、次のような比較回数となります。

これを先ほどの式で表すと…

上下の式を足すと…

合計すると5(5-1)回であり、同じ式を足しているので2で割ると、5(5-1)/2。つまり合計は10回となります。

基本選択法と比較回数

最も小さい（もっとも大きい）要素を取り出して端に置いていき順番通りに並び替える方法です。基本選択法も比較回数は基本交換法と同様にN(N-1)/2です。

基本挿入法と比較回数

基本挿入法は集合から要素を取り出し、順序関係を保つようにして挿入します。全体の比較回数はN(N-1)/2回となります。

改良挿入法（シェルソート）

一定間隔隠岐にデータを取り出したものを整列し、更に間隔を詰めて整列を行う…を繰り返す整列方法です。

クイックソート

適当な基準を決めて、それよりも大きな値と小さな値に分けます。これを繰り返すことで整列を行います。

ヒープソート

未整列の部分を順番に木に構成していき、最大値・最小値を取り出してすでに整列してる部分に移します。

計算量（オーダ）

プログラムがデータを処理する実行時間がどのように変化するかを考えるとき、オーダという概念を利用します。オーダは厳密な実行時間ではなく、データ数が増えればどれくらい実行時間が変化するかを示す目安なので、定数などを無視したりします。

また、オーダは次の規則に則って計算します。

• 順次処理で構成されている部分は、実行時間の最も長い行のオーダが全体の実行時間のオーダとなる。
• 繰り返し処理で構成されている部分は、繰り返される部分のオーダに繰り返し数を掛けた値のオーダが全体の実行時間となる。

例えばn回ループを繰り返すプログラム(ループ1)の中に、さらにn回ループを繰り返すプログラム(ループ2)が入っていた場合、オーダはn²となります。

つまり、基本交換法、基本選択法、基本挿入法のオーダはn²となります。