Big O チートシート: Python の例で説明

Big O Analysis は、アルゴリズムの効率を分析してランク付けするための手法です。

これにより、最も効率的でスケーラブルなアルゴリズムを選択できます。この記事は、Big O Notation について知っておくべきことをすべて説明する Big O Cheat Sheet です。

ビッグオー分析とは何ですか?

Big O Analysis は、アルゴリズムがどの程度拡張できるかを分析するための手法です。具体的には、入力サイズが増加したときにアルゴリズムがどの程度効率的になるかを尋ねます。

効率とは、出力を生成する際にシステム リソースがどの程度適切に使用されるかです。私たちが主に関心のあるリソースは時間とメモリです。

したがって、Big O 分析を実行する際に尋ねる質問は次のとおりです。

1. 入力サイズが大きくなるにつれて、アルゴリズムのメモリ使用量はどのように変化するのでしょうか?
2. 入力サイズが大きくなるにつれて、アルゴリズムが出力を生成するのにかかる時間はどのように変化しますか?

最初の質問に対する答えはアルゴリズムの空間計算量であり、2 番目の質問に対する答えは時間計算量です。両方の質問に対する答えを表現するために、Big O Notation と呼ばれる特別な表記法を使用します。これについては、次に Big O チートシートで説明します。

前提条件

次に進む前に、この Big O Cheat Sheet を最大限に活用するには、代数を少し理解する必要があると言わなければなりません。また、Pythonの例も紹介するので、Pythonを少し理解するのにも役立ちます。コードを記述することはないため、深く理解する必要はありません。

Big O 分析を実行する方法

このセクションでは、Big O 分析を実行する方法について説明します。

Big O Complexity Analysis を実行するときは、アルゴリズムのパフォーマンスが入力データの構造に依存することを覚えておくことが重要です。

たとえば、リスト内のデータがすでに正しい順序で並べ替えられている場合、並べ替えアルゴリズムは最も速く実行されます。これは、アルゴリズムのパフォーマンスにとって最良のシナリオです。一方、同じ並べ替えアルゴリズムでも、データが逆の順序で構造化されている場合は最も遅くなります。それは最悪のシナリオです。

Big O 分析を実行するときは、最悪のシナリオのみを考慮します。

空間の複雑さの分析

この Big O Cheat Sheet では、空間の複雑さの分析を実行する方法を説明することから始めましょう。入力がますます大きくなるにつれて、アルゴリズムが使用する追加メモリがどのようにスケールされるかを検討したいと思います。

たとえば、次の関数は再帰を使用して n から 0 までループします。空間の複雑さは n に正比例します。これは、n が増加すると、呼び出しスタック上の関数呼び出しの数も増加するためです。したがって、空間計算量は O(n) になります。

 def loop_recursively(n):
    if n == -1:
        return
    else:
        print(n)
        loop_recursively(n - 1)

ただし、より良い実装は次のようになります。

 def loop_normally(n):
    count = n
    while count >= 0:
        print(count)
        count =- 1

上記のアルゴリズムでは、追加の変数を 1 つだけ作成し、それをループに使用します。 n がどんどん大きくなっても、追加で使用する変数は 1 つだけです。したがって、アルゴリズムの空間複雑度は一定であり、「O(1)」シンボルで示されます。

上記の 2 つのアルゴリズムの空間複雑さを比較することにより、while ループの方が再帰よりも効率的であると結論付けました。それが Big O Analysis の主な目的であり、より大きな入力でアルゴリズムを実行するときにアルゴリズムがどのように変化するかを分析することです。

時間計算量の分析

時間計算量分析を実行するとき、アルゴリズムにかかる合計時間の増加については気にしません。むしろ、実行される計算ステップの増加を懸念しています。これは、実際の時間は、説明が難しい多くの体系的かつランダムな要因に依存するためです。したがって、計算ステップの増加のみを追跡し、各ステップが等しいと仮定します。

時間計算量分析を説明するために、次の例を考えてみましょう。

各ユーザーが ID と名前を持っているユーザーのリストがあるとします。私たちのタスクは、ID が与えられたときにユーザーの名前を返す関数を実装することです。その方法は次のとおりです。

 users = [
    {'id': 0, 'name': 'Alice'},
    {'id': 1, 'name': 'Bob'},
    {'id': 2, 'name': 'Charlie'},
]

