几种查找算法的比较

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，文中介绍四种查找算法，分别是顺序查找、二分查找、二叉排序树查找和哈希查找。并用JAVA语言编写了相应程序代码，比较了查找同一个数据的时间复杂度和空间复杂度。     

并行查找算法的MPI实现

本文对一种并行查找算法进行介绍,然后给出其MPI实现,并进行时间复杂度分析．     

一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位，这个问题的最直接解法是先将序列排序，从而能得到第K个元素，最少需O(nlogn)次比较，即时间复杂度为O(nlogn)．比较好的方法是采用分治策略解决该同题，但其最坏时间复杂度为O(n^2)，平均时间复杂度为O(2n)．本文提出一种Byte解决第K个元素问题的算法，该算法的平均时间复杂度为O(n n／255)，优于以前对该问题的求解方法，而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集．     

求第K个元素的快速算法

依据数据的机内编码特征，提出了一种从无符号整数序列中查找第K个元素的快速算法．算法分析和实验结果表明：算法的时间复杂度低于传统的基于比较的查找算法，且附加存储空间小．     

基于集合理论的IP地址并行搜索技术

针对现有的IP地址查询技术存在查找速度慢、性能低、可扩展性差、算法空间复杂度大以及成本高等问题,提出了一种结合使用软硬件的方法执行IP地址查询,将路由集合分割成奇偶位两个子集,然后对每个子集进行搜索.此方案能以较低的硬件代价在较短的时间内搜索到IP地址的网络ID号,减少了查找的比较次数和存储空间.     

超宽带中快速低复杂度自动增益控制设计

针对应用于双载波正交频分复用（DC-OFDM）超宽带（UWB）系统高速、低成本和快速收敛的自动增益控制（AGC）的设计要求,提出了低复杂度的采用混合补偿增益的两步式快速AGC设计算法;仿真结果表明,该算法能在室内密集多径的无线环境中保证增益调整精度和稳定度,并能有效减少收敛时间.在AGC电路实现层次,基于对数函数性质提出了输入范围动态可调的低复杂度查找表实现方法;VLSI综合结果表明,该方法能减少46%的芯片面积.     

一种IP数据包快速分类算法

为了提高查找效率,在无冲突哈希查找算法和Grid of Tries算法的基础上提出了一种基于无冲突哈希和多比特Trie树(NHMT)的IP分类算法.该算法的核心有3部分:哈希函数的构造,主要是采用基于目的端口和协议两域构造哈希函数,使得在最坏情况下完全避免了空间爆炸问题;在Grid of Tries算法的基础上,对Grid of Tries算法改造成修剪的Trie树和多比特Trie树,以减少空间复杂度;在无冲突哈希查找算法的基础上扩展一层用于存放源端口号(或范围),扩展后一般要提高算法的时间复杂度,要通过引入多比特Trie树的方法进行解决.对于空间复杂度方面与无冲突哈希查找算法比较,一般情况下不增加空间复杂度.通过仿真,当对10 000条规则进行包分类时,该算法的分类速度可以达到1 Mbit/s,所消耗的最大内存为8.2 MB.     

数据流重组中Hash-Splay查找算法

针对高速网络取证目前所面临的问题,围绕提高网络数据流重组效率,在数据流重组算法中分析比较了几种典型的查找算法,并将Hash表和Splay树组合成Hash-Splay查找算法.该算法首先建立Hash表,然后将所有的TCP连接结点分配到各个表项,每个表项用Splay树将该表项的所有连接结点组织起来.查找时,根据连接标识通过Hash函数计算出Hash地址,再对该Hash地址对应的Splay树进行查找,找到后按照Splay树的操作规则进行查找、插入和删除等操作.由于根据连接标识找到对应Splay树的时间开销很小,可以忽略不计,因此Hash-Splay算法的复杂度可以看作是每棵Splay树操作的平均复杂度,算法同时具有Hash表和Splay树的优点,查找效率比Hash表和Splay树的都高.     

静态查找算法性能分析

查找是信息处理中常用的操作.对顺序查找和折半查找两种静态查找算法的性能进行了分析,并给出了相应算法平均查找长度的计算方法,以便应用软件设计者选择合适的查找算法,优化系统性能.     

