Python の例を使用した Big O 記法とアルゴリズム分析

概要

通常、コンピュータ プログラムを使用して問題を解決するには、複数の方法があります。 たとえば、配列内のアイテムを並べ替える方法はいくつかあります。 マージソート, バブルソート, 挿入ソート、 等々。 これらのアルゴリズムにはそれぞれ長所と短所があり、開発者の仕事はそれらを比較検討して、あらゆるユースケースで使用する最適なアルゴリズムを選択できるようにすることです。 言い換えれば、主な問題は、問題に対して複数のソリューションが存在する場合、特定の問題を解決するためにどのアルゴリズムを使用するかです。

アルゴリズム分析 さまざまなアルゴリズムの複雑さを分析し、目前の問題を解決するための最も効率的なアルゴリズムを見つけることを指します。 Big-O表記 アルゴリズムの複雑さを説明するために使用される統計的尺度です。

このガイドでは、最初にアルゴリズム分析について簡単に説明し、次に Big-O 表記について詳しく見ていきます。 さまざまな Python 関数の助けを借りて、アルゴリズムの複雑さを見つけるために Big-O 表記法をどのように使用できるかを見ていきます。

アルゴリズム分析が重要な理由

アルゴリズム分析が重要である理由を理解するために、簡単な例を使用します。 マネージャーが XNUMX 人の従業員に、ユーザーが入力した数値の階乗を計算するアルゴリズムを Python で設計するタスクを与えたとします。 最初の従業員が開発したアルゴリズムは次のようになります。

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

このアルゴリズムは単純に整数を引数として取ることに注意してください。 内部 fact() 関数という名前の変数 product に初期化されます 1. からループが実行されます 1 〜へ n 各反復中に、 product ループによって繰り返される数が乗算され、結果が product 再び変数。 ループの実行後、 product 変数には階乗が含まれます。

同様に、XNUMX 番目の従業員も、数値の階乗を計算するアルゴリズムを開発しました。 XNUMX 番目の従業員は、再帰関数を使用して階乗を計算しました。 n:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

管理者は、使用するアルゴリズムを決定する必要があります。 そのために、彼らはどちらのアルゴリズムがより速く実行されるかを選択することにしました。 これを行う XNUMX つの方法は、同じ入力でコードを実行するのに必要な時間を見つけることです。

Jupyter ノートブックでは、 %timeit リテラルの後に関数呼び出しを続けて、関数の実行にかかった時間を調べます。

%timeit fact(50)

これは私たちに与えるでしょう：

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

出力は、アルゴリズムが取ることを示しています 9のマイクロ秒 (プラス/マイナス 45 ナノ秒) ループあたり。

同様に、XNUMX 番目のアプローチの実行にかかる時間を計算できます。

%timeit fact2(50)

これは次の結果になります：

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

再帰を含む XNUMX 番目のアルゴリズムは、 15のマイクロ秒 (プラス/マイナス 427 ナノ秒)。

実行時間は、再帰を含む XNUMX 番目のアルゴリズムと比較して、最初のアルゴリズムが高速であることを示しています。 大規模な入力を処理する場合、パフォーマンスの違いはより重要になる可能性があります。

ただし、実行時間はハードウェアに依存するため、アルゴリズムの複雑さを測定するための適切な指標ではありません。 アルゴリズムのより客観的な複雑さ分析メトリックが必要です。 これは、 ビッグオー表記 遊びに来る。

Big-O表記によるアルゴリズム分析

Big-O 表記は、アルゴリズムへの入力とアルゴリズムの実行に必要なステップとの関係を表します。 これは、大きな「O」の後に開き括弧と閉じ括弧が続くことで示されます。 括弧内には、入力とアルゴリズムによって実行されるステップとの関係が「n」を使用して示されます。

重要なポイントは、Big-O は興味がないということです。 特定の 次のようなアルゴリズムを実行するインスタンス fact(50)、むしろ、どれだけうまくいくか 階段 入力の増加が与えられます。 これは、具体的なインスタンスの具体的な時間よりもはるかに優れた評価指標です!

たとえば、 線形関係 入力と、アルゴリズムが実行を完了するために実行するステップとの間で、使用される Big-O 表記は次のようになります。 O（N）. 同様に、 Big-O 記法は 二次関数 is O（n²）.

直感を構築するには：

• O（N）： で n=1、 1 ステップ実行されます。 で n=10、10ステップが実行されます。
• O（n²）： で n=1、 1 ステップ実行されます。 で n=10、100ステップが実行されます。

