- 浏览: 1639653 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (405)
- C/C++ (16)
- Linux (60)
- Algorithm (41)
- ACM (8)
- Ruby (39)
- Ruby on Rails (6)
- FP (2)
- Java SE (39)
- Java EE (6)
- Spring (11)
- Hibernate (1)
- Struts (1)
- Ajax (5)
- php (2)
- Data/Web Mining (20)
- Search Engine (19)
- NLP (2)
- Machine Learning (23)
- R (0)
- Database (10)
- Data Structure (6)
- Design Pattern (16)
- Hadoop (2)
- Browser (0)
- Firefox plugin/XPCOM (8)
- Eclise development (5)
- Architecture (1)
- Server (1)
- Cache (6)
- Code Generation (3)
- Open Source Tool (5)
- Develope Tools (5)
- 读书笔记 (7)
- 备忘 (4)
- 情感 (4)
- Others (20)
- python (0)
最新评论
-
532870393:
请问下,这本书是基于Hadoop1还是Hadoop2?
Hadoop in Action简单笔记(一) -
dongbiying:
不懂呀。。
十大常用数据结构 -
bing_it:
...
使用Spring MVC HandlerExceptionResolver处理异常 -
一别梦心:
按照上面的执行,文件确实是更新了,但是还是找不到kernel, ...
virtualbox 4.08安装虚机Ubuntu11.04增强功能失败解决方法 -
dsjt:
楼主spring 什么版本,我的3.1 ,xml中配置 < ...
使用Spring MVC HandlerExceptionResolver处理异常
3)分类和合并同时进行
典型事例 快速排序:(以整数类型为例)
快速排序的思想是,对于输入,按照以下二个步骤进行排序
对于数组a[p:r]
1)分解(其实包括合并过程):以a[p]为基准将数组分成三段a[p:q-1]、a[q]、a[q+1:r]使得a[p:q-1]中的任意元素都小于等于a[q],a[q+1:r]中的任意元素都大于等于a[q].
2)递归求解:通过递归调用快速排序,分别完成a[p:q-1]和a[q+1:r]的排序。
程序代码:
与QuickSort类似的例子是选择问题:
我们经常遇到的选择问题是选择最大元素和最小元素的问题,这个问题解决起来比较容易,而且时间复杂度为O(n),但是当我们把这个问题一般化的时候,既选择第k小(大)的元素的时候,思考一下,最容易想到的方法是排一下序,第k个 位置就是第k小的元素,在想一想可以找一些能够在每一次能够确定一个元素的最终位置的排序方法(如冒泡法,直接选择排序法等)只需要排好k(k<=n/2时)个的元素或者n-k(k>n/2),但是这样的话其实时间复杂性仍然是O(n^2),比找最大和最小所用的时间复杂度大的多。如果采用QuickSort算法其时间复杂度为O(nlogn),对于排序的确是个非常好的算法,但是我们想QuickSort是把所有的元素都排好的时间复杂度,我们找第k小的元素,从感性上也可以知道这是比排序要简单的问题,但是找第k小的元素,k本身就是个序号问题,如果不排序似乎解决不了这个问题。似乎有一个简单的情形会给我们以启发:我们在桌子上摆了一副扑克,我们规定了各个扑克的大小,现在是找第k小的元素,人或许很容易看出,但计算机似乎有点困难,那就找个就简单的方法吧---瞢,瞢当然不是瞎瞢,瞢错了你可以去掉一些不符和条件的扑克,例如瞢到了一张红桃k,现在好办了,把比红桃k小的扑克数一数,如果小于k-1,那好把红桃k和那些扑克仍在一边,如果等于k-1,恭喜你,瞢对了,否则,把其他的扑克和k仍在一边。对剩余的扑克继续重复上述过程(当然这是k应适当的变化一下)。其实我们发现上述过程如果不是运气特差的话,一次就能够扔掉不少扑克牌。
其算法如下:
//搜索第k小的元素
//上述的算法当然不是优化之后的算法,虽然这个算法最坏情况下仍然是O(n^2),但平均复杂度只是o(n),虽然改进后的的算法在最坏的情况下时间复杂度线性的T(n)<=72c1n,即nlog(10^72)这个算法显然在实际上已经没有什么应用的价值,只有理论价值,因为当数据的规模在比10^72这个数量大的时候,他的速度才会超过快速排序的最坏结果。下面是改进后的算法(线性搜索)的思路.考虑上面程序算法最坏的情况在什么时候发生?当每一次你选择的元素都离你要选择的基准元素相差最远的时候。改进算法就是为了不至于每次都遇到这么差的运气,所以他在选择分化基准元素的时候,他尽量选择大小在中间大小的元素,因为这样在平均的情况下效率挺高,一次就扔掉一半,在最坏的情况下也不会很坏。所以在partition之前要在n个元素中选择中间元素,这当然也是个很难简单就解决的问题,所以不一定真的是最中间的,大体上差不多就行了,因为这样远远比最中间的元素的时间复杂度小得多。算法的步骤如下:
1)将参加划分的n个元素分成[n/r]组(r>1),每组有r个元素,将n-r[n/r]的元素扔掉,然后对每一组的元素找出中间的元素,然后再从中间元素选择中间元素,这样的元素已经满足我们的要求了,虽然不一定是真正的中间元素。二次取中间值的方法复杂度是o(n)数量级的。其他的就和上面没改进的算法步骤一样了,不再详述。
分治法作为一种算法思想和前人总结的经验,关键是理解其算法的思想,不同的题难度不一,应具体问题具体分析。
典型事例 快速排序:(以整数类型为例)
快速排序的思想是,对于输入,按照以下二个步骤进行排序
对于数组a[p:r]
1)分解(其实包括合并过程):以a[p]为基准将数组分成三段a[p:q-1]、a[q]、a[q+1:r]使得a[p:q-1]中的任意元素都小于等于a[q],a[q+1:r]中的任意元素都大于等于a[q].
2)递归求解:通过递归调用快速排序,分别完成a[p:q-1]和a[q+1:r]的排序。
程序代码:
int partition(int a[],int p,int r) { int i=p,j=r+1,x=a[p],temp; while(true) { while(x>a[i]){++i;} while(x<a[j]){--j;} if(i>=j) break; temp=a[i]; a[i]=a[j]; a[j]=temp; } a[p]=a[j]; a[j]=x; return j; } void QuickSort(int a[],int p,int r) { if(p < r) { int q=partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); } }
与QuickSort类似的例子是选择问题:
我们经常遇到的选择问题是选择最大元素和最小元素的问题,这个问题解决起来比较容易,而且时间复杂度为O(n),但是当我们把这个问题一般化的时候,既选择第k小(大)的元素的时候,思考一下,最容易想到的方法是排一下序,第k个 位置就是第k小的元素,在想一想可以找一些能够在每一次能够确定一个元素的最终位置的排序方法(如冒泡法,直接选择排序法等)只需要排好k(k<=n/2时)个的元素或者n-k(k>n/2),但是这样的话其实时间复杂性仍然是O(n^2),比找最大和最小所用的时间复杂度大的多。如果采用QuickSort算法其时间复杂度为O(nlogn),对于排序的确是个非常好的算法,但是我们想QuickSort是把所有的元素都排好的时间复杂度,我们找第k小的元素,从感性上也可以知道这是比排序要简单的问题,但是找第k小的元素,k本身就是个序号问题,如果不排序似乎解决不了这个问题。似乎有一个简单的情形会给我们以启发:我们在桌子上摆了一副扑克,我们规定了各个扑克的大小,现在是找第k小的元素,人或许很容易看出,但计算机似乎有点困难,那就找个就简单的方法吧---瞢,瞢当然不是瞎瞢,瞢错了你可以去掉一些不符和条件的扑克,例如瞢到了一张红桃k,现在好办了,把比红桃k小的扑克数一数,如果小于k-1,那好把红桃k和那些扑克仍在一边,如果等于k-1,恭喜你,瞢对了,否则,把其他的扑克和k仍在一边。对剩余的扑克继续重复上述过程(当然这是k应适当的变化一下)。其实我们发现上述过程如果不是运气特差的话,一次就能够扔掉不少扑克牌。
其算法如下:
//搜索第k小的元素
int partition(int a[],int p,int r)//分化 { int i=p,j=r+1,x=a[p],temp; while(true) { while(x>a[i]){++i;} while(x<a[j]){--j;} if(i>=j) break; temp=a[i]; a[i]=a[j]; a[j]=temp; } a[p]=a[j]; a[j]=x; return j; } int SelectK(int a[],int p,int n,int k)//选择 { int q,i; q=partition(a,p,n); i=q-p+1; if(i<k) return SelectK(a,q+1,n,k-i); else if(i==k) return a[q]; else return SelectK(a,p,q-1,k); }
//上述的算法当然不是优化之后的算法,虽然这个算法最坏情况下仍然是O(n^2),但平均复杂度只是o(n),虽然改进后的的算法在最坏的情况下时间复杂度线性的T(n)<=72c1n,即nlog(10^72)这个算法显然在实际上已经没有什么应用的价值,只有理论价值,因为当数据的规模在比10^72这个数量大的时候,他的速度才会超过快速排序的最坏结果。下面是改进后的算法(线性搜索)的思路.考虑上面程序算法最坏的情况在什么时候发生?当每一次你选择的元素都离你要选择的基准元素相差最远的时候。改进算法就是为了不至于每次都遇到这么差的运气,所以他在选择分化基准元素的时候,他尽量选择大小在中间大小的元素,因为这样在平均的情况下效率挺高,一次就扔掉一半,在最坏的情况下也不会很坏。所以在partition之前要在n个元素中选择中间元素,这当然也是个很难简单就解决的问题,所以不一定真的是最中间的,大体上差不多就行了,因为这样远远比最中间的元素的时间复杂度小得多。算法的步骤如下:
1)将参加划分的n个元素分成[n/r]组(r>1),每组有r个元素,将n-r[n/r]的元素扔掉,然后对每一组的元素找出中间的元素,然后再从中间元素选择中间元素,这样的元素已经满足我们的要求了,虽然不一定是真正的中间元素。二次取中间值的方法复杂度是o(n)数量级的。其他的就和上面没改进的算法步骤一样了,不再详述。
分治法作为一种算法思想和前人总结的经验,关键是理解其算法的思想,不同的题难度不一,应具体问题具体分析。
发表评论
-
二分查找之变型题目
2010-10-24 12:40 2122二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就 ... -
一道笔试题(创新工厂)解法
2010-10-21 17:44 1821一个帖子http://www.iteye.com/topic/ ... -
[zz]大数据量,海量数据 处理方法总结
2010-08-27 22:24 2244大数据量的问题是很多面试笔试中经常出现的问题,比如baidu ... -
Trie and suffix array
2010-04-13 20:54 1903字典数Trie和后缀数组suffix array是处理字符串操 ... -
金币问题
2009-11-09 08:41 1992今年某公司的笔试题: 一个矩阵地图,每一个元素值代表金币数, ... -
楼梯问题
2009-11-09 08:19 1545hl给我的几道某公司的算法题: 1、 有个 100 级的 ... -
一道考察模拟乘法的题目
2009-11-07 22:37 1398今天hl和我讨论一道题目: 写道 整形数组如a={1,4, ... -
链表归并
2009-11-07 21:40 1004以前gx同学问的某某公司的笔试题,写一下练练(纯手写,没编译过 ... -
找出出现次数超过一半的数字
2009-11-07 21:23 1865hl同学问我一道这个题,想了一种方法,感觉还是不错的,只扫描一 ... -
有道难题以超低分晋级
2009-06-10 11:36 1538有道难题比赛居然晋级了,可以领到一个t-shirt。 -
逆序数/逆序数对
2009-06-09 23:17 3742逆序数是个常遇到的问题,主要有两种解法: O(n^2)的方法: ... -
有道难题topcoder
2009-05-31 23:55 2431今天做了有道topcoder的题目,也是第一次在topcode ... -
百度之星第一场题目
2009-05-31 00:03 3597由于不符合参赛条件,未能参加百度之星,看了题目还挺有意思,把题 ... -
一个对字符串很好的Hash函数ELFHHash
2009-05-03 21:41 2247#include<stdio.h> #defin ... -
最大流Ford-Fulkerson算法
2009-04-22 17:33 9631算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford- ... -
大数/高精度加减乘除取模[收藏]
2009-04-16 19:38 5031#include <iostream> #i ... -
带重复数字的全排列
2009-04-16 18:58 3863上次gx同学问我一道又重复数字的全排列的问题,我当时用set保 ... -
差分约束系统
2009-04-15 16:00 3690(本文假设读者已经有以下知识:最短路径的基本性质、Bellma ... -
二分图匹配
2009-04-15 15:40 3703二分图最大匹配的匈牙利算法 二分图是这样一个图,它的顶点可以分 ... -
线段树
2009-03-24 10:58 1658把问题简化一下: 在自然数,且所有的数不大于30000的 ...
相关推荐
关于分治法的算法结课论文,讲述了分治法与递归的联系与区别。分治法是解题思路,而递归是实现的方法,可用递归,也可用非递归
算法分析第二单元员 分治法的学习 中的经典问题3 也叫做归并排序
第十讲 分治法总结.ppt 算法分析与设计
必做:n 用分治思想设计实现二分搜索、合并排序,并且用不同数据量进行实验对比分析。 选做:阶乘(递归与分治)。
1.串匹配问题 给定一段文本,在该文本中查找并定位任意给定字符串。 要求: (1)实现BF算法; (2) 实现BF算法的改进算法:KMP算法 ...(2)分析算法的时间性能,设计实验程序验证分析结论。
汇总了计算机研究生复试有关算法分析与设计各章节简答题,使用了易于口头表达的语言进行了总结。包括算法分析与设计基本概念及各章节问题回答。可供研究生复试或相关专业岗位面试使用。 1. 简述算法定义、属性及指标...
本书目录:出版者的话专家指导委员会译者序前言第1章 引论1.1 本书讨论的内容1.2 数学知识复习1.2.1 指数1.2.2 对数1.2.3 级数1.2.4 模运算1.2.5 证明方法1.3 递归简论总结练习第2章 算法分析2.1 数学基础2.2 模型...
1. 掌握减治法和分治法的思想,熟练掌握顺序表基本算法的实现。 2. 掌握利用利用减治法和分治法解决同一问题的思路。 3. 分析核心代码的时间复杂度和空间复杂度。 二、实验内容和要求 编写一个程序实现任意大整数...
热心学姐来送福利啦哈哈哈哈哈哈哈哈哈哈哈哈哈,西北农林科技大学的算法分析实验报告,
本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支限界法。总结了各类算法的思想和基本解题思路,以及对应的经典题目,适合...
里面有些是用JavaScript写的算法 有些是C++写的 分治法 动态规划 回溯法 贪心法
介绍算法设计的几类方法,如分治法、回溯法、贪心法、动态规划法、分枝限界法等,并结合某些有实用意义的经典算法来加深设计方法的探讨,由浅入深地进行算法效率分析,使学生在掌握各种算法设计方法和分析基本技术的...
1、分治法的基本思想:是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。 2、贪心选择性质:指所求问题的整体最优...
深入理解分治法的算法思想,应用分治法解决实际的算法问题。 【实验性质】 综合性实验 【实验内容与要求】 实验要求】 设下图G=(V,E)是一连通无向图,有3种颜色,用这些颜色为G的各顶点着色,每个顶点着一种颜色,且...
labview的子串和数值提的实现,对于学习使用labview具有极大帮助
主要介绍了Python分治法定义与应用,较为详细的分析了Python分治法的概念、原理、用途,并结合实例总结了Python分治法的各种常见应用,需要的朋友可以参考下
总结的关于中科大研究生课程算法设计与分析习题答案,包括分治法、动态规划、贪心算法、回溯、分支限界等章节内容
四、算法分析与设计 102 1.常用的算法设计方法: 102 1.1 迭代法: 102 1.2 穷举搜索法: 103 1.3 递推法: 104 1.4 递归法 106 1.5 贪婪法 111 1.6 分治法 113 1.7 动态规划法 115 1.8 回溯法 119 1.9 分支定界法...
本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支限界法。总结了各类算法的思想和基本解题思路,以及对应的经典题目,适合...