分治法 练习题 divide and conquer

杨峻2022-10-04 11:39:541条回答

分治法 练习题 divide and conquer
一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减
设计分治法算法找位置p;
用你的算法建立递归关系对于键值比较并解释;
(set up a recurrence relation for the number of key comparisons made by your algorithm and explain it)
根据递归关系,用BIG-O 符号写出复杂度 并用数学归纳法证明(为了简单,可以设n=2k)
急用 最后一问可以不答 只要设计好算法 并写出递推关系式比如T(n)=T(n-2)+1

已提交,审核后显示!提交回复

共1条回复
梦的女 共回答了20个问题 | 采纳率90%
可以用经典的二分法:每次找中间位置.具体地说,
初始有端点1和n,故取中点p=[(n+1)/2],这里中括号表示取整.考察连续的三个点p-1,p,p+1处的数的大小关系.由于已知序列是单峰的(为容易说明算法思想,假设没有相等的数),故A_{p-1},A_{p},A_{p+1}只有三种可能:要么递增,要么递减,要么先增后减.
如果先增后减,则此p即为所求.
如果递增,则说明欲求的峰值点比这个p点大,那么考虑端点p和n,重复上面的算法.
如果递减,则说明欲求的峰值点比这个p点小,那么考虑端点1和p,重复上面的算法.
这就建立了递归算法.
复杂度是O(log_2{n}).因为每次考虑都把欲求的峰值点的可能位置从全部可能中缩小一半(加减1,在大O符号中可忽略不及).具体地说,当序列长度是2^m的时候,第一次取中点,排除掉一半可能,剩下2^{m-1}个可能的峰值点;第二次取中点,排除掉一半可能,剩下2^{m-2}个可能的峰值点;一次类推.最终经过至多多m+1次就能找到峰值点.反过来看,设n=2^m,那么m=log_2{n}.用大O符号,数值+1可以忽略.当序列长度不是2^m的时候,一定有一个m使得序列长度介于2^{m}和2^{m+1},按照上述证明,复杂度介于O(log_2{n})和O(log_2{n}-1),这俩O符号的意思的一样的,所以复杂度是O(log_2{n}).
用归纳法证明的思想本质是一样的,不过严格的陈述需要自己设定很多额外的约定才能说清楚,比如n的值从介于2^{m-1}和2^m变化到介于2^m和2^{m+1}的时候用归纳,需要一些详尽的精准的陈述,不推荐.
1年前

相关推荐

