分治算法
分治思想： 分治算法是一种将一个复杂问题分解成多个较小的子问题，通过递归解决子问题，再将子问题的解合并起来，得到原问题的解。分治思想的核心是通过将问题规模减小、分解和组合来简化问题的解决。
分治算法的基本步骤：
- 分解：将问题划分为多个规模较小、结构与原问题类似的子问题。
- 解决：递归地解决这些子问题，当子问题的规模足够小或问题简单时，可以直接求解。
- 合并：将子问题的解合并成原问题的解。
减治算法： 减治算法是分治算法的一种特殊形式，它也将问题分解成多个子问题，但在减治算法中，通常没有合并步骤。每次递归都是通过缩小问题规模来直接逼近解决方案，典型的例子是 归纳法 和 动态规划。
二分法
什么是二分法： 二分法是一种通过将问题的解空间不断对半分割，逐步缩小搜索范围的算法。通常用来解决有序数据的查找问题。二分法的典型例子是 二分查找，其基本思想是通过比较目标值和中间元素来决定查找区间，逐步缩小查找范围。
二分法变异： 二分法变异是对传统二分法的扩展或修改，常见的变异包括：
- 变异1：处理不完全有序的情况（例如，寻找最左或最右的目标元素）。
- 变异2：用于解决更复杂的决策问题，比如 最小最大值问题 或 区间问题。
为什么需要变异二分法： 传统二分法只适用于简单的查找问题，但在实际应用中，经常遇到更复杂的情况，如：
- 查找某个值的最左或最右位置。
- 求解某个条件成立的最小/最大值。
- 寻找某个阈值条件下的解空间。
这些问题需要对标准二分法进行适当变异，以适应更复杂的需求。
重要例题
- 金块问题：
- 问题：给定一个二维矩阵，其中每个位置都有金块，如何找到从左上角到右下角的最大金块数？你可以在矩阵中上下左右移动。
- 引出结论：通过分治，将问题分解成子问题，利用动态规划的思想来求解最大值。
- 残缺棋盘问题：
- 问题：给定一个
2^n x 2^n的棋盘，其中一个小方块被去除，如何将其余部分覆盖上 L 型小块？ - 引出结论：这是一道典型的分治问题，通过递归分割棋盘并覆盖，可以有效地解决。
- 问题：给定一个
- 循环赛日程表：
- 问题：有
n个队伍，如何安排一个循环赛程，使得每个队伍与其他队伍比赛一次？ - 引出结论：通过分治，将问题划分为较小的子问题，求解比赛安排。
- 问题：有
- 最大子段和问题：
- 问题：给定一个整数数组，求出其中和最大的连续子数组。
- 引出结论：这道题目可以通过分治的方式进行求解，分解成较小的子问题，最终合并求得最大子段和。
重要算法
冒泡排序
- 时间复杂度：
O(n^2) - 空间复杂度：
O(1) - 特点：通过多次遍历，将最大（或最小）元素“冒泡”到数组的一端。适合小规模数据。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("冒泡排序结果:", bubble_sort(arr))插入排序
- 时间复杂度：
O(n^2) - 空间复杂度：
O(1) - 特点：通过从未排序的部分插入元素到已排序部分，逐步扩大已排序部分。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("插入排序结果:", insertion_sort(arr))快速排序
- 时间复杂度：
O(n log n)（平均），O(n^2)（最坏） - 空间复杂度：
O(log n)（平均） - 特点：通过选择一个基准元素，将数组分为两个部分，递归地对每个部分进行排序。效率较高。
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)
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("快速排序结果:", quick_sort(arr))归并排序
- 时间复杂度：
O(n log n) - 空间复杂度：
O(n) - 特点：通过递归地将数组分成两个子数组，然后合并排序。稳定且适用于大规模数据。
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("归并排序结果:", merge_sort(arr))
