常用排序算法时间开销的实验统计分析

以数值数据为排序对象,对交换排序、冒泡排序、选择排序、插入排序、归并排序以及快速排序等常用的六种排序算法的时间复杂度从实验统计角度进行分析和对比.本实验统计数据分析可知具有相同定性指标的排序算法,可能实际时间效率有着很大的差异,这组实验数据可为实际应用中排序算法的选择提供参考.     

选择排序算法的一个改进及分析

针对少量记录排序的应用，对直接选择排序算法进行了挖掘，通过增加记忆功能，使算法性能得到明显提高。改进后的算法在大量记录排序时，较原算法的速度提高1倍以上；在少量记录排序时，是基于比较和移位的排序算法中总体表现最佳的；并且对原序列的有序程度很敏感，原序列相对有序时，速度能大幅度提高。结果表明：该算法很适合少量记录排序、部分排序、较有序记录的排序，以及与快速排序算法的混合使用。     

The distribution search: An O (n) expected time search

Provided an algorithm for the distribution search and proves the time complexity of the algorithm. This algorithm uses a mathematical formula to searchn elements in the sequence ofn elements in O (n) expected time, and experimental reesult proves that distribution search is superior to binary search. Xu Xusong: born in June 1945, Professor     

基于改进K最近邻算法的中文文本分类

针对文本分类存在的高维文本问题,提出文档频率(DF)-卡方统计量特征提取方式,对特征项进行有效约减,降低文本维度,提高分类精度.在K最近邻(KNN)算法的基础上,针对待分类文本需要和大量训练集样本进行相似度计算的问题,提出一种基于分组中心向量的KNN算法,对类别内的样本集分组求出各组中心向量,使其重新代表训练库计算相似度,降低计算复杂度,提升算法的分类性能.通过实验表明:相较传统KNN算法,改进的算法在准确率、召回率及F值方面都有提升,与其他分类算法相比,具有一定的优势.     

Stable initialization scheme for K -means clustering

Though K-means is very popular for general clustering, its performance which generally converges to numerous local minima depends highly on initial cluster centers. In this paper a novel initialization scheme to select initial cluster centers for K-means clustering is proposed. This algorithm is based on reverse nearest neighbor (RNN) search which retrieves all points in a given data set whose nearest neighbor is a given query point. The initial cluster centers computed using this methodology are found to be very close to the desired cluster centers for iterative clustering algorithms. This procedure is applicable to clustering algorithms for continuous data. The application of proposed algorithm to K-means clustering algorithm is demonstrated. Experiment is carried out on several popular datasets and the results show the advantages of the proposed method. Foundation item: Supported by the National Natural Science Foundation of China (60503020, 60503033, 60703086), the Natural Science Foundation of Jiangsu Province (BK2006094), the Opening Foundation of Jiangsu Key Laboratory of Computer Information Processing Technology in Soochow University (KJS0714) and the Research Foundation of Nanjing University of Posts and Telecommunications (NY207052, NY207082)     

二次立体堆排序算法设计与分析

通过对立体堆排序算法的分析,从分段优化数据处理技术角度,提出了二次立体堆排序算法,给出了算法思想、算法描述和算法分析,论证了二次立体堆排序算法,随着排序数量增加,排序速度快于立体堆排序算法越显著.     

排序算法并行化

阐述了BSP上的并行排序算法,进行了该算法的性能分析,并通过与PRAM—CRCW上快排序算法的比较,说明了该算法的可行性．     

基于梯度惩罚生成对抗网络的过采样算法

在不平衡数据分类问题中，为了更注重学习原始样本的概率密度分布，提出基于梯度惩罚生成对抗网络的过采样算法（OGPG）。该算法首先引入生成对抗网络（GAN），有效地学习原始数据的概率分布；其次，采用梯度惩罚对判别器输入项的梯度二范数进行约束，降低了GAN易出现的过拟合和梯度消失，合理地生成新样本。实验部分，在14个公开数据集上运用k近邻和决策树分类器对比其他过采样算法，在评价指标上均有显著提升，并利用Wilcoxon符号秩检验验证了该算法与对比算法在统计学上的差异。结果表明该算法具有良好的有效性和通用性。     

A distributed dynamic clustering algorithm for wireless sensor networks

This paper proposes a distributed dynamic k-medoid clustering algorithm for wireless sensor networks (WSNs), DDKCAWSN. Different from node-clustering algorithms and protocols for WSNs, the algorithm focuses on clustering data in the network. By sending the sink clustered data instead of practical ones, the algorithm can greatly reduce the size and the time of data communication, and further save the energy of the nodes in the network and prolong the system lifetime. Moreover, the algorithm improves the accuracy of the clustered data dynamically by updating the clusters periodically such as each day. Simulation results demonstrate the effectiveness of our approach for different metrics. Biography: WANG Leichun (1974–), male, Ph.D. candidate, research direction: wireless communication.     

基于后缀数组的快速排序算法