def get_username(id, users):
    for user in users:
        if user['id'] == id:
            return user['name']
    return 'User not found'

get_username(1, users)

ユーザーのリストが与えられると、アルゴリズムはユーザーの配列全体をループして、正しい ID を持つユーザーを見つけます。ユーザーが 3 人の場合、アルゴリズムは 3 回の反復を実行します。 10 ある場合、10 のパフォーマンスを発揮します。

したがって、ステップ数はユーザー数に線形かつ正比例します。したがって、私たちのアルゴリズムは線形時間計算量を持っています。ただし、アルゴリズムを改善することは可能です。

ユーザーをリストに保存する代わりに、辞書に保存したとします。ユーザーを検索するアルゴリズムは次のようになります。

 users = {
    '0': 'Alice',
    '1': 'Bob',
    '2': 'Charlie'
}

def get_username(id, users):
     if id in users:
         return users[id]
     else:
         return 'User not found'

get_username(1, users)

この新しいアルゴリズムを使用して、辞書に 3 人のユーザーが含まれていると仮定します。ユーザー名を取得するには、いくつかの手順を実行します。そして、さらに多くのユーザー、たとえば 10 人がいたとします。ユーザーを取得するために、以前と同じ数のステップを実行します。ユーザーの数が増加しても、ユーザー名を取得する手順の数は一定のままです。

したがって、この新しいアルゴリズムには一定の複雑さが伴います。ユーザーの数は関係ありません。実行される計算ステップ数は同じです。

ビッグオー記法とは何ですか?

前のセクションでは、さまざまなアルゴリズムの Big O の空間と時間の計算量を計算する方法について説明しました。複雑さを説明するために、線形や定数などの言葉を使用しました。複雑さを説明する別の方法は、Big O Notation を使用することです。

Big O Notation は、アルゴリズムの空間または時間の複雑さを表現する方法です。表記は比較的単純です。 O の後に括弧が続きます。括弧内に、特定の複雑さを表す n の関数を記述します。

線形複雑度は n で表されるため、O(n) ( 「O of n」と読みます ) と書きます。一定の複雑さは 1 で表されるため、O(1) と書きます。

さらに複雑な点がありますが、それについては次のセクションで説明します。ただし、一般的に、アルゴリズムの複雑さを記述するには、次の手順に従います。

1. n の数学関数 f(n) を作成してみます。ここで、f(n) は使用されるスペースの量、またはアルゴリズムによって実行される計算ステップ、n は入力サイズです。
2. その関数で最も支配的な項を選択します。さまざまな項の支配性の順序は、最も支配的なものから最も支配的なものまで次のとおりです: 階乗、指数、多項式、二次、線形、線形、対数、および定数。
3. 項から係数を削除します。

その結果が、括弧内で使用する用語になります。

例 :

次の Python 関数を考えてみましょう。

 users = [
    'Alice',
    'Bob',
    'Charlie'
]

def print_users(users):
    number_of_users = len(users)
    print("Total number of users:", number_of_users)

    for i in number_of_users:
        print(i, end=': ')
        print(user)

ここで、アルゴリズムの Big O Time の複雑さを計算します。

まず、アルゴリズムが実行する計算ステップ数を表す数学関数 nf(n) を作成します。 n が入力サイズを表すことを思い出してください。

コードから、この関数は 2 つのステップを実行します。1 つはユーザー数を計算するステップ、もう 1 つはユーザー数を出力するステップです。次に、ユーザーごとに 2 つのステップを実行します。1 つはインデックスの印刷、もう 1 つはユーザーの印刷です。

したがって、実行される計算ステップ数を最もよく表す関数は、f(n) = 2 + 2n として記述できます。ここで、n はユーザーの数です。

ステップ 2 に進み、最も支配的な用語を選択します。 2n は線形項、2 は定数項です。線形は定数よりも支配的なため、線形項である 2n を選択します。

したがって、関数は f(n) = 2n になります。

最後のステップは係数を削除することです。この関数では、係数として 2 を持っています。したがって、それを排除します。そして関数は f(n) = n になります。それが括弧内で使用される用語です。

