- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法分析考试题_48263
给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) (分治法)
算法思想
用分治法求最大值和次大值首先将问题划分,即将划分成长度相等的两个序列,递归求出左边的最大值次大值,再求出右边的的最大值次大值,比较左右两边,最后得出问题的解。
b、复杂度分析:
把问题划分为左右两种的情况,需要分别递归求解,时间复杂度可如下计算:
有递推公式为:
T(n)=1 n=1
T(n)= 2T(n/2)+1 n1
所以,分治算法的时间复杂度是n+[logn]-2,当n为奇数时,logn取上线,当n为偶数时,logn取下线。//不知道为什么会-2!
C、代码实现:
#include stdio.h
int a[100];
void maxcmax(int i,int j,int max,int cmax)
{
int lmax,lcmax,rmax,rcmax;
int mid;
if (i==j)
{
max=a[i];
cmax=a[i];
}
else if (i==j-1)
if (a[i]a[j])
{
max=a[j];
cmax=a[i];
}
else
{
max=a[i];
cmax=a[j];
}
else
{
mid=(i+j)/2;
maxcmax(i,mid,lmax,lcmax);
maxcmax(mid+1,j,rmax,rcmax);
if(lmaxrmax)
if(lcmaxrmax)
{
max=lmax;
cmax=lcmax;
}
else
{
max=lmax;
cmax=rmax;
}
else
if(rcmaxlmax)
{
if(rmax==rcmax)
{
max=rmax;
cmax=lmax;
}
else
{
max=rmax;
cmax=rcmax;
}
}
else
{
max=rmax;
cmax=lmax;
}
}
}
int main()
{
int n;
int max,cmax;
printf(输入数组长度);
scanf(%d,n);
printf(输入数组:\n);
for(int i=0;in;i++)
{scanf(%d,a[i]);}
maxcmax(0,n-1,max,cmax);
printf(最大数为 %d\n,max);
printf(次大数为 %d\n,cmax);
return 0;
}
C、运行结果为
求数列的最大子段和(要求时间复杂为nlogn) (算法设计与分析 吕国英 清华大学出版社 135页 4..3.3 二分法变异) (分治法) (也可用动态规划算法 参看递归王晓东计算机算法设计与分析第三版p61页)
a、基本思想:
用分治法求最大子段和首先将问题划分,即将一直序列划分成长度相等的两个序列,
这时会出现3种情况,即①最大子段和在第一个序列,②最大子段和在第二个序列和③ 最大子段和在第一个序列与第二个序列之间。然后,将3种情况的最大子段和合并,取三者之中的最大值为问题的解。
b、复杂度分析:
对应划分得到的情况①和②,需要分别递归求解,对应情况③,两个并列的for循环的时间
复杂度是O(n),所以有递推公式为:
T(n)=1 n=1
T(n)= 2T(n/2)+n-1 n1
所以,分治算法的时间复杂度是O(nlogn)
c、代码实现
#includeiostream.h
#define m 10
int MaxSubSum(int a[],int left,int right)
{
int sum=0;
if(left==right) sum=a[left]0?a[left]:0;
else
{
int i=(left+right)/2;
int max1=MaxSubSum(a,left,i);
int max2=MaxSubSum(a,i+1,right);
int sum1=0,sum2=0;
for(int j=i;j=left;j--)
{
sum1=sum1+a[j];
if(sum1sum2)
sum2=sum1;
}
您可能关注的文档
- 科学发展 标本兼治_33473.doc
- 科创贷产品介绍_33437.ppt
- 科学发展观与潮州市庵埠镇经济的实践_33477.doc
- 科学发展、赶超跨越(党代会工作报告)_33474.doc
- 科学发展观指导下的城市建设_33480.doc
- 科学发展观视野中的大学生思想政治教育_33476.ppt
- 科学宗教艺术的作用关系与哲学启示_33500.ppt
- 科学期末复习题3-6下_33489.doc
- 科学新知_33495.doc
- 科学研究方法谈20071030_33497.ppt
- 《GB/T 32151.42-2024温室气体排放核算与报告要求 第42部分:铜冶炼企业》.pdf
- GB/T 32151.42-2024温室气体排放核算与报告要求 第42部分:铜冶炼企业.pdf
- GB/T 38048.6-2024表面清洁器具 第6部分:家用和类似用途湿式硬地面清洁器具 性能测试方法.pdf
- 中国国家标准 GB/T 38048.6-2024表面清洁器具 第6部分:家用和类似用途湿式硬地面清洁器具 性能测试方法.pdf
- 《GB/T 38048.6-2024表面清洁器具 第6部分:家用和类似用途湿式硬地面清洁器具 性能测试方法》.pdf
- 《GB/T 18238.2-2024网络安全技术 杂凑函数 第2部分:采用分组密码的杂凑函数》.pdf
- GB/T 18238.2-2024网络安全技术 杂凑函数 第2部分:采用分组密码的杂凑函数.pdf
- 《GB/T 17215.686-2024电测量数据交换 DLMS/COSEM组件 第86部分:社区网络高速PLCISO/IEC 12139-1配置》.pdf
- GB/T 13542.4-2024电气绝缘用薄膜 第4部分:聚酯薄膜.pdf
- 《GB/T 13542.4-2024电气绝缘用薄膜 第4部分:聚酯薄膜》.pdf
文档评论(0)