Python算法基础篇之分治算法原理与实战

一、什么是分治算法？

分治算法（Divide and Conquer）是一种重要的算法设计策略，核心思想是：将一个大问题分解为若干个相似的子问题，递归地解决这些子问题，最后将子问题的解合并，得到原问题的解。

1.1 三步走框架

分治算法遵循固定的三步框架：

1.2 分治 vs 递归

很多人容易混淆分治和递归，它们的关系是：

• 递归是一种编程技巧（函数调用自身）
• 分治是一种算法思想（大问题拆小问题）
• 分治通常用递归实现，但递归不一定都是分治

分治算法的递归必须有终止条件：当问题规模小到可以直接求解时，不再继续分解。

1.3 适用场景

分治算法适用于具有以下特征的问题：

• 问题可以分解为若干个相似的子问题
• 子问题的解可以合并为原问题的解
• 子问题之间相互独立（无重叠）
• 问题存在基准情况（可以直接求解的最小规模）

二、经典案例一：归并排序（Merge Sort）

归并排序是分治算法最经典的应用之一，完美体现了"分解-解决-合并"的思想。

2.1 算法原理

如上图所示，归并排序的过程分为两个阶段：

• 分解阶段（分）：将数组不断对半拆分，直到每个子数组只剩1个元素
• 合并阶段（治）：将相邻的有序子数组合并成一个更大的有序数组

2.2 代码实现

defmerge_sort(arr):iflen(arr)<=1:returnarr mid=len(arr)//2left_half=arr[:mid]right_half=arr[mid:]left_sorted=merge_sort(left_half)right_sorted=merge_sort(right_half)returnmerge(left_sorted,right_sorted)defmerge(left,right):result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresultprint("="*50)print("【示例1】归并排序")print("="*50)test_arr=[38,27,43,3,9,82,10]print(f"原始数组:{test_arr}")print(f"排序结果:{merge_sort(test_arr)}")

运行结果：

================================================== 【示例1】归并排序 ================================================== 原始数组: [38, 27, 43, 3, 9, 82, 10] 排序结果: [3, 9, 10, 27, 38, 43, 82]

2.3 归并排序的递归树

[38, 27, 43, 3, 9, 82, 10] / \ [38, 27, 43] [3, 9, 82, 10] / \ / \ [38] [27, 43] [3, 9] [82, 10] / \ / \ / \ [27] [43] [3] [9] [82] [10] 合并->[27,43] 合并->[3,9] 合并->[10,82] 合并->[27, 38, 43] 合并->[3, 9, 10, 82] 合并->[3, 9, 10, 27, 38, 43, 82]

三、经典案例二：快速排序（Quick Sort）

快速排序也是分治算法的经典应用，与归并排序不同的是，快速排序的重点在"分解"阶段。

3.1 算法原理

快速排序的核心步骤：

1. 选择基准（Pivot）：从数组中选择一个元素作为基准
2. 分区（Partition）：将数组分为两部分，左边都小于基准，右边都大于基准
3. 递归排序：对左右两部分递归进行快速排序

3.2 代码实现

defquick_sort(arr):iflen(arr)<=1:returnarr pivot=arr[0]less=[xforxinarr[1:]ifx<=pivot]greater=[xforxinarr[1:]ifx>pivot]returnquick_sort(less)+[pivot]+quick_sort(greater)defquick_sort_inplace(arr,low=0,high=None):ifhighisNone:high=len(arr)-1iflow<high:pivot_index=partition(arr,low,high)quick_sort_inplace(arr,low,pivot_index-1)quick_sort_inplace(arr,pivot_index+1,high)returnarrdefpartition(arr,low,high):pivot=arr[high]i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]returni+1print("\n"+"="*50)print("【示例2】快速排序")print("="*50)test_arr2=[64,34,25,12,22,11,90]print(f"原始数组:{test_arr2}")print(f"简单版本结果:{quick_sort(test_arr2[:])}")arr_inplace=test_arr2[:]quick_sort_inplace(arr_inplace)print(f"原地版本结果:{arr_inplace}")

运行结果：

