n个元素分类(sort)的一个算法

本文给出的是分类 n 个元素的一个递归算法,其时间复杂性为n log n-5/4 n+1og n~(1/2)+C,这个值已经和分类问题的理论下界相当接近。目前所知的和它同级的分类法,如堆分类法(Heapsort)和合并分类法(Mergesort)等,虽然都是 O(nlogn)级的,但所需比较次数都比本文提供的算法多。本文共分三部分:1.最少插入分类法2.时间复杂性3.作者的猜想     

一个新的分类算法——基数子域互换法

本文提出了一个新的分类算法——基数子域互换法。该算法的时间复杂性是O(n),且不依赖于数据结构的初始状态;交换次数最好情况下是0,最坏情况下是O(n),数学期望是,其中M是基数,L_(max)是在M进制下关键字的最大长度;它不需要辅助信息缓冲区,只需要2M个工作单元,该算法尤其适用于n大,关键字短的信息分类;而对于n大,关键字长的信息,则在将该算法与某一有效的比较分类法混合使用后,可较单独用这同一比较分类法的时间复杂性好数倍甚至几十倍。     

无移位操作的快速comb乘法算法

有限域GF(2n)上乘法运算是影响GF(2n)上椭圆曲线密码实现效率的关键运算之一.基于窗口技术的comb乘法算法,被认为是目前有限域GF(2n)上乘法运算最快的算法之一.但是,它仍然使用了移位操作,而移位操作恰好又是域GF(2n)乘法运算中很耗时的操作.提出并实现了一种新的基于窗口技术的快速comb乘法算法,该算法避免了移位操作,且不增加异或运算次数.理论分析和实验结果表明,新算法有很好的实现效率,适合于有限域GF(2n)上椭圆曲线密码算法的软件实现.     

平均分类(Meansort)算法

本文给出了一个基于快速分类(Quicksort)算法的高效算法。人们已经知道,快速分类算法是最有效的分类方法之一。但是,这种方法有一个缺陷,就是在最坏的情况下要进行 O(n~2)次比较。本文给出的算法改进了快速分类算法的平均性能,减少了最坏情况的发生。     

一种基于KNN用户兴趣快速分类算法

用户兴趣的快速分类是个性化检索系统的关键技术,而KNN(K-Nearest Neighbor)是向量空间模型中最好的文本分类算法之一.本文分析了KNN分类法存在的不足,提出了一种用户兴趣快速分类算法,形式化地描述了用户兴趣模型的建立和兴趣更新过程.实验表明改进的算法可以在保持KNN分类性能基本不变的情况下,显著提高分类效率.     

FlashSort排序算法及实现

现在最快的排序算法是快速排序算法,它的时间复杂度达到O(n log n)。但是还有一种排序算法,就是Flashsort排序算法。它的时间复杂度达到O(n),超过了前者。FlashSort排序是基于分类的算法,它的实现思想很简单,是利用构造出来的索引来排序。举一个简单的例子,比如有一百个整数,你很容易就能把它们放在数组的正确位置上,根本不需要作任何比较。     

FlashSort排序解法及实现

现在最快的排序算法是快速排序算法,它的时间复杂度达到O(n log n)。但是还有一种排序算法,就是Flashsort排序算法。它的时间复杂度达到O(n),超过了前者。FlashSort排序是基于分类的算法,它的实现思想很简单,是利用构造出来的索引来排序。举一个简单的例子,比如有一百个整数,你很容易就能把它们放在数组的正确位置上,根本不需要作任何比较。     

一次到位分类法

传统的分类法(如交换、插入、选择等),大都从比较两数的大小出发进行分类,而不考虑两数之差的大小,因此分类速度最快为0(nlog_2n),本文介绍一个分类算法,不但利用两数的大小这一信息,同时还考虑两数之差的大小,或者说被排数据的分布规律,从而加快了分类速度。算法具体描述如下:设有未分类数据y(i)1≤i≤N,定义数组     

n 个规格化数的最优排序算法

<正> n 个实数的排序是最经常遇到的问题之一。目前常用的排序方法是“泡沫分类法”,用 ALGOL60书写,形式为for j:=n-1 step-1 until 1 dofor i:=1 until j doif A[i+1]相似文献   

基于幂级数展开的基本初等函数的高精度快速计算

本文考虑了基本初等函数的高精度快速算法问题.首先讨论与Bernoulli数B_(2n)或Euler数E_(2n)相关的基本初等函数(如tanx、secx、tanhx等)的幂级数展开问题,并给出相应的幂级数展开式的快速算法.然后,对于基本初等函数、双曲函数和反双曲函数,在复数域上给出基于幂级数展开的任意精度的快速算法.由于指数、对数函数可以用幂级数表示,本文设计的算法适用于所有初等函数的计算.算法的特点是编程简单、容易实现,可以自成计算初等函数的体系.     

Rabin指纹算法在重复数据检测中的应用研究

Rabin指纹算法计算效率高、随机性好,可将数据更改对连续指纹序列的影响限制在局部范围内,广泛应用于重复数据检测领域。分析了Rabin指纹在有限域GF(2n)上的运算原理,得出滑动窗口移动时定长字符序列的数字指纹快速计算公式。用伪代码描述了Rabin指纹算法在重复数据检测中的应用,并用VC++语言进行了算法实现,在普通计算机上提取Word文档、程序源代码和BMP图像等三类文件作为测试数据集,测试结果表明算法是有效的。     

软件组件获取方法的研究

