オーダー記法(O記法)と計算量についてわかりやすく解説!!【基本情報】

この記事で解決できる内容

※タップすると該当箇所までジャンプできます。

この記事では、オーダー記法と呼ばれるアルゴリズムの性能を表す計算量をの表記についてわかりやすく解説していきます。

アルゴリズムとは、計算や処理の手順のことで、オーダー記法はその処理の回数を表現するのに用いられます。アルゴリズムの中でも、たくさんのデータの中から特定のデータを見つける探索アルゴリズムの分野で多く出てくるのがオーダー記法です。

この記事を最後まで読んでいただくこと下記のような問いに答えられるようになります。

整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれ整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

ア. log n
イ. n
ウ. n²
エ. n log²

平成27年春期　問6

過去の情報技術者試験でも出題されている問題で、これから基本情報技術者試験などを受験する予定があるのであれば、しっかり理解しておきましょう。

>> 基本情報技術者試験の学習方法をまとめた記事はこちら

オーダー記法(O記法)についてわかりやすく解説

オーダー記法とはアルゴリズムの性能を評価する際に用いられる計算量を表現する方法のことで、O(1) や O(log₂n) のように表現します。

1つの問題を解決するにあたって、たくさんのアルゴリズムが存在しており、どのアルゴリズムを採用するか判断するために、アルゴリズムの良しあしを比較するときなどに計算量で比較したりします。

オーダー記法が表す計算量とは？

計算量とはアルゴリズムの性能を表す指標となる値です。

アルゴリズムが、処理の完了にかかる時間や、処理の回数を数値で表したもので、

このときに便利なのが計算量です。計算量には、時間計算量と空間計算量が存在しますが、今回のオーダー記法で表現するのは、時間計算量です。

優秀なアルゴリズムとは？

アルゴリズムとは、コンピュータの処理の手順や計算方法のことで、アルゴリズムを見える化したものを流れ図やフローチャートと呼ばれます。

例えば、「野菜炒めを作るアルゴリズム」とは「野菜炒めを作る手順」という意味で、

一番、処理の回数が少なく、処理が完了するまでの時間も短いアルゴリズムが「優秀なアルゴリズム」です。

探索アルゴリズム計算量でオーダー記法をわかりやすく説明します

オーダー記法の違いを分かりやすく説明するときに便利なのが、探索アルゴリズムです。

探索アルゴリズムとは「特定の値を探索するアルゴリズム」のことで、以下のような種類があります。

線形探索法の計算量は？

線形探索法とは、データが配列に格納されているときに便利な探索法です。

特に断りが無い限り、データは配列に格納されています。線形探索法は配列の先頭から添字を更新しながら順々に比較していく単純な方法です。

線形探索法のポイントは以下の通りです。

線型探索法のポイント

2分探索法の計算量は？

2分探索法とは、昇順もしくは降順に整列されたデータ領域の中央を調べ、目的のデータが中央の値より前にあるか後ろにあるかを判断して、段々と範囲を絞っていく探索アルゴリズムです。

2分探索法のポイントは以下のとおりです。

2分探索法のポイント

ハッシュ探索法(ハッシュ法)の計算量は？

ハッシュ表探索法(ハッシュ法)は、データをあらかじめ探しやすいところにおいておく方法です。

格納するときも探索するときもハッシュ関数と呼ばれる関数で格納位置を計算するため、1回の探索で特定のデータを見つけ出すことができます。ハッシュ関数を使ってデータを格納する配列などの領域をハッシュ表と呼びます。

ハッシュ法のポイントは以下のとおりです。

ハッシュ表探索法のポイント

オーダー記法で整列法の計算量を表現する

整列法とはデータ列をキー項目の昇順(小さい順)、または、降順(大きい順)に並べ替えることをデータのソート(整列)といいます。

整列法の種類にはバブルソート・選択ソート・挿入ソートなどがあります。

探索法と同様に、情報技術者試験ではそれぞれの整列法がどのような並び替えの方法なのかを問う問題が出題されているので、一つ一つ解説していきます。

バブルソート(交換ソート)の計算量は？

バブルソート(交換ソート)とは隣同士のデータを比較して大小関係が逆ならば交換を行う整列法です。

{ 4.2.5.3.1 } という配列をバブルソートで昇順に並び替えましょう。

4と2の大小関係を比較し、逆だとわかり入れ替えます⇒ { 2.4.5.3.1 }

続いて4と5の大小関係を比較するとそのまま、5と3の比較に移ります。

5と3は大小関係が逆なので交換します ⇒ { 2.4.3.5.1 }

という感じでちまちま並び替えしていき、最終的に{1.2.3.4.5}にする整列法です。

選択ソートの計算量は？

選択ソートとは、一番大きなデータを選んで末尾に置いて行く整列法です。

{ 4.2.5.3.1 }の配列を選択ソートを用いて整列していきましょう。

{ 4.2.5.3.1 }で一番大きな値は5なので5を末尾の1と交換する。 ⇒ { 4.2.1.3.5 }

続いて5は確定したので次に大きいのは4のため4と3を交換する。 ⇒ { 3.2.1.4.5 }

と繰り返していき、最終的に{1.2.3.4.5}とする整列法です。

挿入ソートの計算量は？

挿入ソートとは、データを一個取り出して、置くべき位置に挿入していく整列法です。

同じように{ 4.2.5.3.1 }を挿入ソートを利用して昇順に並べ替えてみましょう。

