本記事の内容
本記事は、基本情報技術者試験におけるアルゴリズムの基本について情報及びコンピュータの素人目線から説明する記事です。
本記事を読むに当たり、アルゴリズムについて知っている必要があるため、以下の記事も合わせてご覧ください。
イントロ (どんなアルゴリズムが出題されるか)
基本情報技術者試験では、以下のアルゴリズムが出題されます。
- 整列アルゴリズム：データを並べるためのアルゴリズム
- 探索アルゴリズム：データを見つけ出すためのアルゴリズム
- 再帰的アルゴリズム：処理の途中で自分自身を呼び出すアルゴリズム
整列アルゴリズム
整列アルゴリズム
整列アルゴリズムとは、データを特定の順番に並べるアルゴリズムを指す。ソートアルゴリズムと呼ばれることもあります。
| 種類 | 解説 |
| バブルソート | 配列の先頭から順に、隣り合ったデータを比較して、順序が違っていたら交換することを繰り返すアルゴリズム |
| 選択ソート | 配列の先頭から順次、データを比較して最小値を選択肢、選択した最小値を先頭のデータと交換することを繰り返すアルゴリズム |
| 挿入ソート | 整列済みの要素を持つ配列に対して、未整列のデータを適切な場所に挿入するアルゴリズム |
| クイックソート | 「基準値よりも小さいグループ」と「基準値よりも大きいグループ」の2つに分け、分けたグループに対しても同じ手順を繰り返すアルゴリズム |
基本情報技術者試験では、クイックソートが頻出で、それ以外が出題されることは稀だそうです。
クイックソート
具体例として、バラバラに配置された1から9までの数を昇順に並べる手順を紹介します。
- 基準値を決める。 基準値はどこでも良いのですが、ここでは列の真ん中の数字「6」とします。
- 基準値「6」よりも小さい数を左のグループに配置し、「6」よりも大きい数を右のグループに配置する。
- 左右に分けられたグループごとに再度、基準値を決めて、2つのグループに分ける。
この手順を繰り返して「これ以上分割できない」というところまで手ヌンを進めると数字が昇順に整列します。
探索アルゴリズム
探索アルゴリズム
探索アルゴリズムとは、特定のデータを見つけ出すアルゴリズムを指す。主とする探索アルゴリズムは以下の3つです。
| 種類 | 説明 |
| 線形探索法 | 先頭のデータから順番に1つずつ照合することで目的のデータを見つける。 |
| ハッシュ法 | ハッシュ表をつかて目的のデータを見つける探索アルゴリズム。 |
| 二分探索法 | 調べる範囲を半分に切り分けながら目的のデータを見つける探索アルゴリズム。 |
ハッシュ法と二分探索法が頻出です。
ハッシュ法
ハッシュ法
ハッシュ法とは、探索対象のデータをハッシュ値に変換し、ハッシュ値を使って目的のデータを見つける探索アルゴリズムである。ハッシュ法は「ハッシュ表探索法」とも呼ばれます。
具体例として、ハッシュ法で上図から「32」を探索する手順を述べます。
ハッシュ法ではまず、ハッシュ関数を使って、探索対象となるデータをハッシュ値に変換します。
ハッシュ値とは、ハッシュ関数の出力です。
代表的はハッシュ関数の1つが剰余です。
ハッシュ関数が「入力した値を10で割った余りを出力する」関数ならば、このハッシュ関数に32を入力すると2が出力されます(\(32\equiv 2\ ({\rm mod}\ 10)\))。
故にこの場合のハッシュ値は2です。
目的のデータはハッシュ値を添え字とした、配列の要素に格納されます。
このようにハッシュ値を添え字に持つ配列をハッシュ表といいます。
つまり、この場合は添字が2である格納場所を探索すれば32を1回で見つけることが出来ます。
ハッシュ法の弱点
入力値が異なっていてもハッシュ値が同じ値になってしまうケースが存在することです。
剰余だとまさにそのとおりですね。
これを衝突と言います。
基本情報技術者試験では「ハッシュ法のデメリットは衝突が起こる可能性があること」というポイントが出題されます。
二分探索法
二分探索法
二分探索法とは、調べる範囲を半分に分割することで目的のデータを見つけるアルゴリズムを指す。二分探索法には以下の2つの特徴があります。
- データを予め整列させておく必要がある
- データを2つに分けながら探索する
例を述べます。
1から9の数字が昇順に並んでいます。
この配列から「6」を二分探索で見つける方法を述べます。
- 列の中から中央の要素を見つける 中央の要素は先頭の添字と末尾の添字の合計を2で割れば見つけられます。
- 右半分の要素に対して、1.と同じ操作をする \((5+8)\div 2=6.5\fallingdtoseq6\)です。
今回は、\((0+8)\div2=4\)です。
\(8>5\)により、列の左半分のグループに6 が存在しないことがわかります。
小数点以下を切り上げるか切り捨てるかは、どちらでもOKです。
添字6の要素7と探索対象の6を比較します。
\(6<7\)により、探索範囲を左半分のグループに絞ります。
この操作を続けることで目的のデータを見つけることが出来ます。
再帰的アルゴリズム
再帰的アルゴリズム
再帰的アルゴリズムとは、処理の中で自分自身を呼び出すアルゴリズムを指す。再帰とは繰り返しを意味します。
基本情報技術者試験において再帰的アルゴリズムは主として「総和、剰余、階乗」の3つを求める際に出題されます。
再帰的アルゴリズムによる総和の求め方
基本情報技術者試験では頻出のようです。
「1から5までの整数の総和」を例に述べます。
この問題の答えは15です。数式での表現で
この問題を数式で表現すれば、以下です。
$$
f(x)=
\begin{cases}
1&(x\leq 1)\\
x+f(x-1)&(x>1)
\end{cases}
$$
まさに、自身を呼び出して使っています。
この、処理の中で自分自信を呼び出している箇所が再帰的アルゴリズムです。
\begin{eqnarray}
f(5)&=&5+f(4)\\
&=&5+4+f(3)\\
&=&5+4+3+f(2)\\
&=&5+$+3+2+f(1)\\
&=&5+4+3+2+1
\end{eqnarray}
プログラム言語で表現
プログラム言語で表現すれば以下です。
f(x): if x≦1 then return 1 else return x+f(x-1)アルゴリズムの計算量を算出する問題
異なるアルゴリズムであっても、出力が同じ場合があります。
このとき、実行時間が短く、メモリの使用量が少ないアルゴリズムの方が優秀です。
オーダー(計算量)とは
アルゴリズムを完了するために必要な計算量のことをオーダーといいます。
データ\(\)と計算量の関係を表す記法をオーダー記法といい、O(計算量)で表します。
尚、オーダーは「これ以上大きくならない」という最大の計算量を表します。
アルゴリズムのオーダー
一覧を表示します。
| アルゴリズム | オーダー記法による計算量 |
| ハッシュ法 | \(O(1)\) |
| 二分探索法 | \(O(\log_2n)\)または\(\log n\) |
| 線形探索法 | \(O(n)\) |
| クイックソート | \(O(n\log n)\) |
復習問題
探索方法とその実行時間のオーダーの適切な組み合わせはどれか、ここで、探索するデータの数をnとし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また、実行時間のオーダーが\(n^2\)であるとは、n個のデータを処理する時間が\(cn^2\)(cは定数)で抑えられることをいう。
| 二分探索 | 線形探索 | ハッシュ探索 | |
| ア | \(\log_2n\) | \(n\) | 1 |
| イ | \(n\log_2n\) | \(n\) | \(\log_2n\) |
| ウ | \(n\log_2n\) | \(n^2\) | 1 |
| エ | \(n^2\) | 1 | \(n\) |
答え
ア結
今回は、基本情報技術者試験におけるアルゴリズムの種類について、情報及びコンピュータの素人目線から説明しました。
問題が解けるということに重きを置き説明しました。
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
Twitterでもリプ、DM問わず質問、コメントを大募集しております！
コメントをする