Big O表記法

11.1 Big O表記の定義

Big O表記は数学的な記法であり、アルゴリズムの実行時間やリソース消費の上限を入力データのサイズに依存して記述するために使用されます。これは、アルゴリズムがどの程度スケーラブルであり、データ量が増えるとパフォーマンスがどう変わるかを特定するのに役立ちます。

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

主な表記:

O(1) — 定数時間の複雑さ:

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

O(n) — 線形時間の複雑さ:

• アルゴリズムの実行時間は入力データのサイズに線形に依存します。
• 例: 配列の全ての要素を順にチェックする。

O(log n) — 対数時間の複雑さ:

• アルゴリズムの実行時間は入力データのサイズが増加するにつれて対数的に増加します。
• 例: ソートされた配列での二分探索。

O(n^2) — 二次時間の複雑さ:

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

O(2^n) — 指数時間の複雑さ:

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

注: 二分探索、バブルソート、「ナップサック問題」については次の講義で詳しく学びます。

11.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. 以下の2つの関数を考えてみましょう:

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

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

例 2. 以下の2つの関数を考えてみましょう:

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

両方の関数は二次時間の複雑さを持っており、支配項はn^2です。したがって、他の項や係数の違いにかかわらず、両方の表現はO(n^2)と解釈されます。

11.3. アルゴリズムの比較

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

例 1:

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

nが小さい場合、アルゴリズムAは小さな定数のために速く動作することがありますが、nが大きくなると、アルゴリズムBの方がはるかに速くなります。なぜなら、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要素に対しておおよそ1億回の操作を行います。
• 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に対してどのようにして非現実的になるかを示しています。

1

Опрос

データ構造,  52 уровень,  4 лекция

недоступен

データ構造

データ構造

Открыть