分治算法
divide and conquer
核心: 分而治之
将原问题分成n个规模较小,且结构与原问题相似的子问题,
递归解决子问题,合并其结果,得到原问题的解.
递归的定义类似于分治
分治是一种处理问题的思想,递归是一种编程技巧
分治算法 一般都比较适合 用递归来实现
解题步骤
题目满足条件
原问题 与 子问题 具有相同的模式
子问题之间无相关性(这一点是 分治 与 动态规划 的明细区别)
具有 分解终止条件 (问题足够小时,可以直接得解)
子问题 的合并操作复杂度不能太高
解题步骤
分解: 将问题分解为 一系列结构类似的子问题
解决: 递归 求解各个子问题, 若问题足够小,直接返回解
合并: 将子问题的结果合并成原问题
分治算法实战
分治算法的原理不难,但灵活应用并不容易
求出一组数的逆序度
逆序度基础知识
n 个数据,期望递增排列,
则完全有序的数据 有序度为n(n-1)/2,逆序度为0
倒序排列的数据 有序度为0,逆序度为n(n-1)/2
数学满逆序度的计算思路,如 倒序排列的数据
每个数可以与另外(n-1)个数构成对,共n个数,有n(n-1)对数
每两个数 之间都会被 凑对两次,
但其中只有 当前数与其右侧数 的顺序组成的对,才是逆序,
即n(n-1)/2 就是所有逆序对的总和.
如何求出一组数据的 逆序对个数,或 有序对个数?
例如[2,4,3,1,5,6],逆序对(2,1)``(4,3)``(4,1)``(3,1)
最简单的办法,拿每个数字与后面的数比较,看有几个比他小,记为k,
每个数轮一遍后,每个数字的k值之和就是逆序对.时间复杂度O(n²).
分治思路:
将数组分为前半A1,后半A2,
计算 A1,A2 内各自的逆序对个数,k1,k2,
再计算A1,A2 间 的逆序对个数k3,
A的逆序度就是 k1 + k2 + k3.
分治解题: 用归并排序的算法改装
(后续补充代码,及leetcode题)
找出距离最近的点对
二维平面上n个点,设计算法快速找出 距离最近的两点(点对)
(后续补充代码,及leetcode题)
矩阵乘积
两个 n * n 的矩阵 A B,设计算法快速求解两个矩阵的乘积 C = A * B
(后续补充代码,及leetcode题)
MapReduce的分治思想应用
分治算法 将任务拆分成多个子任务,子任务可在多台机器上处理
例如 10GB 甚至 10T的数据,
对于谷歌搜索来说, 网页爬取,清洗,分析,分词,权重计算,倒排索引 等各个环节
都会面临海量的数据,采用 MapReduce框架 做任务调度器,
底层依赖 GFS来储存数据, Borg管理机器.
它从GFS中拿数据,交给Borg中的机器执行,Borg监控机器执行的进度,
一旦出现机器宕机 进度卡壳等,就重新从 Borg中调度一台机器执行.
其中 MapReduce 负责提供 高可靠,高性能,高容错的 并行框架计算,
并行处理 几十亿 上百亿 的网页.
既可以处理 数据与数据之间存在关系的任务,如 统计文件(网页)中单词的出现频率.
又可以处理 数据与数据之间没有关系的任务,如 网页分析,分词,每个网页独立分析.
用的就是 分治思想.
拆解任务,多机并行处理,再合并结果(存在关系的任务),也可纯拆不合并(无关系的任务)
