给定n个元素,要求解其中第k小的元素,一般采用先排序后然后直接得结果的过程。在数据量小的情况下没问题,时间复杂度是O(n*logn). 但是当数据量非常大的时候就要考虑是否有更好的算法来代替全局排序。
这里,采用剪枝策略,即如果要在线性时间内得到问题的解,必须在每次迭代的过程中用O(n)的时间剪去部分元素,使得在下次迭代过程中不参与比较。
《算法设计与分析导论》一书给出了一个比较经典的线性时间复杂度下的求解算法。
核心思想:
我们以每5个元素为子集划分源数组,然后对每个子集排序求出中位数,这样的中位数集合组成一个新的序列M,对M递归的求解其中位数p,得到的p即为划分点。p将源数组划分为3部分:
* s1:所有小于p的元素
* s2: 所有等于p的元素
* s3: 所有大于p的元素
下一轮迭代的时候根据输入的level参数判断该剪去哪部分元素,具体参见代码实现部分。
这样,每一轮迭代至少剪去n/4的元素(画个中位数排列的图出来就容易看出),则最坏情况下的时间复杂度表示为:
T(n)=T(3n/4)+T(n/5)+O(n)
其中
* T(3n/4)是下一轮迭代的最大数据量情况下的时间复杂度
* T(n/5)是求寻找中位数组成集合的中位数的时间复杂度
*
根据递推公式可以求得该算法的时间复杂度是O(n)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ElementsHandler {
/**
* 找出浮点型数组array的第level小元素
* 核心思想:如果要在线性时间内得到问题的解,必须在每次迭代的过程中用O(n)的时间剪去部分元素,使得在下次迭代过程中不参与比较
* 我们以每5个元素为子集划分源数组,然后对每个子集排序求出中位数,这样的中位数集合组成一个新的序列M,对M递归的求解其中位数p,得到的p
* 即为划分点。p将源数组划分为3部分:
* s1:所有小于p的元素
* s2: 所有等于p的元素
* s3: 所有大于p的元素
*
* 下一轮迭代的时候根据输入的level参数判断该剪去哪部分元素,具体参见代码实现部分。
*
* 这样,每一轮迭代至少剪去n/4的元素,则最坏情况下的时间复杂度表示为:
* T(n)=T(3n/4)+T(n/5)+O(n)--其中T(3n/4)是下一轮迭代的最大数据量情况下的时间复杂度,
* T(n/5)是求寻找中位数组成集合的中位数的时间复杂度
*
* 可以求得
* 找出浮点型数组array的第level小元素的算法时间复杂度是O(n)
* @param level
* @param array
* @return
*/
public static double calcValueLevel(int level, Double[] array)
{
if(array==null||level<=0||level>array.length)
throw new IllegalArgumentException("Wrong input!");
int len=array.length;
if(len==1)
return array[0];
int blockSize=5;//以每5个元素为子集划分源数组
int blocks=len%blockSize==0?len/blockSize:len/blockSize+1;
List<Double> midList=new ArrayList<Double>();
for(int i=0;i<blocks;i++)
{
int start=i*blockSize;
int end=sortBlock(array, start, blockSize);
midList.add(array[start+(end-start-1)/2]);//添加各个5元素且排好序组的中位数(偶数个的情况取第N/2个数,注意这里不存在偶数情况,因为以5个元素为单位划分)
}
Double[] midsArray=null;
midsArray=midList.toArray(new Double[midList.size()]);//获得每5个元素组中的中位数组成的数组
double mmidValue=calcValueLevel((midList.size()+1)/2,midsArray);//递归求解[n/5]组数的中位数组成的集合的中位数
List<Double> l_list=new ArrayList<Double>();
List<Double> e_list=new ArrayList<Double>();
List<Double> h_list=new ArrayList<Double>();
for(int i1=0;i1<len;i1++)
{
if(array[i1]<mmidValue)
{
l_list.add(array[i1]);
}
else
{
if(array[i1]>mmidValue)
h_list.add(array[i1]);
else
e_list.add(array[i1]);
}
}
if(level<=l_list.size())
{
Double[] lArray=null;
lArray=l_list.toArray(new Double[midList.size()]);
return calcValueLevel(level,lArray);
}
else
{
if(l_list.size()+e_list.size()>=level)
{
return mmidValue;
}
else
{
Double[] hArray=null;
hArray=h_list.toArray(new Double[h_list.size()]);
return calcValueLevel(level-l_list.size()-e_list.size(),hArray);
}
}
}
/**
* 在blockSize比较小的情况下,这里针对5个单位排序,任意方法都可以,我选择简单的选择排序算法
* @param array
* @param start
* @param blockSize
*/
public static int sortBlock(Double[] array, int start, int blockSize) {
int end=(start+blockSize)>array.length?array.length:start+blockSize;
//选择排序:小->大
for(int i=start;i<end-1;i++)
{
for(int j=i+1;j<end;j++)
{
if(array[i]>array[j])
{
double temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
return end;
}
/**
* @param args
*/
public static void main(String[] args) {
int level=10;
Double[] d=new Double[]{2.1,1.2,3.1,1.2,2.1,7.3,4.8,5.3,5.2,2.1,10.0,0.1,-1.1};
double res=ElementsHandler.calcValueLevel(level,d);
System.out.println("第"+level+"小的数是:"+res);
Arrays.sort(d);
System.out.println(Arrays.toString(d));
}
}
分享到:
相关推荐
对普通用户来说,大型线性方程组的求解是一个困难问题,可通过外包计算进行解决。现有的大型线性方程组外包求解方案计算效率较低或计算结果无法完全验证。提出了一个可验证的大型线性方程组求解的外包计算协议。在...
序列复杂度的求解的matlab源程序,给定序列,返回其复杂度
序列S的k错线性复杂度曲线的第m个跃变点对应的km值和对应km错线性复杂度LCm,称为序列S的m紧错线性复杂度。通过使用简洁的cost二维结构,给出了周期为2n的二元序列的紧错线性复杂度算法,并证明具有Stamp-Martin模式...
常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶 O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶 O(2^n)。 "定义:如果一个问题的规模是n,解这一...
N皇后问题,完全原创,感觉挺不错的,哈哈
内容描述:非线性特征:样本熵、模糊熵、排序熵、复杂度[已测试] 1.APPEN m 2.Fuzen. m 3.Fuzzy Entropy. m 4.LZC m 5.Peren. m 6.Sampleen m 7.sampleen plus m 8.Sampleentropy m 9.说明:系统是基于Matlab 2016b...
论文研究-基于层次粒子群算法的非线性双层规划问题求解策略.pdf, 在交通与物流网络系统规划中的许多决策问题可以归结为双层规划模型, 这类问题大多属于非凸优化问题. ...
目的 针对传统的求解线性最小二乘问题方法的计算、存储复杂度大,不适于大规模问题的缺点,提出...结论数值实验表明新算法和相关算法相比求解精度可接受,但大大减少求解时间且在同等计算平台下可处理更大规模的问题。
求最小生成树(简称MST)是一个经典的图论问题,已存在许多近似线性时间复杂度的快速求解算法可以解决。然而,度约束的最小生成树的求解则被证明是一个NP-完全问题,目前仍无法找到多项式时间复杂度的求解算法。本文用...
我们考虑具有布尔和连续状态的离散时间动态系统,其中连续状态在...我们的方法的复杂度在时间范围内呈线性增长,并且随着状态维度呈立方体增长,与标准卡尔曼滤波器相同。数值实验表明,该方法在实际应用中表现良好。
本文通过建立连续可分离的非线性多维背包问题的结构性质,开发了一种用于求解一般结构的连续非线性多维背包问题的多层二元解法。 计算复杂度是变量数量的多项式。 我们提供了两个示例来说明我们的方法的一般应用,...
关于序列二次规划_SQP_算法求解非线性规划问题的研究
非线性整数规划是一个具有指数复杂度的NP问题,如果约束较为复杂,Matlab优化工具箱和一些优化软件比如lingo等,常常无法应用,即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。...
程序可以求解线性方程组,迭代速度相对较快,复杂度O(Nlog(N))
(2)在相同的规模n 下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 (3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B.(1),...
针对信号处理、系统识别等领域中涉及到的无约束非线性lp问题,为减小由于二进制编码的舍入误差对该问题计算结果的影响,对求解该问题的极大熵方法进行了区间扩张。证明了区间扩张后的极大熵函数至少具有二阶收敛性,...
提出了一种基于认知无线电(CR)技术的跨层传输控制方案,该方案在满足与主用户冲突率约束及缓存器状态...仿真结果表明,方案能够在满足约束的条件下最小化功率消耗,而且低复杂度的求解方法对该方案性能的影响很小。
对于区间[a,b]上连续不断且f(a)·f(b)的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法...直到找到为止,时间复杂度:O(log(n))
用于执行矩阵向量乘积之类的矩阵运算,以接近线性的复杂度求解和行列式计算(对于类似于HODLR的矩阵,HODLRlib HODLRlib是一个灵活的库,用于执行矩阵向量乘积之类的矩阵运算,求解以及近似线性复杂度的行列式计算...
立了极大极小任务分配问题的混合整数线性规划模型,提出一种矩阵作业解答。并与穷举解及混合整数线性规划解 的计算复杂度进行了比较.理论分析和数值试验表明矩阵作业法对两类任务分配问题。极大极小和总体极小任务...