算法：分治

敖炜 Lv5
  2024-03-12 14:25:17 2024-03-12 14:25:17 创建   2024-04-19 09:30:21 2024-04-19 09:30:21 更新      1.4k 字  5 分钟  

分治

分治算法

分治算法全称分而治之，通常基于递归实现，包括“分”和“治”两个步骤（MapReduce就是这个思路）

  1. 分（划分）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止
  2. 治（合并）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解

何时适用分治算法

  1. 问题可分解：原问题可分解为类似的子问题，子问题可用相同方式进行划分
  2. 子问题是独立的：子问题之间没有重叠，可独立解决
  3. 子问题的解可以合并：原问题的解通过合并子问题的解得来

通过分治提升效率

分而治之既可以有效解决算法问题，还可以提升算法效率。算法效率的提高可以从操作数量和并行计算两个方面讨论

  1. 操作数量优化

  1. 并行计算优化

分治生成的子问题是相互独立的，通常可以并行解决，有利于操作系统的并行优化

分治常见应用

  1. 解决经典算法问题

寻找最近点对、大整数乘法（Karatsuba）、矩阵乘法（Strassen）、汉诺塔问题、求解逆序对

  1. 应用于设计算法和数据结构

二分查找、归并排序、快速排序、桶排序、树（如BST、AVL树、红黑树、B树、B+树等的查找、插入和删除操作）、堆、哈希表（某些哈希冲突解决方案间接应用了分治策略）

分治搜索策略

回顾一下，搜索算法分为两大类

  • 暴力搜索：遍历数据结构，时间复杂度为
  • 自适应搜索：利用特有的数据组织形式或先验信息，时间复杂度可达到甚至

这其中时间复杂度为的搜索算法通常是基于分治策略实现的，本质上是暴力搜索每轮只能排除一个选项，而分治搜索每轮可以排除一半选项

构建二叉树问题

Q：给定一课二叉树的前序遍历和中序遍历，从中构建二叉树，返回二叉树的根节点（假设二叉树中没有值重复的节点）

  1. 如何分治
  • 问题如何分解：将原问题划分为构建左子树、右子树和初始化根节点。每棵子树上可以有相同的划分方式。
  • 子问题独立：左子树与右子树相互独立，没有交集
  • 子问题的解可以合并：得到左子树和右子树后，分别与根节点连接即可
  1. 如何划分子树

前序遍历：[ 根节点 | 左子树 | 右子树 ]
中序遍历：[ 左子树 | 根节点 | 右子树 ]

  • 前序遍历第一个节点即为根节点
  • 在中序遍历中找到根节点索引，从而可确定左子树和右子树节点个数
  • 已知左子树和右子树节点个数，就可以对前序遍历进行划分
  1. 基于变量描述子树区间
  • 当前树的根节点在pre中的索引记为i
  • 当前树的根节点在in中的索引记为m
  • 当前树在in中的索引区间记为[l, r]

根据以上变量，可以推断

  • 左子树根节点在pre中的索引为i+1

  • 右子树根节点在pre中的索引为i+1+(m-l)
    m-l的含义是“左子树的节点数量”

  • 左子树在in中的索引区间[l, m-1]

  • 右子树在in中的索引区间[m+1, r]

  1. 代码实现

hmap存储数组inorder中元素到索引的映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def dfs(preorder, inorder_map, i, l, r):
    """构建二叉树：分治"""
    if r - l < 0:
        return None
    # 初始化根节点
    root = TreeNode(preorder[i])
    # 查询m，从而划分左子树
    m = inorder_map[preorder[i]]
    # 子问题：构建左子树
    root.left = dfs(preorder, inorder_map, i+1, l, m-1)
    # 子问题：构建右子树
    root.right = dfs(preorder, inorder_map, i+1+(m-l), m+1, r)
    # 返回根节点
    return root

def build_tree(preorder, inorder):
    inorder_map = {val: i for i, val in enumerate(inorder)}
    root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)
    return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* dfs(vector<int>& preorder, unordered_map<int, int>& inorderMap, int i, int l, int r){
    if (r - l < 0){
        return NULL;
    }
    TreeNode* root = new TreeNode(preorder[i]);
    int m = inorderMap[preorder[i]];
    root->left = dfs(preorder, i+1, l, m-1);
    root->right = dfs(preorder, i+1+m-l, m+1, r);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
    unordered_map<int, int> inorderMap;
    for(int i = 0; i < inorder.size(); i++){
        inorderMap[inorder[i]] = i;
    }
    TreeNode* root = dfs(preorder, inorderMap, 0, 0, inorder.size()-1);
    return root;
}

时空复杂度

  1. 设树的节点数量为n，初始化每一个节点使用时间，总体时间复杂度为
  2. 当二叉树退化为链表时，最差情况出现，此时递归深度达到n，总体空间复杂度为

汉诺塔问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def move(src, tar):
    """移动一个圆盘"""
    pan = src.pop()
    tar.append(pan)

def dfs(i, src, buf, tar):
    """求解汉诺塔问题f(i)"""
    # 将src顶部i个圆盘借助buf移到tar
    if i == 1:
        move(src, tar)
        return
    # 子问题f(i-1):将src顶部i-1个圆盘借助tar移到buf
    dfs(i - 1, src, tar, buf)
    # 子问题f(1):将src剩余一个圆盘移到tar
    move(src, tar)
    # 子问题f(i-1):将buf顶部i-1个圆盘借助src移到tar
    dfs(i-1, buf, src, tar)

def solve_hanota(A, B, C):
    n = len(A)
    dfs(n, A, B, C)

时空复杂度

时间复杂度为，空间复杂度为

  • 标题: 算法：分治
  • 作者: 敖炜
  • 创建于 : 2024-03-12 14:25:17
  • 更新于 : 2024-04-19 09:30:21
  • 链接: https://ao-wei.github.io/2024/03/12/算法：分治/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
算法：分治
  1. 分治算法
    1. 何时适用分治算法
    2. 通过分治提升效率
    3. 分治常见应用
    4. 分治搜索策略
    5. 构建二叉树问题
      1. 时空复杂度
    6. 汉诺塔问题
      1. 时空复杂度