分割統治法

分割統治法#

概要#

分割統治法（Divide and Conquer） は、問題を小さな部分問題に再帰的に分割し、各部分問題を解いてから結果を統合することで元の問題を解くアルゴリズム設計手法である。

3つのステップ#

ステップ

説明

Divide（分割）

問題をより小さな部分問題に分割する

Conquer（統治）

各部分問題を再帰的に解く（十分小さければ直接解く）

Combine（統合）

部分問題の解を統合して元の問題の解を得る

利点と欠点#

利点

  • 再帰的な構造により問題が明確に整理できる

  • 独立した部分問題は並列処理に適している

  • ソートや探索など多くの問題で最適に近い計算量を実現できる

欠点

  • 再帰呼び出しのオーバーヘッドがある

  • スタックフレームの積み重ねによるメモリ使用量が増える

  • 部分問題に重複がある場合は動的計画法の方が効率的

応用例#

例1: マージソート#

配列を半分に分割し、それぞれをソートしてからマージする。

  • Divide: 配列を中央で2つに分割

  • Conquer: 各半分を再帰的にマージソート

  • Combine: ソート済みの2つの配列を1つにマージ

計算量: \(O(n \log n)\)

def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # Divide & Conquer
    right = merge_sort(arr[mid:])

    # Combine
    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


arr = [38, 27, 43, 3, 9, 82, 10]
print(f"入力: {arr}")
print(f"出力: {merge_sort(arr)}")

入力: [38, 27, 43, 3, 9, 82, 10]
出力: [3, 9, 10, 27, 38, 43, 82]

例2: クイックソート#

ピボットを基準に配列を2つに分割し、再帰的にソートする。

  • Divide: ピボットを選び、ピボット未満・以上の2つに分割

  • Conquer: 各部分配列を再帰的にソート

  • Combine: 分割時点で順序が決まるため統合コストなし

計算量: 平均 \(O(n \log n)\)、最悪 \(O(n^2)\)

def quick_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + mid + quick_sort(right)


arr = [38, 27, 43, 3, 9, 82, 10]
print(f"入力: {arr}")
print(f"出力: {quick_sort(arr)}")

入力: [38, 27, 43, 3, 9, 82, 10]
出力: [3, 9, 10, 27, 38, 43, 82]

例3: 二分探索#

ソート済み配列を半分に絞り込みながら目的の値を探す。

  • Divide: 中央値と比較し、探索範囲を左半分か右半分に絞る

  • Conquer: 絞り込んだ範囲で再帰的に探索

  • Combine: 統合不要（見つかった時点で結果が確定）

計算量: \(O(\log n)\)

def binary_search(arr: list[int], target: int, lo: int = 0, hi: int | None = None) -> int:
    """ソート済み配列から target のインデックスを返す。見つからなければ -1。"""
    if hi is None:
        hi = len(arr) - 1

    if lo > hi:
        return -1

    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)


arr = [1, 3, 5, 7, 9, 11, 13, 15]
for target in [7, 6]:
    idx = binary_search(arr, target)
    if idx >= 0:
        print(f"{target} は index {idx} に存在する")
    else:
        print(f"{target} は存在しない")

7 は index 3 に存在する
6 は存在しない

例4: 最大部分配列問題（カダネ法の分割統治版）#

配列中の連続する部分配列のうち、和が最大のものを求める。

部分配列は以下の3つのいずれかに属する。

  1. 左半分のみに含まれる

  2. 右半分のみに含まれる

  3. 中央をまたぐ

中央をまたぐ場合の最大和は \(O(n)\) で求められる。

計算量: \(O(n \log n)\)

def max_crossing_sum(arr: list[int], lo: int, mid: int, hi: int) -> int:
    left_sum = float('-inf')
    total = 0
    for i in range(mid, lo - 1, -1):
        total += arr[i]
        left_sum = max(left_sum, total)

    right_sum = float('-inf')
    total = 0
    for i in range(mid + 1, hi + 1):
        total += arr[i]
        right_sum = max(right_sum, total)

    return left_sum + right_sum


def max_subarray(arr: list[int], lo: int = 0, hi: int | None = None) -> int:
    if hi is None:
        hi = len(arr) - 1

    if lo == hi:
        return arr[lo]

    mid = (lo + hi) // 2
    return max(
        max_subarray(arr, lo, mid),
        max_subarray(arr, mid + 1, hi),
        max_crossing_sum(arr, lo, mid, hi),
    )


arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(f"配列: {arr}")
print(f"最大部分配列の和: {max_subarray(arr)}")  # 期待値: 6 ([4,-1,2,1])

配列: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
最大部分配列の和: 6
Contents