分治法是經典演算法策略,將問題分解為子問題遞迴求解再合併。本文以「尋找陣列最大值」為例,詳細解析分治法在 Python 中的實作邏輯、程式碼與複雜度分析。
給定一個整數陣列,使用分治法找出最大值。若陣列大小 ≤ 2 可直接比較,否則分解為子問題遞迴求解。
# -*- coding: utf-8 -*-
import random
def max_value(pair):
"""解決基準問題:返回兩個元素中的最大值"""
return max(pair)
def solve(arr):
"""分治遞迴主函數"""
if len(arr) <= 2:
print(max_value(arr))
return
# 分解:切分為長度 2 的子陣列
sub_arrays = [arr[i:i+2] for i in range(0, len(arr), 2)]
# 解決子問題並收集結果
max_list = [max_value(sub) for sub in sub_arrays]
# 合併:遞迴處理最大值陣列
solve(max_list)
if __name__ == "__main__":
test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
solve(test_list)
輸入:[12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
[[12,2], [23,45], [67,3], [2,4], [45,63], [24,23]][12, 45, 67, 4, 63, 24][[12,45], [67,4], [63,24]][45, 67, 63][[45,67], [63]][67, 63]max(67, 63) = 67
def max_divide_conquer(arr, left, right):
if left == right:
return arr[left]
if right == left + 1:
return max(arr[left], arr[right])
mid = (left + right) // 2
left_max = max_divide_conquer(arr, left, mid)
right_max = max_divide_conquer(arr, mid + 1, right)
return max(left_max, right_max)
# 呼叫
arr = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
print(max_divide_conquer(arr, 0, len(arr) - 1)) # 67
此版本空間複雜度 O(log n),更適合大規模資料。
雖然尋找最大值用線性掃描更簡單高效,但此例完美展示分治法「分解-解決-合併」的核心模式,為理解合併排序、快速排序、最近點對等複雜分治演算法奠定基礎。