静态查找算法性能分析

查找是信息处理中常用的操作。对顺序查找和折半查找两种静态查找算法的性能进行了分析，并给出了相应算法平均查找长度的计算方法，以便应用软件设计者选择合适的查找算法，优化系统性能。     

Shell排序时间复杂度实验研究

为探索具有最优渐近时间复杂度的步长序列及其选择方法,以不同步长序列对一些规模较大的待排序列进行试验,研究了Shell排序的时间复杂度与步长序列的关系。     

一种新的2-路插入排序算法

详细分析2-路插入排序算法,给出了一种改进的2-路插入排序算法及其实现．这种插入排序算法不论时间复杂度还是空间复杂度,相对原2-路插入排序算法都有较好的改善。     

一种新的快速码本搜索算法设计

提出一种新的分类预选算法。旨在解决矢量量化数据压缩技术中,当码本值和矢量维数增大时,全码本搜索产生很大的实时复杂计算问题。该算法与传统的全搜索算法相比,能减小编码矢量选取过程中产生的计算复杂度。同时,编码器的性能几乎没有受到影响,仅仅在存储需求量方面略有增加。     

一种传感器网络中频繁移动模式挖掘算法

针对传感器网络中包括目标位置和时间的二维属性频繁移动模式挖掘问题,建立了一种新的树状结构OMP-tree,OMP-tree可以压缩存储大量的原始移动模式.同时提出了一种条件搜索算法,使用该算法可以大大减少满足条件的前缀模式数量.基于OMP-tree和条件搜索算法,设计了一种新的挖掘目标的频繁移动模式算法OMP-mine.该算法基于模式增长思想,直接递归地从条件模式基中得到频繁的前缀模式,然后连接后缀,达到模式增长的目的.仿真结果表明,OMP-mine算法可以有效挖掘出传感器网络中具有二维属性的频繁移动模式,并较好地降低了算法的时间和空间复杂度.     

A novel fuzzy keyword retrieval scheme over encrypted cloud data

In this paper, we focus on the fuzzy keyword search problem over the encrypted cloud data in the cloud computing and propose a novel Two-Step-Bloom-Secure-Filter (TSBSF) scheme based on Bloom filter to realize the efficiency and flexibility of data use. The proposed scheme not only reduces the space complexity significantly but also supports the data update with low time complexity and guarantees the search accuracy. Experimental results on real world data have certified the validity and practicality of this novel method.     

一种新的基于图像的路径压缩优化方法及其在数字岩心中的应用

针对并查集方法进行图像连通区域识别过程中,数据量大,时间复杂度高等问题,提出一种基于路径压缩理论的“标签吸收”方法,它能够使查找树的高度和时间复杂度降低,并且仅需一次扫描就可以对整个图像的连通区域完成识别,本文详细论述了整个方法的实现过程并将其应用于油气田开发领域数字岩心微观图像识别中,结果表明该优化方法准确可行。     

基于结构相似度的H.264快速算法

H.264比以往的视频压缩标准具有更高的压缩效率, 然而编码的复杂度也大大增加. 针对降低编码复杂度,提出了基于结构相似度(SSIM)的快速算法(FMEBSS), 该算法可以通过减少不必要的运动搜索点和复杂的搜索模式, 达到减小运动估计复杂度的目的. 试验结果表明在保证编码质量不下降的前提下, 该算法可以平均节约编码时间约50%, 同时有效地降低了编码码流长度.     

一维数组循环移动的高效算法

给出一种时间复杂度为O(n)的一维数组循环移动的高效算法,并给出用PASCAL语言实现的方法及技巧。     

基于遗传算法的二维熵方法自动阈值

利用二维灰度直方图方法对于有噪声的图象进行分割,可以取得比较满意的效果。但是该方法时间复杂度高,耗时长,因此,如何设法减少运算时间就显得很必要。二维直方图的阈值选取,就其本质而言,是一个求全局最优的优化问题,而遗传算法对这类问题往往很有效。该文给出了在二维熵方法中,利用遗传算法对最优阈值进行搜索的快速算法,运算时间仅为穷尽搜索的１／１００。