算法设计与分析习题谁会做给定数组A=(98,31,22,44,37,9)试用分治法求其第二小元素(要求使用SELECT算
算法设计与分析习题谁会做
给定数组A=(98,31,22,44,37,9)
试用分治法求其第二小元素
(要求使用SELECT算法)
hongaikai1年前1
sysshang 共回答了18个问题 | 采纳率94.4%
这个是利用分治思想来解
考点是快排
可以用二分法对原数组进行排序
快排(QuickSort)是一种基于分治思想的二分排序法.对于一段序列,我们先
选出一个划分元素,然后用线性的时间复杂度将大于和小于划分元素的元素
移动到划分元素的两边,再由划分元素处将序列拆分为两部分,分别进一步
处理.显然这里划分元素的选择决定了拆分序列的平均程度.
因为算法是二分的,每段序列的处理是线性的,易知时间复杂度为O(nlgn).
可是假设每一次选择的划分元素都是序列里最大或最小的,那么拆分的时间
复杂度也会变成线性的,所以快排在最坏情况下的时间复杂度为O(N^2).
用分治法在一个元素集合中寻找最大元素和最小元素 c++
用分治法在一个元素集合中寻找最大元素和最小元素 c++
算法我会 主要是主函数不会写
如果您没有完整代码 教我一下主函数怎么写也行
chenwull1年前1
巴颜格日顺 共回答了12个问题 | 采纳率100%
我做的::(其中算法中我设计的是模板类,不想那么复杂所以主函数中就直接用集合int a[10]={2,5,3,9,7,6,0,1,4,8}了)
分治法:
#include "stdafx.h"
#include
template
class SortableList
{
private:
T *l;
int maxSize,n;
public:
SortableList(int mSize)
{
maxSize=mSize;
l=new T[maxSize];
n=0;
}
~SortableList(){delete []l;}
void MaxMin(int i,int j,T &max,T &minn)const;
int init(T a[],int nSize)
{
if(nSize
算法设计与分析的题目,证明:如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂
算法设计与分析的题目,
证明:如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到O(n).
这是关于分治法的题
喵囡1年前1
touppp34 共回答了13个问题 | 采纳率92.3%
上面那个完全是照搬别人的嘛,问题也都不一样的.关键点在于子规模与合并这间的关系
从分治法的一般设计模式可以看出,用它设计的程序一般是 A、顺序 B、选择 C、循环 D、递归
diejian1年前1
shiye911 共回答了17个问题 | 采纳率76.5%
D、递归
简单的说,分治法就是把一个大问题分成两小问题;然后用同样的算法分别套用到这两个小问题上,知道问题被分解到一个极限,成为1个极简单的原子问题,从而可以简单的求解。
五个名词解释:(1) 计算机算法(2) 最好情况(3) 分治法(4) 图的着色问题(5) 最坏情况(6) 旅行售货员问题
涛241年前1
xuhengzhang 共回答了19个问题 | 采纳率89.5%
(1)计算机算法
计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程,或者说,算法是对计算机上执行的计算过程的具体描述.
http://baike.baidu.com/view/1337026.htm?fr=ala0
(2) 最好情况和(5) 最坏情况
参看http://baike.baidu.com/view/396887.html
(3) 分治法
http://baike.baidu.com/view/1583824.htm
(6) 旅行售货员问题
旅行售货员问题是图论中非常著名的一个问题,用图论的语言描述:即求一个正权完全图的权值最小的哈密顿回路(H―回路).
分治法的几种变形、实例分析、二分查找法 Binary Search
诚者无妄1年前1
梦阆中宋雪儿 共回答了15个问题 | 采纳率66.7%
分治法的几种变形
二分法 dichotomy
一种每次将原问题分解为两个子问题的分治法,是一分为二的哲学思想的应用.这种方法很常用,由此法产生了许多经典的算法和数据结构.
分解并在解决之前合并法 divide and marriage before conquest
一种分治法的变形,其特点是将分解出的子问题在解决之前合并.
管道传输分治法 pipelined divide and conquer
一种分治法的变形,它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回.此方法经常用来减少算法的深度.分治法的实例分析 二分查找法 Binary Search
在对线性表的操作中,经常需要查找某一个元素在线性表中的位置.此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息.
比较自然的想法是一个一个地扫描L的所有元素,直到找到x为止.这种方法对于有n个元素的线性表在最坏情况下需要n次比较.一般来说,如果没有其他的附加信息,在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较.
如果线性表里只有一个元素,则只要比较这个元素和x就可以确定x是否在线性表中.因此这个问题满足分治法的第一个适用条件;同时我们注意到对于排好序的线性表L有以下性质:
比较x和L中任意一个元素L[i],若x=L[i],则x在L中的位置就是i;如果xL[i],同理我们只要在L[i]的后面查找x即可.无论是在L[i]的前面还是后面查找x,其方法都和在L中查找x一样,只不过是线性表的规模缩小了.这就说明了此问题满足分治法的第二个和第三个适用条件.很显然此问题分解出的子问题相互独立,即在L[i]的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件.
于是我们得到利用分治法在有序表中查找元素的算法.
function Binary_Search(L,a,b,x);beginif a>b then return(-1)else beginm:=(a+b) div 2;
if x=L[m] then return(m)
else if x>L[m]
then return(Binary_Search(L,m+1,b,x));
else return(Binary_Search(L,a,m-1,x));end;end;在以上算法中,L为排好序的线性表,x为需要查找的元素,b,a分别为x的位置的上下界,即如果x在L中,则x在L[a..b]中.每次我们用L中间的元素L[m]与x比较,从而确定x的位置范围.然后递归地缩小x的范围,直到找到x.
下面分析该算法的复杂性.设在n个元素的数组中查找x需要的比较次数为T(n),如果每次比较x和L[m]时,总有xL[m],即x根本不在L中,则:
该方程的解为T(n)=O(logn).所以在最坏情况下二分查找法的复杂度为O(logn).