萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 分治法求最大值:演算法原理與實作

分治法是經典演算法策略,將問題分解為子問題遞迴求解再合併。本文以「尋找陣列最大值」為例,詳細解析分治法在 Python 中的實作邏輯、程式碼與複雜度分析。

問題描述

給定一個整數陣列,使用分治法找出最大值。若陣列大小 ≤ 2 可直接比較,否則分解為子問題遞迴求解。

演算法邏輯

  1. 基準情況:陣列長度 ≤ 2,直接比較返回最大值。
  2. 分解:將陣列切分為長度為 2 的子陣列(最後一組可能為 1)。
  3. 解決:對每個子陣列遞迴呼叫求最大值。
  4. 合併:收集所有子陣列的最大值,形成新陣列遞迴處理,直到剩單一值。

Python 實作


# -*- 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]

  1. 切分:[[12,2], [23,45], [67,3], [2,4], [45,63], [24,23]]
  2. 子問題最大值:[12, 45, 67, 4, 63, 24]
  3. 遞迴切分:[[12,45], [67,4], [63,24]]
  4. 子問題最大值:[45, 67, 63]
  5. 遞迴切分:[[45,67], [63]]
  6. 子問題最大值:[67, 63]
  7. 最終比較:max(67, 63) = 67

複雜度分析

  • 時間複雜度:O(n)。每層處理所有元素一次,共 log₂n 層,但每層元素總數遞減,總比較次數 ≈ n - 1,同線性掃描。
  • 空間複雜度:O(log n) 遞迴呼叫堆疊 + O(n) 中間陣列。可優化為原地分治降至 O(log n)。

優化版:原地分治 (索引範圍)


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),更適合大規模資料。

教學意義

雖然尋找最大值用線性掃描更簡單高效,但此例完美展示分治法「分解-解決-合併」的核心模式,為理解合併排序、快速排序、最近點對等複雜分治演算法奠定基礎。

copyright © 萬盛學電腦網 all rights reserved