したがって、アルゴリズムの時間計算量は O(n)、つまり線形計算量です。

さまざまな Big O の複雑さ

Big O チートシートの最後のセクションでは、さまざまな複雑さと関連するグラフを示します。

#1. 絶え間ない

一定の複雑性とは、アルゴリズムが一定量の空間 (空間複雑性解析を実行する場合) または一定数のステップ (時間複雑性解析を実行する場合) を使用することを意味します。入力が増加してもアルゴリズムに追加のスペースや時間が必要ないため、これは最も最適な複雑さです。したがって、非常に拡張性が高いです。

一定の複雑さは O(1) として表されます。ただし、一定の複雑さで実行されるアルゴリズムを作成できるとは限りません。

#2. 対数

対数複雑度は、O(log n) という用語で表されます。コンピューター サイエンスで対数の底が指定されていない場合は、2 であると想定されることに注意することが重要です。

したがって、log n は log ₂ n になります。対数関数は、最初は急速に増加し、その後減速することが知られています。これは、n の数がますます大きくなるにつれて、それらがスケーリングされ、効率的に動作することを意味します。

#3. 線形

線形関数の場合、独立変数が p 倍にスケールされる場合。従属変数は、p と同じ係数でスケーリングされます。

したがって、線形複雑度を持つ関数は、入力サイズと同じ係数で増大します。入力サイズが 2 倍になると、計算ステップ数またはメモリ使用量も増加します。線形複雑さは記号 O(n) で表されます。

#4. 線形演算

O (n * log n) は線形関数を表します。線形関数は、一次関数に対数関数を乗算したものです。したがって、log n が 1 より大きい場合、線形関数は一次関数よりわずかに大きな結果を生成します。これは、n に 1 より大きい数を掛けると増加するためです。

n の値が 2 より大きい場合、log n は 1 より大きくなります (log n は log ₂ n であることを思い出してください)。したがって、n の値が 2 より大きい場合、線形関数は線形関数よりもスケーラビリティが低くなります。ほとんどの場合、n は 2 より大きくなります。したがって、線形関数は一般に対数関数よりもスケーラビリティが低くなります。

#5. 二次関数

二次複雑度は O(n ² ) で表されます。これは、入力サイズが 10 倍に増加すると、実行されるステップ数または使用されるスペースが 10 ² 倍、つまり 100 増加することを意味します。これはあまり拡張性が高くなく、グラフからわかるように、複雑さは急速に増大します。

二次複雑さは、バブル ソートなど、n 回ループし、反復ごとに再度 n 回ループするアルゴリズムで発生します。これは一般に理想的ではありませんが、場合によっては、二次複雑度のアルゴリズムを実装する以外に選択肢がない場合があります。

#6. 多項式

多項式の複雑さを持つアルゴリズムは O(n ^p ) で表されます。ここで、p は定数の整数です。 P は、n が引き上げられる順序を表します。

この複雑さは、ネストされたループが p 個ある場合に発生します。多項式の複雑さと 2 次の複雑さの違いは、2 次の複雑さは 2 のオーダーですが、多項式は 2 より大きい任意の数値を持ちます。

＃7。 指数関数的

指数関数的な複雑さは、多項式の複雑さよりもさらに速く増加します。数学では、指数関数のデフォルト値は定数 e (オイラー数) です。ただし、コンピューター サイエンスでは、指数関数のデフォルト値は 2 です。

指数関数的な複雑さは、記号 O(2 ⁿ ) で表されます。 n が 0 の場合、2 ⁿ は 1 です。しかし、n を 5 に増やすと、2 ^{n は} 32 に膨れ上がります。n を 1 増やすと、前の数値が 2 倍になります。したがって、指数関数はあまり拡張性がありません。

#8. 階乗

階乗複雑度は、記号 O(n!) で表されます。この関数も非常に急速に成長するため、拡張性がありません。

結論

この記事では、Big O 分析とその計算方法について説明しました。また、さまざまな複雑性とそのスケーラビリティについても説明しました。

次に、Python ソート アルゴリズムで Big O 分析を練習してみるとよいでしょう。