まずは空の配列{}を用意して、{ 4.2.5.3.1 }の先頭の4を入れます。 ⇒ {4} { 2.5.3.1 }

{ 2.5.3.1 }の先頭2を置くべき位置に挿入します。 ⇒ {2.4}と{ 5.3.1 }

といった順序で1つずつデータ列に挿入していくことで昇順に並び替える整列法です。

その他の整列法：高速ソート法

午前試験では用語のみが出題されるだけなので今回の記事では用語を説明することとします。

高速ソート法には、クイックソート・シェルソート・マージソートなどがあります。

高速ソート法の種類

オーダー記法の暗記ポイントをまとめます

基本情報技術者試験の午前試験ではオーダー記法は覚えておけば時間もかからず解ける問題ばかりのため、計算量を暗記しておくと良いです。

暗記しやすいように、オーダー記法から探索アルゴリズムや整列法へ逆引きもしておきます。

O(1) の意味とは？

O(1)はデータ量がどんなに増えても、処理回数(計算回数だったり探索回数)を常に1回しか行わないという意味です。

探索アルゴリズムでいうとハッシュ法探索の計算量がO(1)です。

O(n) の意味とは？

O(n)はデータ量がnだけ増えると、処理の回数もn増えるという意味です。

探索法や整列法でいうと、線形探索法の計算量が O(n) です。

O(n²)  の意味とは？

O(n²)は、データ量が増えると処理回数はn²ずつ増えるという意味を表しています。
具体的にはソートがこれに当たります。

整列法の挿入ソートの計算量が O(n²) です。

O(log₂n) の意味とは？

O(log₂n)は、データ量がn増えると、計算量が log₂n ずつ増えるというのを表現しています。

log₂n が分かりづらいですが、log₂n = E は 2^E = n と同じ意味です。「2を何乗したらnになるのか」を表しており、そのため、O(√n)と似た意味になります。

探索法や整列法でいうと2分探索法の計算量が O(log₂n)です。
正直logの意味が分かりづらい人もいると思いますが、そういうときは「2分探索法の計算量がlog」とだけ覚えておきましょう。

オーダー記法に関する基本情報技術者試験の過去問題にチャレンジ！

2,000個の相異なる要素が，キーの昇順に整列された表がある。外部から入力したキーによってこの表を2分探索して，該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき，キーの比較回数は最大何回か。

ア. 9
イ. 10
ウ. 11
エ. 12

出典：平成20年秋期 午前問13

整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれ整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

ア. log n
イ. n
ウ. n²
エ. n log²

出典：平成27年春期　午前問6

整列アルゴリズムの一つであるクイックソートの記述として，適切なものはどれか。

ア. 対象集合から基準となる要素を選び，これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで，整列を行う。
イ. 対象集合から最も小さい要素を順次取り出して，整列を行う。
ウ. 対象集合から要素を順次取り出し，それまでに取り出した要素の集合に順序関係を保つよう挿入して，整列を行う。
エ. 隣り合う要素を比較し，逆順であれば交換して，整列を行う。

出典：平成27年秋期　問7

オーダー記法以外！基本情報技術者試験おすすめ学習方法

オーダー記法について学習している人の中には、基本情報技術者試験の学習をしている人も多いのではないでしょうか？

もしも基本情報技術者試験を確実に１発で合格したいのであれば、参考書やオンライン学習サービスを利用するのがおすすめです。

以下のサービスを利用して基本情報技術者試験合格を目指してみてください！

基本情報技術者試験おすすめの学習方法

おすすめ学習方法①：本・参考書

基本情報技術者試験の学習をするなら、マイペースにお金もそんなにかけずに、学習できる「本・参考書」がおすすめです。

僕が実際に中を見て確認した中でおすすめの参考書は以下の通り。

基本情報技術者試験のおすすめ参考書

それぞれに、メリット・デメリットが存在しており、あなたの学習意欲が湧き上がる、よりわかりやすい参考書を選ぶ必要があります。

以下の記事では、それぞれの参考書がどんな人におすすめなのか、メリットやデメリットを紹介しているので、基本情報技術者試験を本や参考書で学習したい人は是非読んでみてください！

基本情報技術者試験に合格するためのオンライン講座おすすめ3選

続きを見る

おすすめの学習方法②：オンライン講座

基本情報技術者試験を、確実に1発で合格したいのであれば、「オンライン講座」を利用して最短最速で学習するのもおすすめです。

オンライン講座で学習することで、わからないところをすぐに質問できるため、挫折するリスクを下げてられますし、学習ペースも管理してくれるので、モチベーションの維持にもなり、より確実に合格を目指せます。

特に以下の3つのサービスがおすすめです。

基本情報技術者試験 おすすめオンライン講座

基本情報技術者試験に独学で合格するためのおすすめ参考書5選

続きを見る

まとめ

今回は基本情報技術者試験の午前試験の対策として、オーダー記法について解説しました。

オーダー記法そのものだけを理解するというよりは、探索アルゴリズムや整列法(ソート法)とセットで理解して置きたい項目です。

基本情報技術者試験でもよく出題されているので、これから資格取得を目指している人はこの記事の内容はしっかり理解しておきましょう。

今後基本情報技術者試験を学習して一発合格を目指しているのであれば、以下の記事で参考書を選ぶか、オンライン講座を利用するのがおすすめです！是非チェックしてみてください。