Pythonで学ぶアルゴリズム効率。ビッグO表記を理解できる7種類のサンプルコード。

ビッグO表記は、アルゴリズムのパフォーマンスや複雑さを表すための記法です。以下は、各ビッグO表記に対するPythonのサンプルプログラムです。

1. 定数時間 O(1)

定数時間アルゴリズムは、入力サイズに関係なく、常に同じ時間で実行されます。

def constant_time_algorithm(arr):
    return arr[0] if arr else None

# 定数時間
print(constant_time_algorithm([1, 2, 3, 4, 5]))

2. 対数時間 O(log⁡n)

対数時間アルゴリズムは、入力サイズが増えると、実行時間は対数的に増加します。バイナリサーチが良い例です。

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 対数時間
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(sorted_array, 15))

3. 線形時間 O(n)

線形時間アルゴリズムは、入力サイズに比例して実行時間が増加します。線形探索が良い例です。

def linear_search(arr, target):
    for i, item in enumerate(arr):
        if item == target:
            return i
    return -1
 
# 線形時間
unsorted_array = [5, 2, 9, 1, 5, 6]
print(linear_search(unsorted_array, 5))

4. 対数線形時間 O(nlog⁡n)

対数線形時間アルゴリズムは、入力サイズに対して、実行時間がnlog⁡nnlognで増加します。マージソートが良い例です。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    middle = len(arr) // 2
    left = merge_sort(arr[:middle])
    right = merge_sort(arr[middle:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 対数線形時間
unsorted_array = [5, 2, 9, 3, 5, 6]
print(merge_sort(unsorted_array))

5. 多項式時間（２乗） O(n2)

入力サイズに対して、実行時間が二乗で増加します。バブルソートが良い例です。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
 
# 多項式時間（２乗）
unsorted_array = [5, 2, 9, 3, 1, 6]
print(bubble_sort(unsorted_array))

6. 多項式時間（3乗） O(n3)

入力サイズに対して、実行時間が三乗で増加します。行列の直積が良い例です。

def matrix_multiplication(a, b):
    result = [[0] * len(b[0]) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(b)):
                result[i][j] += a[i][k] * b[k][j]
    return result

# 多項式時間（3乗）
matrix_a = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
matrix_b = [
        [9, 8, 7],
        [6, 5, 4],
        [3, 2, 1]
    ]

print(matrix_multiplication(matrix_a, matrix_b))

7. 指数時間 O(2n)

入力サイズに対して、実行時間が指数で増加します。再帰によるフィボナッチ数列計算が良い例です。

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# 指数時間
print(fibonacci(5))

上記のグラフは、各アルゴリズムのビッグO表記に基づいた理論的な実行時間を表しています。縦軸は対数スケールで描画しており、横軸は入力サイズ nです。このグラフから、アルゴリズムの時間複雑度がどのように入力サイズ nに影響するかを視覚的に理解することができます。

ビッグO表記は、アルゴリズムの性能や効率を評価するための重要な工具です。この表記法を理解することで、プログラムのスケーラビリティやパフォーマンスを予測し、最適化することができます。これらの例を通して、ビッグO表記がどのようにアルゴリズムの動作を表現し、評価するかを理解できるでしょう。これにより、読者はより効率的で、最適化されたプログラムを開発できるようになります。

実際に学べたオススメ書籍！

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

プログラマの数学 第2版

なっとく！アルゴリズム

関連記事