在搜索技术和各种流行的排序算法优缺点比较的基础上,给出了一种基于后缀数组的新的快速排序算法,该算法在时间和空间性能上均优于传统的快速排序算法;并在同等的条件下,用该方法与快速排序算法对相同的内容进行排序,结果表明:该算法特别适用于大文本的排序问题,可用于搜索技术和数据压缩中.     

基于二元树复小波和SVD不变性的纹理图像分类算法

针对双树复小波变换(DT-CWT)用于图像的纹理特征提取时,不具有旋转和尺度不变性的局限,提出了一种基于DT-CWT和SVD的纹理分类算法.该算法首先利用DT-CWT从图像中提取出纹理特征,然后对纹理特征进行奇异值分解获得具有旋转和尺度不变性的特征向量,采用BP神经网络作为分类器,并提出改进的BP算法训练网络,使得网络很快找到全局最优解.将本方法与其他的分类算法进行比较,实验结果表明,本算法具有较高的分类正确率.     

有向网络下的CoDA社区发现算法评估

CoDA算法是一种基于概率模型的能识别二分结构的社区发现算法。为了验证该算法的社区划分效果,采用信息检索领域的F-measure标准,对有向网络下重叠社区和非重叠社区的CoDA社区发现算法进行评估。F-measure标准中F1-measure值的大小能反映CoDA算法社区划分效果的优劣。实验所用的数据集由LFR Benchmark工具生成,数据集中节点数最小为100,最大为20 000,每增加100节点对CoDA算法社区划分效果评估一次。分析实验结果可以得出,当节点数小于1 600时,CoDA算法的划分效果较好。当节点数大于1 600时,随着节点个数增多,CoDA算法社区划分效果逐渐变差。由此说明,基于概率模型的CoDA算法适用于小规模社交网络社区的划分。     

求多重分形谱的一种实用算法

给出了一类图象所对应的多重分形谱的一种实用算法，该算法可用于一类实验数据的处理．     

基于Java按位拆分快速排序算法的数值仿真

介绍了一种新的按位拆分排序算法的基本思想,并利用Java语言实现了该算法程序.通过多种数据实验和Matlab数值仿真,直观形象地说明了该算法的高效性.     

快速排序的改进算法

对快速排序算法进行了改进,根据在待排序列基本有序的情况下,插入排序有较好的性能特点,在改进算法中,只对长度k大于的子序列递归调用快速排序,最后再对整个序列用插入排序方法排序,我们得到了时间复杂性为1.386 nlog(n/k) nk/4 3(n 1)/(k 1) O(logn)的排序算法,当k取值为8左右时,改进算法的性能较隹.     

一种基于Hough变换的四边形分类识别算法

在直线和圆的识别算法基础上提出一种基于Hough变换的四边形分类识别算法,并进行实验验证。该算法通过Hough变换检测所构成四边形的4条线段,分别计算出4条线段与平面直角坐标系横坐标的夹角值(或是斜率),然后用冒泡排序法对夹角值排序后比较大小,根据线段间的关系(平行、垂直、相交)对四边形进行分类识别。算法可行,效果较好。     

一种有向图并行性拓扑排序算法

论述了有向图并行性拓扑排序的基本概念及其算法，解决了目前有向图拓扑序列串行性的缺点，说明有向图并行拓扑排序具有应用范围广、实用价值大的特点。     

面向云数据中心资源均衡分配需求的聚类调度算法研究

针对云数据中心资源利用率较低、能源消耗较高的问题,提出了基于资源需求差异的资源均衡调度策略。在包簇框架模型基础上,利用与资源需求相关的距离度量因子,将资源需求差异大的包通过改进的k-means算法进行聚类;利用资源之间的相关性作为包与簇之间的距离,在资源分配的过程中使包能够集中映射到簇中,从而减少簇的使用个数。实验结果表明,在包簇框架的概念下,基于资源需求差异的改进后的k-means聚类算法能够优化包聚类步骤,资源调度算法能够提高云数据中心各类资源利用率、降低资源分配过程中产生的能耗,具有有效性和可扩展性。     

基于改进k-means算法的可见光通信非线性补偿技术

可见光通信系统中,正交频分复用技术的高峰均功率比会加大发射信号产生非线性失真的概率。为了降低系统的误码率,提出了一种改进的k均值(k-means)算法的非线性补偿技术。该算法考虑了信号的传输特性,运用Dijkstra算法优化了k-means算法中初始点的选择,能够准确地找到接收信号星座图的聚类中心,避免了传统k-means算法在选择初始聚类点时陷入局部最优解。仿真结果表明,相比于传统的k-means算法,改进的k-means算法能更准确地找到非线性失真后信号的星座点位置,因此能有效地解决可见光通信系统的非线性问题,降低了系统的误码率。     

选择排序算法的改进

经过深入分析论证,指出传统的选择排序算法所存在的效率不高的缺陷,提出了改进方法,并编程予以实现。