1。 最坏情况下 3n/2-2 次比较可以得到数组的最大值和最小值
max[n/2] min[n/2]
a[1....n] 可以 a[1] a[2] 比较得到 max[1] min[1] ,
同理 ,可以得到 max[] min[] 的值比较次数 n/2
max[] 中得到最大值 n/2-1
min[] 中得到最小值 n/2-
则总共 n/2+n/2+n/2-1-1 比较次数
import javax.swing.JOptionPane;
public class two15{
public static void main(String args[])
{
int a[]=new int[50];//
int min[]=new int[25];//
int max[]=new int[25];//
int n=0,i=0,k=1;
String num;
String aa[]=new String[50];
num=JOptionPane.showInputDialog("enter the total num of the array");
n=Integer.parseInt(num);
//单个数不进行比较
if(n!=1){
for(i=0;i<n;i++)
{
aa[i]=JOptionPane.showInputDialog("请输入数组的每个元素");
a[i]=Integer.parseInt(aa[i]);
}
//用分治法把N个数分成2/N组 每组两个进行比较,把小的放在MIN,大的放在MAX
//最差情况下比较N/2次
for(i=1;i<(n/2)*2;i=i+2)
{
if(a[i-1]<=a[i])
{
min[k-1]=a[i-1];max[k-1]=a[i];k++;
}
else
{
min[k-1]=a[i];max[k-1]=a[i-1];k++;
}
}
/*在MAX中找出最大的,在MIN中找出最小的
*最差情况下比较2*(N/2-1)次
*/
int maxm=max[0],minm=min[0];
for(k=1;k<n/2;k++)
{
if(max[k]>maxm) maxm=max[k];
if(min[k]<minm) minm=min[k];
}
if(n%2!=0)//N为奇数时,还要和最后一个数比较
{
if(a[n-1]>maxm) maxm=a[n-1];
if(a[n-1]<minm) minm=a[n-1];
}
JOptionPane.showMessageDialog(null,
"最大的数是"+maxm+"最小的数是"+minm,
"result",JOptionPane.INFORMATION_MESSAGE);
}
else JOptionPane.showMessageDialog(null,
"一个数无须查找","警告!"
,JOptionPane.INFORMATION_MESSAGE);
}
}
2. 得到数组的最大值次大值比较次数最多 n+log(n) -2
假设 a5 最大 ,则得到一个锦标赛树
a5
a1 a5
a1 a4 a5
a1 a2 a3 a4 a5 a6
做n/2次比较,可以得到n/2个较小的数。重复做一直到只剩下一个数,即最小值。将最小值换成负无穷,沿着最小值的比较路线走上去,可以得到次小值。
循环直到产生最小值的过程会产生一棵树,而且是完全二叉树,每次比较都会产生出一个内部结点,因此总的比较次数就是树中内结点的个数。完全二叉树最坏情况下是满二叉树,有n个叶结点,因此高为O(log(n)),
内结点个数是n-1。
等比数列求和:
1+2+4+8...+n = (1-2^(log_2_n+1)) = 2n-1
第二次沿最小数的比较路径走上去,所做的比较次数就是这棵树的高度。
一共 logn 层
则要得到 次大值 , 从最底层 ,a5 = 负无穷 ,按照原先 a5 上升的路再走一遍 ,每次上升一层,到顶层
即为次最大值
比较 logn -1 次
- 大小: 13.7 KB
- 大小: 13.5 KB
- 大小: 15 KB
分享到:
相关推荐
c++实现获取一维数组极值点。可以通过调整阈值,改变极值点获取值
c++实现获取一维数组极值点。可以通过调整阈值,改变极值点获取值
findExtrema.m 旨在从 N 维数组中查找极值点(最小值和最大值)。 这个实现的运行速度比http://www.mathworks.com/matlabcentral/fileexchange/12275-extrema-m-extrema2-m快得多,它使用了 Mathworks 的 Image ...
c++实现获取一维数组极值点。可以通过调整阈值,改变极值点获取值
本程序使用matlab求取二维数组的极大值与极小值
4.7 函数极值点 4.8 数值积分 4.9 随机数据的统计描述 4.10 多项式拟合和非线性最小二乘 4.11 插值和样条 4.12 样条函数及其应用 4.13 Fourier分析 4.14 常微分方程 4.15 稀疏矩阵 第五章 符号计算 5.1 符号对象和...
matlab 矩阵数组
这是两个相似的程序。 它们用于在一组 x,y 数据中查找极值点的坐标和索引。 它们可用于查找一阶导数为零的位置到获得信号的包络之间的目的。 示例在所附的 pdf 文件中给出
最后,它返回序列中极端位置的元胞数组。 元胞数组仅由两个元胞组成。 第一个包含最大值的逻辑向量,另一个包含最小值的相似向量。 如果向量的相邻元素中存在更多相等的值,则只返回一个位置。 还关注低内存需求和...
移动数组元素到另一数组 大小写转换 删除指定的字符 子字符串查找 字符统计 字符串逆置 回文数 数字字符串转换成整数 比较字符串长度 子字符串移动 字符串连接 在链表中查找元素 结构体和链表排序 求链表中的极值
QDX是一个二行二列的数组,第一列代表极值所在的位置,第二列代表极值 弯矩极值及位置MDX MDX是一个二行二列的数组,第一列代表极值所在的位置,第二列代表极值 子程序 集中力偶对弯矩贡献的子函数QMM 集中力对...
Matlab实现的HHT中的镜像对称延拓
这三个函数计算二维单元格(或数字)矩阵中所有数字的最小值和最大值。 单元格矩阵可能包含其他单元格矩阵、数字矩阵或它们的混合。 包含的单元格矩阵又可能包含其他单元格矩阵,等等。 搜索由嵌套调用执行,因此...
代码可能包括字符串匹配(KMP/Boyer-Moore)、编辑距离、后缀数组等算法。 数据结构:组织和存储数据的方式,如数组、链表、栈、队列、树、图等。代码实现这些结构的基本操作,以支持高效的数据处理。 数论:研究...
第12章 极值问题的求解 12.1 一维极值连分式法 12.1 n维维极值连分式法 12.3 不等式约束线性规划问 12.4 求n维极值的单行条优法 12.5 求约束条件下n维极值的复形调优法 第13章 数学变换与滤波 13.1 傅立叶级数逼近 ...
将驾驶室声环境听觉系统的振动认知以数字化进行表现,利用MATLAB软件解析数据,编制波形图,同时结合综合波形图对比分析、数据极值分析、相关性分析和人体听觉差异实验研究后证明:声环境波形图具有一定的相似性,声环境...
(通过与顶点关联的两条边的另外两个顶点是不是在交点同一侧来判断一个顶点是否为极值点) 顶点为局部极值:交点被连续记录两次 顶点不是局部极值:交点只被记录一次 运行结果 注:本思路与介绍图片均来自CSDN上博主...
实例004——使用函数模板实现不同数据类型的极值函数 实例005——使用C++实现格式化数据的IO 实例006——实现数字金额的中文大写转换 实例007——将十进制数转换为二进制输出 实例008——产生随机数 实例009...
实例004——使用函数模板实现不同数据类型的极值函数 实例005——使用C++实现格式化数据的IO 实例006——实现数字金额的中文大写转换 实例007——将十进制数转换为二进制输出 实例008——产生随机数 实例009...
7.4 极值问题的求解算法 215 7.4.1 极值求解算法 215 7.4.2 极值求解示例 217 7.5 特殊函数的计算算法 221 7.5.1 伽玛函数 221 7.5.2 贝塔函数 224 7.5.3 正弦积分函数 228 7.5.4 余弦积分函数 231 7.5.5 ...