综合算法 II | 分治与贪心

综合算法 II | 分治与贪心分治算法分治Divide and Conquer将大问题分解为小问题分别求解后合并结果。归并排序def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): 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快速排序def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) middle quick_sort(right)贪心算法贪心Greedy在每一步选择当前最优解期望得到全局最优。活动选择问题def activity_selection(activities): activities.sort(keylambda x: x[1]) count 1 end activities[0][1] for i in range(1, len(activities)): if activities[i][0] end: count 1 end activities[i][1] return count哈夫曼编码哈夫曼编码使用贪心构建最优前缀码。分治与贪心对比特点分治贪心策略分解后合并局部最优最优性保证最优不一定最优复杂度通常 O(n log n)因问题而异总结分治和贪心是两种重要的算法策略。分治保证最优贪心效率高但需验证。