kantablog Written by Kanta Nakamura

【完全初心者向け】ビック・オー記法(Big O)とは何かを徹底解説してみる【例題あり】

Algorithm PROGRAMMING

悩む人

BigOを知りたい人「ビック・オー記法って聞いたことはあるけど、一体何だろう?初心者でもわかるように、優しく教えてくれる人はいないかなぁ〜」

このような悩みを解決していきます。

本記事の内容

【超初心者向け】ビック・オー記法(Big O)とは何かを解説してみた【例題あり】

この記事を書いている僕は、台湾の大学でコンピューターサイエンスを専攻している現役大学生です。大学でコンピューターサイエンスを学んだり、自分で開発をしたりした経験から、ビック・オー記法の知識がつきました。

本記事は下記のような人におすすめです。

こんな人におすすめ

  • ビックオー記法の概要を理解したい
  • 簡単なコードを見て、時間計算量を推測できるようにしたい
  • アルゴリズムなどのコーディング対策をしたい

本記事を読めば、GAFAMのような世界的大企業の採用面接でも使われる知識であるビック・オー記法の概要を掴み、使えるようになります。

なお、本記事では「世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法」より、一部抜粋しています。

それでは、本題に入ります。

ビック・オー記法(Big O)とは何か

hint

ビック・オー記法とは、アルゴリズムの性能を記述するために使う表記方法のことです。もっと簡単にいうと、「自分の考えたコードが速くなっているか遅くなっているか判断するために使うもの」です。

ビック・オー記法を理解できていないと、書いたコードが速くなっているのか判断ができずに開発時に苦労したり、周りから厳しい評価を受けることになります。

実際にGAFAMのようなBig-tech企業でも、アルゴリズムのコーディング面接があるのは有名ですよね。世界の大企業がそれらを面接に使うということは、つまりビック・オー記法の考え方が大切だということになります。

とても難しそうに思われるかもしれませんが、一度理解してしまえば、一生使える武器にもなるので、コスパも悪くないはずです。

ここからは、ビック・オー記法に必要な知識や考え方をざっと解説してから、例題を解いてビック・オーをマスターしていきます。

時間計算量、空間計算量とは

ビック・オー記法において考えるべき計算量は2つあります。

考慮すべき計算量2つ

  • 時間計算量(どれくらいの時間がかかるか)
  • 空間計算量(どれくらいのメモリを使うか)

それぞれ解説していきます。

時間計算量

時間計算量とは、アルゴリズムが問題を解くにあたって実行しなければならない処理や操作などの回数(ステップ数)のことです。

ステップ数が多ければ多いほど時間計算量は増え、コードが遅くなる、逆に、ステップ数が少ないほど時間計算量は少なくなり、コードも速くなり良いコードになるというわけです。

実例

AさんがBさんにファイルを送らなければならないとします。

今、Aさんが使える送信方法は2つあり、1)電子的に送信する方法、2)飛行機で送信する方法があります。

上記のような場合の実行時間を考えてみてください。
このような場合は次のように考えることができます。

  1. 電子的に送信:ファイルのサイズに対して転送時間は線形に増加すると考えられるので、ファイルのサイズのnとすると、O(n)になる。
  2. 飛行機で送信:ファイルサイズが大きくても小さくても、一定の時間で届けられるので、O(1)となる。

もっとわかりやすいように、グラフで表してみます。

O(n)

上記のように、あなたが普段書いているコードもビック・オー記法によって、考えられる実行時間を表すことができるのです。時間計算量とはビック・オー記法の概念が意味するそのものなのです。

一般的なものでは、小← O(log N)、O(N log N)、O(N)、O(N^2)、O(2^N) →大があります。ここでいうNとは配列などの解きたい問題のサイズを表しています。

空間計算量

アルゴリズムにおいて、時間だけが問題ではありません。アルゴリズムに要求されるメモリの量にも気をつけなければなりません。

例えば、サイズnの配列を作るには、O(n)のメモリを消費します。また、n✖️nの二次元配列のときは、O(n^2)のメモリが必要になるということです。

これはわかりやすいですね😌

定数、影響のない項を捨てる

ビック・オー記法では、実行時間を計算するときには、定数や影響のない項を無視して捨てるというルールがあります。

問題:O(1)、O(N)の2つのコードがあるとしたら、あなたはどちらのコードの方が早いと思いますか?
結論:どちらもあり得る。

なぜなら、ビック・オー記法は単に計算量増加の割合を記述しているに過ぎないからです。このため、実行時間は定数を捨てています。

もし、O(1)のコードは、100個もの手順があり、O(N)が10個の手順しかなかったら、O(N)のコードの方が早いということは十分にあります。繰り返しになりますが、

O(1)、O(N)ってなんだっけ?

  • O(1): 実行時間は一定で変化なし
  • O(N): Nが大きいほど、実行時間も増え、Nが小さいほど、実行時間も少なくなる

