文档章节

排序算法-10-算法-分治法(Divide and Conquer)

Corwien
 Corwien
发布于 2016/06/17 16:15
字数 768
阅读 155
收藏 0

##Divide and Conquer - 分治法 在计算机科学中,分治法是一种很重要的算法。分治法即**『分而治之』**,把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个思想是很多高效算法的基础,如排序算法(快速排序,归并排序)等。

###分治法思想 分治法所能解决的问题一般具有以下几个特征:

  1. 问题的规模缩小到一定的程度就可以容易地解决。
  2. 问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解。
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

分治法的三个步骤是:

  1. 分解(Divide):将原问题分解为若干子问题,这些子问题都是原问题规模较小的实例。
  2. 解决(Conquer):递归地求解各子问题。如果子问题规模足够小,则直接求解。
  3. 合并(Combine):将所有子问题的解合并为原问题的解。

分治法的经典题目:
Divide and Conquer - 分治法 在计算机科学中,分治法是一种很重要的算法。分治法即『分而治之』,把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个思想是很多高效算法的基础,如排序算法(快速排序,归并排序)等。

分治法思想 分治法所能解决的问题一般具有以下几个特征:

问题的规模缩小到一定的程度就可以容易地解决。 问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。 利用该问题分解出的子问题的解可以合并为该问题的解。 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 分治法的三个步骤是:

分解(Divide):将原问题分解为若干子问题,这些子问题都是原问题规模较小的实例。 解决(Conquer):递归地求解各子问题。如果子问题规模足够小,则直接求解。 合并(Combine):将所有子问题的解合并为原问题的解。

分治法的经典题目:

  1. 二分搜索
  2. 大整数乘法
  3. Strassen矩阵乘法
  4. 棋盘覆盖
  5. 归并排序
  6. 快速排序
  7. 循环赛日程表
  8. 汉诺塔

© 著作权归作者所有

共有 人打赏支持
Corwien
粉丝 26
博文 149
码字总数 115164
作品 0
广州
程序员
排序系列-归并排序

这个算法感觉有点儿 空间换时间的感觉,因为他的分治策略,在使用分布式,或者并行运算的时候应该有很大的发挥空间。 视频讲解 C语言版 http://v.youku.com/vshow/idXNjg1NTQzNTg4.html?from...

李雷岗
2016/11/28
2
0
递归 —— 二分查找法 —— 归并排序

PS:什么是递归、二分查找、归并排序。 递归排序大家都不陌生,递归简单的说就是自己在没有达到目的的同时在此调用本身,把一个大问题层层转化为和原问题相似的小问题解决,递归需要有边界条...

CMusketeer
07/29
0
0
图解排序算法(四)之归并排序

基本思想   归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conque...

myy629464
2017/09/18
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

解析高可用分布式键值存储 etcd 的原理

这篇文章将会介绍 etcd 的实现原理,其中包括 Raft 协议、存储两大模块,在最后我们也会简单介绍 etcd 一些具体应用场景。 etcd 的官方将它定位成一个可信赖的分布式键值存储服务,它能够为整...

小刀爱编程
27分钟前
2
0
在ubuntun虚拟机里安装goLang语言编程环境

Go语言是谷歌2009发布的第二款开源编程语言。 Go语言专门针对多处理器系统应用程序的编程进行了优化,使用Go编译的程序可以媲美C或C++代码的速度,而且更加安全、支持并行进程。 北京时间201...

JerryWang_SAP
27分钟前
6
0
c++builder导出函数export function DLL

__stdcall __export 即可,如: ulong __stdcall __export od_disasm(char *src,ulong srcsize,ulong srcip, t_disasm *disasm,int disasmmode){ return Disasm(src,srcsiz......

simpower
29分钟前
2
0
KDC服务安装及配置

阿伦哥-
32分钟前
2
0
mybatis-plus公共字段操作以及springboot2整合mybatis-plus

1、公共实体 对于User类中有而user表中没有的属性需要加第二个注解@TableField(exist = false),表示排除User类中的属性 所有新增公共字段加注解 并指定 @TableField(value = "corp_code",fi...

glen_xu
36分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部