At n=1、これら XNUMX つは同じように実行されます。 これは、入力とその入力を処理するためのステップ数との関係を観察することが、具体的な入力で関数を評価するよりも優れているもう XNUMX つの理由です。

以下は、最も一般的な Big-O 関数の一部です。

名前	ビッグオー
定数	O（c）
線形	O（N）
二次	O（n²）
キュービック	O(nXNUMX)
指数関数	お(2ⁿ)
対数	O（log（n））
対数線形	O（nlog（n））

これらの関数を視覚化して比較できます。

一般的に言えば、線形よりも悪いものは、悪い複雑さ (つまり、非効率的) と見なされ、可能であれば避けるべきです。 線形の複雑さは問題なく、通常は必要悪です。 対数は良いです。 コンスタントすごい！

Big-O がどのように計算されるかを理解するために、定数、線形、および XNUMX 次の複雑さの例をいくつか見てみましょう。

一定の複雑性 – O(C)

入力の数に関係なく、アルゴリズムの実行を完了するために必要なステップが一定のままである場合、アルゴリズムの複雑さは一定であると言われます。 一定の複雑さは、 O（c） コラボレー c 任意の定数にすることができます。

リストの最初の項目の二乗を見つけ、それを画面に表示する単純なアルゴリズムを Python で書きましょう。

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

上記のスクリプトでは、 入力サイズに関係なく、または入力リスト内の項目数 itemsの場合、アルゴリズムは次の 2 つのステップのみを実行します。

1. 最初の要素の二乗を見つける
2. 結果を画面に出力します。

したがって、複雑さは一定のままです。

さまざまなサイズのライン プロットを描画すると、 items X 軸に入力、Y 軸にステップ数を入力すると、直線が得られます。 これを視覚化するのに役立つ短いスクリプトを作成しましょう。 入力の数に関係なく、実行されるステップの数は同じままです。

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

線形の複雑さ – O（N）

アルゴリズムの実行を完了するために必要なステップが入力の数に比例して増加または減少する場合、アルゴリズムの複雑さは線形であると言われます。 線形複雑度は、 O（N）.

この例では、リスト内のすべての項目をコンソールに表示する簡単なプログラムを書きましょう。

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

の複雑さ linear_algo() forループの反復回数が 入力のサイズに等しい items 配列. たとえば、 items リストでは、for ループが 4 回実行されます。

x 軸に入力数、y 軸にステップ数を使用して、線形複雑度アルゴリズムのプロットを簡単に作成してみましょう。

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

これは次の結果になります：

注意すべき重要なことは、入力が大きい場合、定数は値を失う傾向があるということです。 これが、通常 Big-O 表記から定数を削除し、O(2n) などの式を通常 O(n) に短縮する理由です。 O(2n) と O(n) はどちらも線形です。具体的な値ではなく、線形関係が重要です。 たとえば、 linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

入力を反復する XNUMX つの for ループがあります。 items リスト。 したがって、アルゴリズムの複雑さは次のようになります。 O（2n）ただし、入力リストに無限の項目がある場合、無限の XNUMX 倍は依然として無限に等しいです。 定数は無視できます 2 （最終的には重要ではないため）、アルゴリズムの複雑さは残ります O（N）.

X 軸に入力を、Y 軸にステップ数をプロットして、この新しいアルゴリズムを視覚化してみましょう。

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

上記のスクリプトでは、 y=2nただし、出力は線形であり、次のようになります。

二次複雑度 – O（n²）

アルゴリズムの複雑さは、アルゴリズムを実行するために必要なステップが入力の項目数の XNUMX 次関数である場合、XNUMX 次であると言われます。 二次複雑度は次のように表されます。 O（n²）:

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

入力リストのすべての項目を反復処理する外側のループと、入力リストのすべての項目を反復処理するネストされた内側のループがあります。 実行されるステップの総数は n*n です。ここで、n は入力配列内の項目の数です。

次のグラフは、XNUMX 次複雑度のアルゴリズムのステップに対する入力数をプロットしたものです。

対数複雑度 – O（logn）

一部のアルゴリズムは、次のような対数の複雑さを実現します。 バイナリ検索. 二分探索は配列内の要素を検索します。 真ん中 配列の、要素が含まれていない半分を剪定します。 残りの半分についてもこれを繰り返し、要素が見つかるまで同じ手順を続けます。 各ステップでは、 半分 配列内の要素の数。

