Big O記法: 基本コンセプト

2.1 Big O記法の定義

Big O記法は数学的な記法で、アルゴリズムの実行時間や資源消費の 上限を入力データのサイズに基づいて記述します。これは、どのように アルゴリズムがスケールして、データ量の増加に伴ってパフォーマンスが どう変わるかを判断するのに役立ちます。

Big O記法はアルゴリズムのもっとも重要な側面に焦点を当てていて、 定数やあまり重要でない項目は無視して、アルゴリズムの長期的な 挙動に集中できます。

主な記法:

O(1) — 定数時間:

• アルゴリズムの実行時間は入力データのサイズに依存しません。
• 例: 配列の要素へのインデックスによるアクセス。

O(n) — 線形時間:

• アルゴリズムの実行時間は入力データのサイズに線形に依存します。
• 例: 配列の全要素の単純なループ。

O(log n) — 対数時間:

• アルゴリズムの実行時間は、入力データのサイズの増加に伴い対数的に増加します。
• 例: ソートされた配列でのバイナリサーチ。

O(n^2) — 二次時間:

• アルゴリズムの実行時間は入力データのサイズの二乗に依存します。
• 例: バブルソート、挿入ソート。

O(2^n) — 指数時間:

• アルゴリズムの実行時間は入力データのサイズの指数に依存します。
• 例: ナップサック問題の全探索。

2.2 Big O記法の解釈

どうやってBig O記法を解釈して使うの?

定数や重要でない項目の無視:

Big Oは関数の成長オーダーを記述しますが、定数や重要でない 項目は無視します。たとえば、O(2n)とO(3n)はO(n)として解釈されます。

アルゴリズムの比較:

Big Oはアルゴリズムを漸近的な効率で比べることができます。 例えば、O(n log n)のアルゴリズムは非常に大きなデータ量に対して O(n^2)のアルゴリズムより効率的です。

最悪の場合の解析:

Big Oは通常、アルゴリズムの最悪の実行時間を解析するために使われ、 その最大の複雑さを評価することができます。

定数の無視

定数や重要でない項目の無視

例 1:

二つの関数を考えます:

• f(n) = 3n + 2
• g(n) = 5n + 1

両方の関数は線形時間複雑度を持っており、各関数の主な項目はnです。 したがって、係数や他の項目の違いにも関わらず、両方の関数は O(n)として解釈されます。

例 2:

二つの関数を考えます:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

両方の関数は二次時間複雑度を持っており、主な項目はn^2です。 他の項目や係数の違いにも関わらず、両方の式はO(n^2)として解釈されます。

2.3. アルゴリズムの比較

1. 非常に大きなデータ量でのアルゴリズムの比較

例 1:

• アルゴリズムAは時間複雑度O(n^2)を持っています。
• アルゴリズムBは時間複雑度O(n log n)を持っています。

小さいnの値では、アルゴリズムAはより小さい定数値のため速く動作するかもしれませんが、大きいnの値になると、アルゴリズムBははるかに速くなります。 なぜなら、その成長は対数的であって、二次的ではないからです。

例 2:

• アルゴリズムXは時間複雑度O(n)を持っています。
• アルゴリズムYは時間複雑度O(1)を持っています。

アルゴリズムYは常に速く、それはなぜなら時間複雑度O(1)が 入力データのサイズに依存しないことを意味するからです。

2. 最悪の場合の解析

例 1:

バブルソートのアルゴリズムは最悪の場合、時間複雑度O(n^2)を持っています。 これは、配列が逆順にソートされているときに、各要素が他のすべての要素と比較され そして交換される必要があることを意味します。

例 2:

バイナリサーチは最悪の場合、時間複雑度O(log n)を持っています。 これは、最悪の場合でも、要素を見つけるために必要なステップ数が配列のサイズに対して 対数的に依存するので、非常に効率的であることを意味します。

3. パフォーマンスとスケーラビリティへの影響

例 1:

データを処理するための2つのアルゴリズムがあり、一つは時間複雑度O(n^2)を持ち、 もう一つはO(n log n)を持っていて、データのサイズを1000要素から 10,000要素に増やすと、パフォーマンスの違いが著しく目立ちます。

• アルゴリズムO(n^2)は、10,000要素に対して約100,000,000回の操作を行います。
• アルゴリズムO(n log n)は、10,000要素に対して約40,000回の操作を行います。

例 2:

O(2^n)で動作するアルゴリズムを考えると、入力データのサイズを10から 20要素に増やすと、操作数が指数関数的に増加します。

• n = 10の場合: 2^10 = 1024操作。
• n = 20の場合: 2^20 = 1,048,576操作。

これは、指数時間複雑度が大きな値のnに対して急速に非実用的になることを示しています。