第一种方法是进行两次冒泡排序，第一次找出最大的数，需要比较(N-1)次，第二次找出第二大的数，需要比较(N-2)次，所以这种方法总共需要遍历2遍，比较(2N-3)次。第二种方法是声明两个变量a和b，初始化为前两个数，且a&b.然后依次遍历后面的数，如果大于b则替换b，然后调整a和b值，使a&b成立。然后就这样一直进行下去，直到N个数全部遍历完，则b即为所求。这种方法只遍历一遍，但是空间需要额外的两个，且对于大于b数字还需要与a进行再次的比较。最好情况下，a和b恰好是最大值和次大值，此时需要比较的次数最小，算上a和b的初始比较，总共需要(N-1)次。最坏的情况下，a和b恰好是最小值和次小值，此时比较了b之后还需要比较a，那么就退化成第一种算法了。上述两个算法算是可行的。不过，我觉得第二种算法的随机性太大，有没有改进的可能？还有其他更加高效的算法吗？请教各位算法大神。
该问题被发起重新开启投票
投票剩余时间：
之前被关闭原因：
该问题被发起删除投票
投票剩余时间：
距离悬赏到期还有：
参与关闭投票者：
关闭原因：
该问题已经被锁定
锁定原因：（）
保护原因：避免来自新用户不合宜或无意义的致谢、跟帖答案。
该问题已成功删除，仅对您可见，其他人不能够查看。
我这边有一个方案大家探讨一下，由于产生N个数字中，找到最大数字的比较次数为N-1次，这个是不可优化的，可以认为是找出第二大数字的比较次数的下限；这样先将N个数字两两分组，每组取最大值，这样共有N/2+1个组，这样找到最优点需要N-1次比较，但是会剩下N/2+1个点（每组中的最优点，和最大点所在组的两个点），对剩下的N/2+1个数进行比较，产生次最大点需要比较N/2次比较，故总共大约需要比较的次数为3N/2，我们可以将每组中较大的点存在奇数或者偶数位置，从而使得空间复杂度为O(1)；这样实现找到第二个最大点的比较。进而，不考虑空间复杂度的情形下，我们可以进一步减少比较次数，对这N个数进行二分比较，整个比较过程会构建出一个二分的比较树，假定每个数在每轮比较的点都被记录了下来，这样第一轮找到最大点大约需要N-1次比较，而在找到第二大点时，我们可以把和最大点比较过的点集合起来进行比较，树的高度为lgN，所以第二轮比较点的个数为lgN，这样在不考虑空间复杂度的情形下，比较次数恒定为N+lgN，而空间复杂度考虑可以设想用类似静态链表形式实现。可能空间复杂度可以达到O(N)
在找一组数字取第二大数这个问题中其实就是根据先序比较消除冗余匹配的策略，我这边有一个想法虽然和前述方法相比不是在时空复杂度上不是最优，但是可以提供一种思路，若有更好的方法可以基于此进行优化，方法如下：基本思想是：通过一次匹配，利用第一次遍历比较过程中获取的数据间相对大小信息来消除第二次遍历过程中不必要的比较；具体方案：设定一个rank数组，长度为N，对应N个数，每个值表示数组中现在已知比当前数大的数的个数，初始化为0，表示当前已知的比当前数大的数的个数为0个数，这样，先取第一个数和后面的数进行比较，较小数的rank值增1（表示对应数字），若当前数的rank值大于等于2，表示数组中已经有两个数比当前数大，所以这个数不可能为第二大值，抛弃之；检查下一个数，若下一个数的rank值大于等于2，则不进行比较了，继续拿下一个数字进行比较；如此重复，直到有一个数比较完所有数之后rank值为1；经过我用多个序列进行测算，发现最终的匹配次数和冒泡排序一致，为2N-3次，但是空间复杂度为O(N)，有一些退化，但是希望后来有人对这个想法进行优化
说一个思路。1、每两个元素成组比较，需要n/2次——形成数据对；2、数据对比较，按照较大的那个数比较；3、反复2，直至余下的数据只有1个。（当然，不能丢弃之前的比较结果。）这样，构建出一个二叉树。如果一个数据对，连续比较两次都小，那么这个数据对就可以丢弃了。也就是丢弃上面那个树，三层之外的节点。那么余下就是固定比对次数了。2和3的比较次数，应该是O(n)。
我是新手啦，只是来发表一下意见...可能上面已经说了我说的这个方法...但是我有些术语看不懂...我比较直白的表达一次我的想法...
我是觉得...N个数两两比较...大的提取出来...一直比到得出最大的,需要比较N-1次...然后剩下两个最接近最大数的两个数比较...就得出第二大的...一共比较N次...
譬如...1 5 2 6 3 7 4 85 6 7 86 88然后6和7再比一次(最近跟8比较的两个数)牺牲了O(N)个空间...感觉最后的判断有点难写...要不要剩下最后三四个的时候来个冒泡算了...最多也是N+1次?
上面的错了...算出最大的数之后,还要把所有跟最大的数对比过的数搜集起来...再求一次最大数... - -,那就要3N/2次了...没什么用...
&?php $n = rand(100,200);$number = $n;$array = array();for($i=0;$i&$n;$i++){
$array[$i]['number'] = rand();}/*$array2 = $sort($array2);print_r($array2);echo "&br /&";print_r($array);*/$counts = 0;for($i=0;$i&$n;$i=$i+2){
if($i+1&$n){
if($array[$i]['number'] & $array[$i+1]['number']){
$array[$n]['number'] = $array[$i]['number'];
if(!empty($array[$i]['kill'])){
$array[$n]['kill'] = $array[$i]['kill'];
$array[$n]['kill'][] = $i+1;
$array[$n]['number'] = $array[$i+1]['number'];
if(!empty($array[$i+1]['kill'])){
$array[$n]['kill'] = $array[$i+1]['kill'];
$array[$n]['kill'][] = $i;
$counts++;
$n++;}$k = count($array) - 1;$zuida = $array[$k]['number'];/*echo "&br /&";print_r($array);*/$dierda = '';foreach($array[$k]['kill'] as $numbers){
$dierda = (empty($dierda))?$array[$numbers]['number']:$
$dierda = ($array[$numbers]['number'] & $dierda)?$array[$numbers]['number']:$
$counts++;}$counts = count($array) - $number + (count($array[$k]['kill']) - 1 );echo "N:".$echo "&br /&";echo "count:".$echo "&br /&";/*echo "&br /&";echo $echo "&br /&";echo $*///最后$array里面个数 - $numbers 其实就是 N-1,
$array[$k][kill]里面的个数其实就是 floor(log2(N)) 最后还要减1;
还有人看我这个吗?求顶啊!!!计算次数是 N-1 + log2(N) - 1 呢...就是记录了每个数打败了谁,每个数最多比较floor(log2(N))次...提取出来再求最大值...那就比较次数很少了...就是浪费了很多空间...N-1 + log2(N) - 1啊~~给分啊~~~
我用的是第二种方法。代码如下：
#include&stdio.h&
#include&stdlib.h&
int find(int *a,int n)
int second=*(a+i);
while(i&n)
if(*(a+i)&second)second=*(a+i);
int findsecondmaxvalue(int *a,int n)
int first=*(a+i);
int second=*(a+i);
while(i&n)
if(*(a+i)&first)
first=*(a+i);
else if(*(a+i)==first)
//do nothing
else if(*(a+i)&first&&*(a+i)&second)
second=*(a+i);
//do nothing
//最大值和次大值相等(只可能出现在数组的第一个元素)
if(first==second)
second=find(a,n);
int main()
int a[]={9,5,1,7,4,6,2,3,8};
int n=sizeof(a)/sizeof(a[0]);
int second=findsecondmaxvalue(a,n);
printf("次大值=%d\n",second);
把数列分成两份，分别取最大值，然后再比较两个最大值……可以不？
基数排序，数据规模不大的情况下用全覆盖基数，一遍搞定，空间换时间的经典解决方案。这类问题数据规模是性能的一个重要制约因素，不同规模有不同的解决方案的，不能一概而论，毕竟每种方案的最优覆盖领域是不一样的~~
这不是数据结构堆排序吗？？取出前两个根节点就是了。
我的方法是参考《编程珠玑》第一章解决排序的方法，使用位图排序。前提条件是知道N的集合范围，此方法适合用于有限和稠密集合，遍历[N+1,2N－1]次就出结果，缺点是很占内存空间（N要小于1亿）。
解题步骤：假设N的集合范围[0,5]，N个数为{2,4,5,1}初始一个一维数组｛0，0，0，0，0，0｝。然后遍历N次，每次把数值所对应的数组下标值设置为1，遍历后数组为{0,1,1,0,1,1}.这样就可以从数组末尾倒数第二个开始向前找，只要遇到值为1，就输出数组下标值。
所以最好的结果是在数组N-1个找到，最坏结果是在第一个找到。所以程序查找次数为[N+1,2N－1]。
想了一个方法首先将进行N个数二分，分别在每组中利用冒泡排序选出最大的数，然后比较这两个最大的值，这样比较下来是N-1次，然后选择最大的所在的组，去除这个最大值，剩余的N/2-1个数再冒泡排序一次，得到最大值这个最大值与另外一组的最大值进行比较，如果这个值较大，这个就是第二大的，否则，另外一组的最大值是第二大的。这部分比较的次数是N/2-1次综合起来是比较了3N/2-2次相对两次冒泡排序，次数有所减少。
我觉得应该使用堆排序的方法。使用大顶堆。
我今天在网上闲逛，无聊之中发现一个叫&左耳朵耗子&的人在酷壳上写的一篇博文。地址如下：
所以专门跑来贴链接。希望对你有所帮助。
我觉得可以考虑使用经典快速排序中使用到的parition算法，就是划分法，每次找当前数组中间的数，然后丢弃一半，继续找，直到找到k=1(下标从0算起)，就可找到第2大的那个元素。时间复杂度是o(N)
可使用桶排序的思路。扫一遍数据，并把它们扔到各自的桶中。如果桶是升序的，那最大和第二大的数就在最后那个桶或倒数第二个非空桶中。如果该桶中的数据仍然很多，可再次桶排序，直至求出第二大数，或可以接收其他排序方式为止。
效率的话，决定于如何根据具体的数据来设计&桶&。因为桶排序一般不需要比较，所以只要设计好&桶&，效率就应很高。
桶排序有两个特例，即基数排序和计数排序。
不是您所需，查看更多相关问题与答案
德问是一个专业的编程问答社区，请
后再提交答案
关注该问题的人
共被浏览 (14128) 次计算机执行下面的语句时,语句s的执行次数为_____________.for(i=l;i=i;j--) 【答案】(n+3)(n-2)/2
嘪嘠嘠嶪404
答案就是 (n+3)(n-2)/2群举法.n=2的时候为0n>2的时候 3+4+.n-2次得出：(3+n)*(n-2)/2
啊 我忘了写为什么。。。
群举n的值然后套进去啊
n等于2时，
for(i=1;i=i;j--) // 执行0次
n等于3的时候
for(i=1;i=i;j--) //s执行3次
。。。。。。。
额还是不懂。。。i<3-1哪儿来的呀？
额 我还以为是1.应该是1吧 不是l吧
啊啊我错了，没有-1.
为您推荐：
其他类似问题
扫描下载二维码& 知识点 & “在数学活动课上，老师要求同学们先做下面的...”习题详情
0位同学学习过此题，做题成功率0%
在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； 第1次分割：将原等腰梯形纸片分割成3个等边三角形； 第2次分割：将上次分割出的一个等边三角形分割成3个全等的等腰梯形，然后将刚分割出的一个等腰梯形分割成3个等边三角形； 以后按第2次分割的方法进行下去…请解答下列问题： （1）请你在图2中画出前两次分割后的图案； （2）若原等腰梯形的面积为a，请你通过操作、观察，将第2次，第3次分割后所得的一个最小等边三角形的面积分别填入下表： &
分割次数（n）
一个最小等边三角形的面积（S）
（3）请你猜想，分割所得的一个最小等边三角形面积S与分割次数n有何关系？（请直接用含a的式子表示，不需写推理过程）　&
本题难度：
题型：解答题&|&来源：网络
分析与解答
习题“在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； 第1次分割...”的分析与解答如下所示：
仔细分析题意，根据数据首先应找出哪些部分发生了变化，是按照什么规律变化的，从而用式子表示．
解： （1）． （2） 根据图形，得到第二次分割得到的最小的等边三角形面积为(
)3a； 同理第三次分割得到的最小等边三角形的面积为(
)5a； 故答案为：(
)5a； （3）归纳总结得到：S=
找到答案了，赞一个
如发现试题中存在任何错误，请及时纠错告诉我们，谢谢你的支持！
在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； ...
错误类型：
习题内容残缺不全
习题有文字标点错误
习题内容结构混乱
习题对应知识点不正确
分析解答残缺不全
分析解答有文字标点错误
分析解答结构混乱
习题类型错误
错误详情：
我的名号（最多30个字）：
看完解答，记得给个难度评级哦！
经过分析，习题“在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； 第1次分割...”主要考察你对“第6章 特殊平行四边形与梯形”
等考点的理解。
因为篇幅有限，只列出部分考点，详细请访问。
第6章 特殊平行四边形与梯形
与“在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； 第1次分割...”相似的题目：
[2014o鄂州o中考]如图所示，小机车通过滑轮组提升重物，机车的最大输出功率为10kw 重物重3500N，动滑轮重500N．机车所受摩擦阻力不计，绳重及滑轮转动时摩擦忽略不计．（1）滑轮组的机械效率是&&&&%．（保留1位小数）（2）若要求重物以1m/s匀速提升，则机车能提升重物的最大重量为&&&&N．
[2014o南宁o中考]图甲是建造大桥时所用的起吊装置示意图，使用电动机和滑轮组（图中未画出）将实心长方体A从江底竖直方向匀速吊起，图乙是钢缆绳对A的拉力F1随时间t变化的图象．A完全离开水面后，电动机对绳的拉力F大小为6.25×103N，滑轮组的机械效率为80%，已知A的重力为2×104N，A上升的速度始终为0.1m/s．（不计钢缆绳与滑轮间的摩擦及绳重，不考虑风浪、水流等因素的影响），求：长方体A完全离开水面后，在上升过程中F的功率为（
）．2300W2400W2500W2600W
[2013o北京o中考]如图是利用滑轮组匀速提升水中圆柱体M的示意图，滑轮组固定在钢架上，滑轮组中的两个滑轮质量相等，绕在滑轮组上的绳子能承受的最大拉力为900N，连接圆柱体M与动滑轮挂钩的绳子能承受的最大拉力为3000N．圆柱体M高为3m，底面积为0.02m2，密度为4.5×103kg/m3．在绳端拉力F作用下，圆柱体M从其下表面距水面15m处匀速上升到其上表面与水面相平的过程中用了3min，在这个过程中，拉力F的功率为160W，滑轮组的机械效率为η，钢架对定滑轮的拉力为T．在圆柱体M被缓慢拉出水的过程中，圆柱体M的下表面受到水的压强为p．不计绳重、轮与轴的摩擦及水的阻力，g取10N/kg．下列选项中正确的是（　　）压强p的最小值为15000Pa拉力T的大小为2700N拉力F的大小为640N滑轮组的机械效率为90%
“在数学活动课上，老师要求同学们先做下面的...”的最新评论
该知识点好题
该知识点易错题
欢迎来到乐乐题库，查看习题“在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； 第1次分割：将原等腰梯形纸片分割成3个等边三角形； 第2次分割：将上次分割出的一个等边三角形分割成3个全等的等腰梯形，然后将刚分割出的一个等腰梯形分割成3个等边三角形； 以后按第2次分割的方法进行下去…请解答下列问题： （1）请你在图2中画出前两次分割后的图案； （2）若原等腰梯形的面积为a，请你通过操作、观察，将第2次，第3次分割后所得的一个最小等边三角形的面积分别填入下表：
分割次数（n）
一个最小等边三角形的面积（S）
（3）请你猜想，分割所得的一个最小等边三角形面积S与分割次数n有何关系？（请直接用含a的式子表示，不需写推理过程）”的答案、考点梳理，并查找与习题“在数学活动课上，老师要求同学们先做下面的“循环分割”操作，然后再探索规律： 如图1，是一等腰梯形纸片，其腰长与上底长相等，且底角分别60°和120°，按要求开始操作（每次分割，纸片均不得留有剩余）； 第1次分割：将原等腰梯形纸片分割成3个等边三角形； 第2次分割：将上次分割出的一个等边三角形分割成3个全等的等腰梯形，然后将刚分割出的一个等腰梯形分割成3个等边三角形； 以后按第2次分割的方法进行下去…请解答下列问题： （1）请你在图2中画出前两次分割后的图案； （2）若原等腰梯形的面积为a，请你通过操作、观察，将第2次，第3次分割后所得的一个最小等边三角形的面积分别填入下表：
分割次数（n）
一个最小等边三角形的面积（S）
（3）请你猜想，分割所得的一个最小等边三角形面积S与分割次数n有何关系？（请直接用含a的式子表示，不需写推理过程）”相似的习题。算法导论 9.1-1 求第二小元素 - [ 《算法导论》答案 ] - 看云
一、题目描述
证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）
二、常规方法
使用两次for循环，分别将数组从前往后扫描。
第一扫次扫描过程中，不断记录和更新当前情况下的最小元素。
第二次和扫描过程中，不断记录和更新当前情况下的第二小元素。
伪代码如下：
Int min = array[0], minId = 0;
FOR i in [1, n), i++
IF (array[i] & min)
Min = array[i];
Int secId = ( minId = 0 ? 1 : 0 ), sec = array[secId];
FOR i in [secId+1, n), i++
IF (i = minId) CONTINUE
IF ( array[i] & sec )
Sec = array[i];
三、常规方法的比较次数
第一个循环过程中，每次循环内部的比较次数为1次，循环次数即扫描的元素个数为n-1，因此比较第一次循环过程的次数是n-1。
第二个循环过程中，每次循环内部的比较次数也中1次，循环次数即扫描的元素个数为n-2（去去掉了最小元素），因此比较第二次循环过程的次数是n-2。
常规方法的比较次数为(n-1)+(n-2)，即2n-3次。
四、方法改进一
在第一次循环求最小元素的过程时，对元素内容一无所知，因此n-1次的比较是必要的，难有优化空间。
在第二次循环求第二小元素的过程时，对元素的内容不再是一无所知。如果充分利用第一次循环所得到的信息，也许可以省掉第二次循环中不必要的比较。
本次优化的重点在第二次循环。
五、第一次循环的可用信息
如果 a & b 且 b & c，那么不需要经过a和c的比较就可以知道 a & c。
假设数组中的元素为a, b, c, d, e, f, g … 。
当扫描到元素d时，最小元素为c，可知 a & c, b & c, d & c。
当扫描到元素e时，最小元素变为了e，可知 e & c。
那么 a & c & e, b & c & e, d & c & e，
a,b,d不可能是第二小元素或最小元素
c是第二小元素，e是最小元素
接着上文继续扫描，当扫描到元素e时，最小元素为e，结论如上。
当扫描到元素g时，最小元素仍为e，可知f & e, g & e。
那么a & c & e, b & c & e, d & c & e, f & e, g & e
a, b, d不可能是第二小元素或最小元素
c, f, g有可能是第二小元素，e是最小元素
六、根据第一遍的可用信息作第二次循环
假设已经作过第一次扫描，找到了最小元素，为e，现在要充分利用第一次扫描的信息作第二次扫描。
这一次，我们并不是对除了e以外的所有元素扫描，而是只选择其中一部分。选择的依据来自于上一节的内容。
我们大胆猜测，第二小元素的候选值是那些在第一次扫描过程中与e做过直接比较的元素。
证明如下：
在第一次循环的过程中，第二小元素一定与最后元素e直接比较过。
第一种情况，在数组顺序中，第二小元素在e之前出现
在出现之前，第二小元素一直都是被当作当前状态的最小元素，遇到e之后，因为与e比较失败，最小元素才变成了e。
第二种情况，在数组顺序中，第二小元素在e之后出现
e会与后面的每一个元素直接比较。
没有与最小元素e直接比较过的元素一定不会是第二小元素
证明过程与1相反，略。
七、方法改进一的伪代码
第一次扫描的比较没有改变，只是每次比较的过程记录下来，以便第二次扫描的时候知道某个元素曾经和谁做过比较。
Int min = array[0], minId = 0;
FOR i in [1, n), i++
IF (array[i] & min)
Min = array[i];
QUEUE[i].PUSH(min);
QUEUE[minId].push(array[i]);
第二次扫描时，仅取出最小元素所对应的队列元素做比较
Int secId = QUEUE[minId].ELEMET(0)
FOR i in [1, QUEUE[minId].size), i++
IF (QUEUE[minId].ELEMET(i) & sec )
Sec = QUEUE[minId].ELEMET(i);
八、方法改进一的比较次数
第一次扫描的次数仍然为n-1，主要差别在于第二次扫描。
第二次扫描也是FOR循环，每次循环内部的比较次数是1次，总的比较次数取决于 队列中元素的个数。假设个数为m，那么比较次数为m-1。
为了计算m，我画了这样一个图。叶子结点为数组中的元素。没有标字母的节点表示其它两个孩子结点的比较结果。画出这样的图，任假设一个结点为最小元素，都能很清晰地看出其队列中元素的个数。
我们取两种最极端的情况：
假如最小元素为A，那么其队列中的元素为B, C, D，3个元素
假如最小元素为D，那么其队列中的元素为A, B, C中的最小值，1个元素。
结论，方法改进一的比较次数最多为2n-3，最少为n-1，取决于最小元素所在位置。
九、方法改进二
虽然方法改进一相比于常规方法是有了改善，但最多比较次数仍然需要2n-3次，未达到题目所要求。这次我们方找最小元素的过程入手。
上文已经说过，求最元素的过程到少要经过n-1次比较，这一点是难以改变的。但我们仍可以通过调整第一次遍历方式，使留给第二次遍历更多有用的信息。尽量让每个元素与其它元素的比较次数平均化，这样，当任意一个元素成为最小元素时，它的队列的元素个数都不会太多。仍然以上文的图为例：
方法改进一的第一次遍历可以画成这一样的图，数组中的每一元素是这个二叉树的叶子结点。假如某一个元素是最小元素，那么它的队列的元素即该叶子结点的高度。只要将树平均化，如下图所示，保证每一个叶子的高度都不会太高，那么每个元素对应的队列都就不会太大。
十、方法改进二的比较次数
方法改进二的伪代码比较复杂，请大家直接阅读源代码。
对于第一次遍历，比较次数仍为n-1。
对于第二次遍历，比较次数取决于第一次遍历转化生成的二叉树的高度h。
将二叉树平均化以后，树的高度为h= ceil[lgn]。
结论，方法改进二的比较次数最多为n+ ceil[lgn]-2。
十一、代码
页面正在加载中