================================================== 【示例2】快速排序 ================================================== 原始数组: [64, 34, 25, 12, 22, 11, 90] 简单版本结果: [11, 12, 22, 25, 34, 64, 90] 原地版本结果: [11, 12, 22, 25, 34, 64, 90]

3.3 归并排序 vs 快速排序

四、经典案例三：最大子数组问题

最大子数组问题（Maximum Subarray Problem）是找出数组中连续子数组的最大和。

4.1 问题描述

给定一个整数数组，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。

例如：[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大子数组是[4, -1, 2, 1]，和为6。

4.2 分治解法思路

将数组从中间分成两半，最大子数组只可能有三种情况：

1. 完全在左半部分：递归求解左半部分
2. 完全在右半部分：递归求解右半部分
3. 跨越中点：从中间向两边扩展，找最大和

最终结果是这三种情况的最大值。

4.3 代码实现

defmax_subarray_divide_conquer(arr,low,high):iflow==high:returnlow,high,arr[low]mid=(low+high)//2left_low,left_high,left_sum=max_subarray_divide_conquer(arr,low,mid)right_low,right_high,right_sum=max_subarray_divide_conquer(arr,mid+1,high)cross_low,cross_high,cross_sum=max_crossing_subarray(arr,low,mid,high)ifleft_sum>=right_sumandleft_sum>=cross_sum:returnleft_low,left_high,left_sumelifright_sum>=left_sumandright_sum>=cross_sum:returnright_low,right_high,right_sumelse:returncross_low,cross_high,cross_sumdefmax_crossing_subarray(arr,low,mid,high):left_sum=float('-inf')sum_val=0max_left=midforiinrange(mid,low-1,-1):sum_val+=arr[i]ifsum_val>left_sum:left_sum=sum_val max_left=i right_sum=float('-inf')sum_val=0max_right=mid+1forjinrange(mid+1,high+1):sum_val+=arr[j]ifsum_val>right_sum:right_sum=sum_val max_right=jreturnmax_left,max_right,left_sum+right_sumprint("\n"+"="*50)print("【示例3】最大子数组问题（分治法）")print("="*50)test_arr3=[-2,1,-3,4,-1,2,1,-5,4]print(f"原始数组:{test_arr3}")start,end,max_sum=max_subarray_divide_conquer(test_arr3,0,len(test_arr3)-1)print(f"最大子数组:{test_arr3[start:end+1]}")print(f"最大和:{max_sum}")print(f"起始索引:{start}, 结束索引:{end}")

运行结果：

================================================== 【示例3】最大子数组问题（分治法） ================================================== 原始数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4] 最大子数组: [4, -1, 2, 1] 最大和: 6 起始索引: 3, 结束索引: 6

4.4 更优解法：Kadane算法

defmax_subarray_kadane(arr):max_sum=current_sum=arr[0]start=end=temp_start=0foriinrange(1,len(arr)):ifcurrent_sum<0:current_sum=arr[i]temp_start=ielse:current_sum+=arr[i]ifcurrent_sum>max_sum:max_sum=current_sum start=temp_start end=ireturnstart,end,max_sum start_k,end_k,max_sum_k=max_subarray_kadane(test_arr3)print(f"\nKadane算法结果:")print(f"最大子数组:{test_arr3[start_k:end_k+1]}")print(f"最大和:{max_sum_k}")

五、经典案例四：汉诺塔问题

汉诺塔（Tower of Hanoi）是分治算法最经典的问题之一。

5.1 问题描述

有三根柱子（A、B、C），A柱上有n个大小不一的圆盘，大盘在下，小盘在上。要求将所有圆盘从A柱移动到C柱，规则：

1. 每次只能移动一个圆盘
2. 大盘不能放在小盘上面
3. 可以借助B柱作为辅助
   

5.2 分治思路

将n个圆盘的问题分解为三个子问题：

1. 将上面n-1个圆盘从A柱借助C柱移动到B柱
2. 将最底下的第n个圆盘从A柱直接移动到C柱
3. 将B柱上的n-1个圆盘借助A柱移动到C柱

5.3 代码实现