よって、O(2N)として表せるアルゴリズムでも、O(N)としているのです。

実例

下記のコードを見てください。

min_and_max_1 min_and_max_2

A(O(N))とB(O(2N))どちらが高速でしょうか?

Aのコードは1つのループで、Bのコードは2つのループです。しかし、Aのコードは1つのループに対して2行分のコードが書かれています。

一見、ループが1つしかないAのコードの方が高速に見えますが、実際はもっと細かいところまで詳細をすべて調べなければどちらが高速かは判断できません。だから、定数を無視するのです。

最初は少し抵抗があるかもしれませんが、勉強しているうちに理解していくと思います。焦らず、ぼちぼち学んでいきましょう。😌

影響の少ない項を捨てる

O(N^2 + N)の場合はどうでしょう?
2番目のNの部分は、厳密にいうと定数ではありません。しかし、このNは実行時間において、影響が少ないため切り捨てることができるのです。

定数部分は切り捨てるという話はしましたので、O(2N^2)はO(N^2)とするのは理解できますよね。
つまり、O(2N^2) = O(N^2 + N^2)O(N^2)と考えることができます。

O(N^2 + N^2)の、2つ目のN^2の項を切り捨てることと同じですから、O(N^2 + N)のNの項は切り捨てられてもいいというわけです。

影響の少ない項の切り捨て例

  • O(N^2 + N)はO(N^2)
  • O(N + logN)はO(N)
  • O(5*2^N + 1000N^100)はO(2^N)

ここで使う考えが、小← O(log N)、O(N log N)、O(N)、O(N^2)、O(2^N) →大です。

上記の例のようにO(N^2)にとってO(N)は影響はないので、O(N^2 + N)O(N^2)と表せるのです。

例外として、O(B + A)のような、AとBの特別な情報がないといけない場合は、実行時間を和の式で表すことになります。

足すべきか掛けるべきか

2つのステップがあるアルゴリズムの実行時間を考えると、ある疑問が生まれます。
それは、

実行時間をどんな時に足して、どんな時に掛けるべきかということ。

下記のコードを見てください。

①実行時間を足す

add_algorithm

②実行時間を掛ける

multiply_algorithm

上記のコードが、足す場合と掛ける場合のいい例です。

①のコードは、Aに対する処理を行ったあとに、Bに対する処理を行っているので、合計の計算量は、O(A + B)になります。

逆に、②のコードは、Aにおける個々の要素について、Bに対する処理を行っているので、合計の計算量は、O(A * B)となります。

まとめると、

  • アルゴリズムが「Aを行い、それが終わったらBを行う」場合は、実行時間の和
  • アルゴリズムが「Aを行うたびに、Bを行う」場合は、実行時間の積

この考え方は、ビック・オーの基本的な考え方なので、理解しておきましょう。

LogN 実行時間とは

次に、O(LogN)について解説します。

例として、二分探索を行う関数について考えてみましょう。
昇順ソート済みの要素数Nの配列から、xを探すとします。もし、配列の中央の要素とxが等しければreturnをし、xが中央の要素より小さければ左を探索、大きければ右を探索します。

logn

合計の実行時間は、Nから1まで(Nを2で繰り返し割ったとき)何ステップかかるかということになります。

  1. N = 16
  2. n = 8 /* 2でわる */
  3. n = 4 /* 2でわる */
  4. n = 2 /* 2でわる */
  5. n = 1 /* 2でわる */

つまり、逆に1から16まで見たときにNを何回掛けるのか考えると:

  1. N = 1 /* 2でかける */
  2. n = 2 /* 2でかける */
  3. n = 4 /* 2でかける */
  4. n = 8 /* 2でかける */
  5. n = 16

式にすると、2^k = Nとなり、このKが実行時間となります。

kを求めるには、log(対数)を使います。

2^4 = 16 -> log2 16 = 4
log2 N = k -> 2^k = N

上記の式より、探索空間の要素数が毎回半分になっていくような問題は、実行時間はおそらくlogNになるといえるのです。

例題で練習してみよう

ここまで、ビック・オー記法の基本的な考え方を解説しました。
けっこうなボリュームでしたよね?けど、これをマスターすれば、一生使える武器になると考えるとコスパが良すぎます😌

ここからは、例題を解きつつ、ビック・オーに慣れていきます。

例題は、「初心者向け】ビック・オー記法のおすすめ例題10選まとめ【解説付き】」こちらからどうぞ。
解説とともにおすすめ例題10選をまとめています。

ここまで、ビック・オー記法の基礎を解説してきましたが、あくまでビック・オーはコードをより早くするための考え方です。

コードを書かなければ、この知識も無駄になってしまうので、ぜひアルゴリズムなどの問題を解いて、知識を深めてみてください。

今回は、これで終わりになります。
ありがとうございました。

参考文献

本記事で使用したコードは、下記の本から一部抜粋しました。僕もアルゴリズムの勉強に使用した良本です。