基于组件技术的应用开发(CBD)可以有效地减少开发成本和复杂性,并可以很大程度地缩短开发周期,提高软件质量。其中一个关键的问题就是如何能使重用者能够在因特网上准确、快速地查找到适用的组件;而这取决于科学的分类方法对各种各样的组件进行分类和管理,以及高效准确的搜索查找方法。文章对传统的分面分类法(Facetedclassification)进行了修改和扩充,在此基础上提供了一个新的分类体系对组件库进行科学地分类和管理;同时针对组件查找问题,提出了体系分类法,并实现了一个基于此分类法的用于软件组件的专门搜索引擎。     

并行归并选择算法

本文利用动态分组原理,基于Valiant的快速归并算法,给出了一个从n个数中选取m个最小(或最大)者的(m,n)归并选择算法.此算法在具有[n/2]台处理器的并行系统上,可在O(log n log logm-sum from i=1 to log[n/2](i=1)logi)的时间步内完成(m,n)选择问题的求解.     

利用未标识文档提高中心分类法性能的研究

中心分类法性能高效,但需要大量的训练文档(已标识文档)来训练分类器以保证分类的正确性.而训练文档因需花费大量人力物力来分类而数量有限,同时,网络上存在着很多未标识文档.为此,对中心分类法进行改进,提出了ONUC和0FFUC算法,以弥补当训练文档不足时,中心分类法性能急剧下降的缺陷.考虑到中心分类法易受孤立点的影响,采取了去边处理.实验证明,与普通的中心分类法、其它半监督经典算法比较,在训练文档很少的情况下,该算法能获得较好的性能.     

求有向图必经结点的一个有效算法

本文给出在任意有向图中求必经结点的一个算法,以及对应的BASIC语言写的程序。算法使用了深度优先搜索、脱机最小值算法、不相交集的合并算法,以及能体现优先队列功能的2—3树算法,从而使算法的时间复杂性最多为O(nlogn e),空间复杂性最多为O(e),n,e分别为图的结点数和边数。当e≥nlogn时,本算法时间复杂性为O(e),它在一个常数范围内是最优的。     

基于超椭球分类面的SVDD快速决策方法

针对现有支持向量数据描述(SVDD)快速决策方法在检测不同分布特性的未知样本时分类精度低下的问题,提出基于超椭球分类面的SVDD(HE-SVDD)快速决策方法.该方法通过构建超椭球分类面,提高了不同分布类型数据的分类精度,同时将SVDD的决策复杂度从$O(n)$降低到O(2)(n为支持向量数量).首先研究超球分类面快速决策方法的局限性,进而给出超椭球分类面的构建方法.在多种数据集上的实验结果表明,HE-SVDD可以在很大程度上提升现有快速决策方法的分类精度和适用数据类型.     

充分利用局部有序的快速排序

1984年R.G.Dromey提出了在快速排序中利用部分有序的算法。本文对他的有序性概念进行了扩充。改进后的算法充分利用了排序数据的有序性。算法的最佳性能为o(n),最坏情况为O(n~2)。因此本算法优于快速排序和TRANSORT。     

决策树分类法及其在土地覆盖分类中的应用

基于决策树分类算法在遥感影像分类方面的深厚潜力,探讨了3种不同的决策树算法(UDT、MDT和HDT)。首先对决策树算法结构、算法理论进行了阐述,然后利用决策树算法进行遥感土地覆盖分类实验,并把获得的结果与传统统计分类法进行比较。研究表明,决策树分类法有诸多优势,如:相对简单、明确、分类结构直观,另外,与以假定数据源呈一固定概率分布,然后在此基础上进行参数估计的常规分类方法相比,决策树属于严格“非参”,对于输入数据空间特征和分类标识具有更好的弹性和鲁棒性(Robust)。     

计算q~(l_1)×q~(l_2)二维DCT的快速算法

离散余弦变换 (DCT)广泛应用于信号处理的许多领域 ,多维 DCT(MD- DCT)是图像处理和视频信号处理的重要工具 .通常 ,多维 DCT采用行列法用一维算法实现 ,实现效率较低 .近年来虽然出现了一些多维 DCT直接实现算法 ,但大多要求变换为 2 n× 2 n,限制了适用范围 .该文研究较一般的二维 DCT快速算法 ,将 ql1 × ql2 (q为奇素数 ;l1 ,l2 分别为两个不同的整数 )二维 DCT转化为多项式变换和一维简化余弦变换 ,通过特别设计的快速多项式变换算法和 1D- RDCT递归分解算法 ,提出了一种计算复杂性较低且具有规则运算结构的 ql1 × ql2 二维 DCT算法 .本算法的设计方法可以方便地推广到多维 (>2 )的情况 .     

计算q1^l×q2^l二维DCT的快速算法

离散余弦变换(DCT)广泛应用于信号处理的许多领域,多维DCT(MD-DCT)是图像处理和视频信号处理的重要工具.通常,多维DCT采用行列法用一维算法实现,实现效率较低.近年来虽然出现了一些多维DCT直接实现算法,但大多要求变换为2n×2n,限制了适用范围.该文研究较一般的二维DCT快速算法,将ql1×ql2(q为奇素数;l1,l2分别为两个不同的整数)二维DCT转化为多项式变换和一维简化余弦变换,通过特别设计的快速多项式变换算法和1D-RDCT递归分解算法,提出了一种计算复杂性较低且具有规则运算结构的ql1×ql2二维DCT算法.本算法的设计方法可以方便地推广到多维(>2)的情况.