求大神做一个算法分析问题是遍历数组一次,求出数组中的最小元素和次小元素.下面有两个算法,具体程序就不写了,把算法大概的思路写下来,求分析一下,其中数组是a[n],F是最小元素,S是次小元素第一个：F=S=a[0];for(i=0;ia[i]){S=F;F=a[i];}}第二个是：if(a[0]a[i])s=f;f=a[i];elses=a[i];}}大致从以下几个方面分析一下1.这两个算法是否都能够完成只遍历一次就找到最小和次小元素2.这两个算法从本质上来说是否相同3.如果不同哪一个算法更好,执行效率更高
2019-04-13
求大神做一个算法分析
问题是遍历数组一次,求出数组中的最小元素和次小元素.下面有两个算法,具体程序就不写了,把算法大概的思路写下来,求分析一下,其中数组是a[n],F是最小元素,S是次小元素
第一个：
F=S=a[0];
for(i=0;ia[i])
{
S=F;
F=a[i];
}
}
第二个是：
if(a[0]a[i])
s=f;
f=a[i];
else
s=a[i];
}
}
大致从以下几个方面分析一下
1.这两个算法是否都能够完成只遍历一次就找到最小和次小元素
2.这两个算法从本质上来说是否相同
3.如果不同哪一个算法更好,执行效率更高
优质解答
第1个不可以,第2个是可以的
2个算法不相同
可以说2个算法有一个共同点,就是用s来存次小的,用f来存最小的
第一个算法是错的,它检查a[i]的时候,用 f 来衡量是否要修改 s和f 的值
例如：f=1,s=3的时候,如果遇到a[i]=2时,因为2>1,所以没拿2来修改 s和f 的值 明显不对
第二个算法是对的,它检查a[i]的时候,用 S 来衡量是否要修改 S和F 的值
因为S比F大,所以当a[i]比S小时才需要修改S F的值
比知道这个执行效率是什么意思,如果建立在正确的前提下的话,是第2个高,因为第1个是错的,
如果仅仅考虑时间复杂度的话,是第一个效率高,第一个是O(n) 第二个是O(2n) 虽然都可以化成
O(n) 但是毕竟系数不同
第1个不可以,第2个是可以的
2个算法不相同
可以说2个算法有一个共同点,就是用s来存次小的,用f来存最小的
第一个算法是错的,它检查a[i]的时候,用 f 来衡量是否要修改 s和f 的值
例如：f=1,s=3的时候,如果遇到a[i]=2时,因为2>1,所以没拿2来修改 s和f 的值 明显不对
第二个算法是对的,它检查a[i]的时候,用 S 来衡量是否要修改 S和F 的值
因为S比F大,所以当a[i]比S小时才需要修改S F的值
比知道这个执行效率是什么意思,如果建立在正确的前提下的话,是第2个高,因为第1个是错的,
如果仅仅考虑时间复杂度的话,是第一个效率高,第一个是O(n) 第二个是O(2n) 虽然都可以化成
O(n) 但是毕竟系数不同