defhanoi(n,source='A',target='C',auxiliary='B'):ifn==1:print(f"Move disk 1 from{source}to{target}")return1moves=0moves+=hanoi(n-1,source,auxiliary,target)print(f"Move disk{n}from{source}to{target}")moves+=1moves+=hanoi(n-1,auxiliary,target,source)returnmovesprint("\n"+"="*50)print("【示例4】汉诺塔问题")print("="*50)n=3print(f"\n{n}个圆盘的移动步骤：")total_moves=hanoi(n)print(f"\n总移动次数:{total_moves}")print(f"理论最小次数:{2**n-1}")

运行结果：

================================================== 【示例4】汉诺塔问题 ================================================== 3个圆盘的移动步骤： Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C 总移动次数: 7 理论最小次数: 7

5.4 汉诺塔的数学规律

如果每秒移动一次，64个圆盘需要约5850亿年才能移完！

六、进阶应用：分治求幂

6.1 问题描述

计算 x 的 n 次幂（x^n），如何高效计算？

6.2 代码实现

defpower(x,n):ifn==0:return1half=power(x,n//2)ifn%2==0:returnhalf*halfelse:returnx*half*halfdefpower_iterative(x,n):result=1base=xwhilen>0:ifn%2==1:result*=base base*=base n//=2returnresultprint("\n"+"="*50)print("【示例5】分治法快速求幂")print("="*50)x,n=2,10print(f"计算{x}^{n}")print(f"递归分治结果:{power(x,n)}")print(f"迭代快速幂结果:{power_iterative(x,n)}")print(f"内置函数结果:{pow(x,n)}")print(f"\n计算 2^100:")print(f"分治结果:{power(2,100)}")

运行结果：

================================================== 【示例5】分治法快速求幂 ================================================== 计算 2^10 递归分治结果: 1024 迭代快速幂结果: 1024 内置函数结果: 1024 计算 2^100: 分治结果: 1267650600228229401496703205376

七、分治算法的时间复杂度分析

7.1 主定理（Master Theorem）

分治算法的时间复杂度通常可以用主定理来计算：

如果递归式为：T(n) = a * T(n/b) + f(n)

其中：

• a >= 1：子问题的数量
• b > 1：问题规模的缩小因子
• f(n)：分解和合并的代价

则有三种情况：

7.2 经典算法的时间复杂度

八、分治算法的常见陷阱

8.1 陷阱1：忘记基准情况

# 错误：没有基准情况，导致无限递归defbad_divide(arr):mid=len(arr)//2left=bad_divide(arr[:mid])right=bad_divide(arr[mid:])returnleft+right# 正确：必须有基准情况defgood_divide(arr):iflen(arr)<=1:returnarr mid=len(arr)//2left=good_divide(arr[:mid])right=good_divide(arr[mid:])returnmerge(left,right)

8.2 陷阱2：子问题不独立（应该用动态规划）

分治要求子问题相互独立。如果子问题有重叠（如斐波那契数列），应该用动态规划或记忆化搜索：

# 错误：用分治计算斐波那契，时间复杂度O(2^n)deffib_divide(n):ifn<=1:returnnreturnfib_divide(n-1)+fib_divide(n-2)# 正确：用动态规划，时间复杂度O(n)deffib_dp(n):ifn<=1:returnn dp=[0]*(n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]

8.3 陷阱3：合并代价过高

分治的效率取决于合并步骤的代价。如果合并代价太高，分治可能不如直接求解：

# 反例：合并代价为O(n^2)，总复杂度可能不如暴力解法defbad_merge_sort(arr):iflen(arr)<=1:returnarr mid=len(arr)//2left=bad_merge_sort(arr[:mid])right=bad_merge_sort(arr[mid:])returnbad_merge(left,right)# O(n^2)合并# 总复杂度：O(n^2 log n)，不如直接O(n^2)的算法

九、总结

9.1 分治算法核心要点

分治算法三步走： 1. 分解（Divide）：将大问题拆成小问题 2. 解决（Conquer）：递归解决小问题 3. 合并（Combine）：将小问题的解合并为大问题的解 关键要素： - 基准情况（Base Case）：问题足够小，直接求解 - 子问题独立性：子问题之间无重叠 - 合并效率：合并步骤不能太耗时

9.2 分治 vs 其他算法思想

9.3 推荐练习题