文档章节

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

Corwien
 Corwien
发布于 2016/06/17 16:15
字数 768
阅读 139
收藏 0
点赞 0
评论 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
图解排序算法(四)之归并排序

基本思想   归并排序(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
数据结构-二路归并及归并排序

一、介绍: 归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;...

sssssuuuuu666
2017/12/08
0
0
白话经典算法系列之五 归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

彭博
2012/04/12
41
0
Java排序算法(九):归并排序

归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 归并排序是建立在归并...

小七_Dream
2015/09/28
2K
0
人工智能你必须掌握的32个算法(二)归并排序算法

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子...

木头释然
07/16
0
0
7--归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 归并排序思想: 多次将两个或者两个以上的有序表合并成一个新的有序表。...

抢地主
2016/03/24
35
0
【算法和数据结构】排序(四)归并排序和快速排序(C++实现)

归并排序和快速排序 前言: 前面三篇文章分别介绍了三种排序算法:冒泡排序、插入排序和选择排序。它们的实现思想都是基于排序问题本身产生的,时间复杂度都是θ(n^2)。 而现在介绍的两种排...

qq_28869927
2017/01/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

rabbitmq学习记录(六)交换机Exchange-direct

实现功能:一条消息发送给多个消费者 交换机模式:direct 相比于之前的fanout模式,可以进一步的筛选获取消息的消费者。 fanout模式下,只要消费者监听的队列,已经与接收生产者消息的交换机...

人觉非常君
13分钟前
0
0
Java 之 枚举

Java 中声明的枚举类,均是 java.lang.Enum 类的子类,Enun 类中的常用方法有: name() 返回枚举对象名称 ordinal() 返回枚举对象下标 valueOf(Class enumType, String name) 转换枚举对象 ...

绝世武神
21分钟前
0
0
使用爬虫实现代理IP池之放弃篇

啥叫代理IP以及代理IP池 概念上的东西网上搜索一下就好了,这里简单科普一下(大部分会读这篇文章的人,基本是不需要我来科普的),白话说就是能联网并提供代理访问互联网的服务器,它提供的...

一别丶经年
37分钟前
0
0
sqoop导入数据到Base并同步hive与impala

使用Sqoop从MySQL导入数据到Hive和HBase 及近期感悟 基础环境 Sqool和Hive、HBase简介 Sqoop Hive HBase 测试Sqoop 使用Sqoop从MySQL导入数据到Hive 使用复杂SQL 调整Hive数据类型 不断更新 ...

hblt-j
今天
0
0
Dart 服务端开发 文件上传

clent端使用angular组件 upload_component.html form id="myForm" method="POST" enctype="multipart/form-data"> <input type="file" name="fileData"> <!-- file field --></form>......

scooplol
今天
0
0
apache和tomcat同时开启,乱码问题

tomcat和apache同时开启,会走apache的转发,执行的是AJP/1.3协议。所以在tomcat的配置文件server中, <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" useBodyEncodingForU......

Kefy
今天
0
0
使用ssh-keygen和ssh-copy-id三步实现SSH无密码登录 和ssh常用命令

ssh-keygen 产生公钥与私钥对. ssh-copy-id 将本机的公钥复制到远程机器的authorized_keys文件中,ssh-copy-id也能让你有到远程机器的home, ~./ssh , 和 ~/.ssh/authorized_keys的权利 第一步...

xtof
今天
0
0
orcale 查询表结构

SELECT t.table_name, t.colUMN_NAME, t.DATA_TYPE || '(' || t.DATA_LENGTH || ')', t1.COMMENTS FROM User_Tab_Cols t, User_Col_Comments t1WHERE t.table_name......

wertwang
今天
0
0
华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大

华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大!华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大! 在华为最新发布的nova 3手机上,抖音通过华为himedia SDK集成了60fps、超级...

华为终端开放实验室
今天
0
0
多 SSH Key 实现同一台服务器部署多 Git 仓库

本文以以下需求为背景,介绍详细的做法: 需在同一台服务器同时部署两个不同的 Github 仓库(对 Bitbucket 等 git 服务同样适用) root 用户可在远程登录 SSH 后附上预期的 SSH Key 进行 gi...

yeahlife
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部