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

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

※見たいところをタップするとジャンプできます。

「オーダー記法（O記法）」とは、アルゴリズムがどれくらいの処理時間や回数で動くのかを表すための計算量の表記法です。

たとえば、大量のデータから特定の情報を探す「探索アルゴリズム」や、データを並べ替える「整列アルゴリズム」などでは、処理量がデータの数nに対してどのように増えるのかをO(n) や O(log n) といった形で表します。

基本情報技術者試験などの情報系資格では、「O(n²)はどれ？」「2分探索の計算量は？」といった問題もよく出題されます。

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

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

平成27年春期　問6

これから基本情報技術者試験をはじめとしたIT資格試験を受ける予定があるなら、しっかり理解しておくべき重要なテーマです。

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

オーダー記法(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

基本情報技術者試験などIT資格におすすめの学習方法３選

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

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

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

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

関連記事：【IT登竜門】基本情報技術者一発合格！おすすめの学習方法5選

動画学習（Udemy）｜スマホでスキマ時間にインプット！

動画講座は、図解や実演つきで視覚的に理解できるので、参考書でつまずいた人でもスッと頭に入ります。

Udemyでは、基本情報技術者試験やアルゴリズムの基礎を学べる講座が多数あり、セール時は1,000円台で購入できるのも魅力です。

こんな人は動画学習がおすすめ！

Udemyで基本情報技術者試験合格を目指す！おすすめ講座5選！

続きを見る

オンライン通信講座（スタディング・BizLearnなど）｜体系的に合格を狙う

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

合格までの学習プランが組まれており、スケジュール管理や復習機能も充実。インプットとアウトプットのバランスが良く、試験慣れしやすいからです。

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

こんな人はオンライン通信講座がおすすめ！

特に、基本情報技術者試験をBizLearn(ビズラーン)で学習するのであれば、科目A試験を免除できる制度があるため、学習効率を飛躍的にアップさせることができます。本気で合格を狙っている人はぜひ講座の確認をしてみてください。

BizLearn基本情報講座の評判・口コミは？おすすめポイントまとめ

続きを見る

書籍・参考書｜昔ながらの定番スタイルでじっくり学ぶ

基本情報技術者試験の学習をコストを抑えて学びたい人にとって、参考書は最強コスパの学習手段です。

ただし、図や文章の理解に時間がかかる場合があるため、「まず全体像を動画で掴んでから読む」といった併用も効果的です。

こんな人は参考書の学習がおすすめ

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

もし、おすすめの参考書が知りたいのであれば、下記3冊の中から選んでいただければ間違いなしです！

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

基本情報技術者試験おすすめ参考書10選｜独学で合格するための最新版テキストを厳選！【令和7年度対応】

続きを見る

まとめ

今回は、基本情報技術者試験でも頻出の「オーダー記法（O記法）」について、探索・整列アルゴリズムとセットでわかりやすく解説してきました。

オーダー記法は単なる“暗記項目”ではなく、「どんな処理がどれだけの回数動くか？」考え方の軸を掴むことが大切です。探索アルゴリズムや整列法(ソート法)とセットで理解しておきたいところ。

次にやるべきアクション！