分治算法

分治算法，先「分」后「治」，核心思想是将原问题划分为若干个规模较小且相互独立的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。

最优子结构性质（Optimal Substructure）：如果原问题的解可以通过合并子问题的解得到，且子问题的解可以独立地计算，那么问题具有最优子结构性质。
时间复杂度：分治算法的时间复杂度通常可以通过递归的深度和每层的操作复杂度来分析。常见的分治算法的时间复杂度一般为$O(nlogn)$。
示例算法：常见的应用了分治思想的算法有归并排序（Merge Sort）、快速排序（Quick Sort）、Karatsuba乘法算法（用于大整数乘法）等。

算法框架

归并排序（Merge Sort）：归并排序的思想是通过递归地将数组划分为两个子数组，直到子数组的长度为1或0，然后再逐步合并两个有序子数组。合并时，比较两个子数组的首元素，将较小的元素放入合并数组中，直到其中一个子数组的元素全部合并完成，然后将另一个子数组的剩余元素直接添加到合并数组的末尾。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 划分数组为两个子数组
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 递归地对子数组进行排序
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 合并两个有序子数组
    return merge(left, right)

def merge(left, right):
    merged = []
    i, j = 0, 0
    
    # 比较两个子数组的元素，并按顺序合并
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    
    # 将剩余的元素添加到合并数组中
    while i < len(left):
        merged.append(left[i])
        i += 1
    while j < len(right):
        merged.append(right[j])
        j += 1
    
    return merged

快速排序（Quick Sort）：选择一个基准元素，通过将数组划分为左右两个部分，使得左侧部分的元素都小于等于基准元素，右侧部分的元素都大于等于基准元素，然后递归地对左右两部分进行排序，最终得到完全有序的数组。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 选择基准元素
    pivot = arr[0]
    left = []
    right = []
    
    # 将数组中小于基准元素的放入左侧，大于基准元素的放入右侧
    for i in range(1, len(arr)):
        if arr[i] <= pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    
    # 递归地对左右两部分进行排序
    left = quick_sort(left)
    right = quick_sort(right)
    
    # 合并左右两部分和基准元素
    return left + [pivot] + right