これには、配列をソートする必要があり、データについて (ソートされているなどの) 仮定を立てる必要があります。

入力データについて推測できる場合は、アルゴリズムの複雑さを軽減する手順を実行できます。 対数の複雑さは、高度にスケーリングされた入力でも優れたパフォーマンスを達成するため、望ましいものです。

複雑な関数の複雑さを見つける?

前の例では、入力に対してかなり単純な関数を使用しました。 しかし、入力に対して (複数の) 他の関数を呼び出す関数の Big-O をどのように計算すればよいでしょうか?

見てみましょう：

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

上記のスクリプトでは、いくつかのタスクが実行されています。まず、コンソールに文字列が 5 回表示されます。 print 声明。 次に、入力リストを画面に XNUMX 回出力し、最後に別の文字列をコンソールに XNUMX 回出力します。 このようなアルゴリズムの複雑さを見つけるには、アルゴリズム コードを部分に分解し、個々の部分の複雑さを見つけようとする必要があります。 各ピースの複雑さを書き留めます。

最初のセクションには次のものがあります。

for i in range(5):
	print("Python is awesome")

この部分の複雑さは O（5） 入力に関係なく、このコードでは XNUMX つの一定のステップが実行されているためです。

次に、次のようになります。

for item in items:
	print(item)

上記のコードの複雑さは次のとおりです。 O（N）. 同様に、次のコードの複雑さも O（N）:

for item in items:
	print(item)

最後に、次のコードでは、文字列が XNUMX 回出力されるため、複雑さは次のようになります。 O（3）:

print("Big O")
print("Big O")
print("Big O")

全体的な複雑さを見つけるには、これらの個々の複雑さを単純に追加する必要があります。

O(5) + O(n) + O(n) + O(3)

上記を単純化すると、次のようになります。

O(8) + O(2n) = O(8+2n)

入力 (この場合は長さ n) が非常に大きくなると、定数は重要ではなくなります。つまり、無限大の XNUMX 倍または半分がまだ無限大のままです。 したがって、定数は無視できます。 アルゴリズムの最終的な複雑さは O（N）!

最悪の場合と最良の場合の複雑さ

通常、誰かがアルゴリズムの複雑さについて尋ねるとき、彼らは最悪の場合の複雑さ (Big-O) に関心があります。 場合によっては、ベスト ケースの複雑性 (ビッグ オメガ) にも関心がある場合があります。

これらの関係を理解するために、別のコードを見てみましょう。

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

上記のスクリプトには、数値と数値のリストを入力として受け取る関数があります。 渡された数値が数値のリストにある場合は true を返し、そうでない場合は戻ります。 None. リストで 2 を検索すると、最初の比較で見つかります。 これは、検索されたアイテムが最初に検索されたインデックスで見つかるという点で、アルゴリズムの最良のケースの複雑さです。 最良のケースの複雑さこの場合、 O（1）. 一方、10個検索すると、最後に検索したインデックスで見つかります。 アルゴリズムはリスト内のすべてのアイテムを検索する必要があるため、 最悪の場合の複雑さ になる O（N）.

ベスト ケースとワースト ケースの複雑さに加えて、計算することもできます。 平均的な複雑さ アルゴリズムの (Big-Theta) は、「ランダムな入力が与えられた場合、アルゴリズムの予想される時間の複雑さ」を教えてくれますか?

スペースの複雑さ

アルゴリズムの実行を完了するために必要なステップ数をカウントする時間計算量に加えて、次のこともわかります。 スペースの複雑さ これは、プログラムの実行中にメモリに割り当てる必要があるスペースの量を指します。

次の例を見てください。

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

　 return_squares() 関数は整数のリストを受け入れ、対応する正方形のリストを返します。 アルゴリズムは、入力リストと同じ数のアイテムにメモリを割り当てる必要があります。 したがって、アルゴリズムの空間複雑度は次のようになります。 O（N）.

まとめ

Big-O 表記は、アルゴリズムの複雑さを測定するために使用される標準的なメトリックです。 このガイドでは、Big-O 記法とは何か、またそれを使用してさまざまなアルゴリズムの複雑さを測定する方法について説明しました。 また、さまざまな Python の例を使用して、さまざまなタイプの Big-O 関数についても調べました。 最後に、スペースの複雑さとともに、最悪の場合と最良の場合の複雑さを簡単に確認しました。