并行归并排序算法

构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ＾１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数小于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ＾１／２ｌｏｇ ｎ）。     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．     

完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

判定点集是否在多边形内部的算法

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。     

几何算法求解货郎担问题

本文提出求解货郎担问题的一种几何算法。它的时间复杂性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次乘法，其中ｎ，ｍ分别是点集的点数和凸包顶点数。     

Mn（NO3）2溶液热扩散的TiO2压敏电阻—电容性能

对于Ｎｂ２Ｏ５施主掺杂的ＴｉＯ２半导瓷，掺入ＢａＣＯ３，Ｂｉ２Ｏ３可形成晶界绝缘层并可降低烧结温度，采用Ｍｎ（ＮＯ３）２溶液热扩散的方法使Ｍｎ＾２＋进入晶界可提高晶界热垒，从而提高压敏电压及非线性系数，大幅度降低介电损耗。     

二维模式近似匹配的快速算法

给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜＋ｈｍ２）。     

Toeplitz矩阵相乘的快速卷积算法

本文利用Ｔｏｅｐｌｉｔｚ矩阵可分解为循环阵与斜循环阵之和的特点２，借助于卷积的ＦＦＴ算法，推导出计算两个Ｔｏｅｐｌｉｔｚ矩阵之积的一种新的快速算法，其乘法复杂性为２ｎ＾２＋Ｏ（ｎｌｏｇ２ｎ）。     

一种并行测试的最优设计方法

本文采用整数线性规划，实现了并行测试的最优设计。该方法使得并行测试图（ＰＴＧ）的最大完全子图（ＭＣＳ）的顶点数最少，即ＰＴＧ的点着色数（ＶＣＮ）最少，因而使得总的测试时间最少。文中提出了一个Ｏ（ｎ＾２）的最优测试调度算法。实现证明该模型是有效的，正确的。     

一种求简单多边形凸包的最优算法

计算一般多边形凸包的算法时间复杂度为Ｏ（ｎ＾２）。     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

An improved algorithm for hierarchical clustering using strong components

In 1982 the author presented an O(m(log n)²) time algorithm for hierarchically decomposing a directed n-vertex, m-edge graph with weighted edges into strong components. Such an algorithm is useful in cluster analysis of data with an asymmetric similarity measure. The present paper gives a simpler algorithm with the faster running time of O(m log n).     

A parallel median algorithm

We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)²) parallel time on O(n) processors in Valiant's comparison model.     

用于WEB文档分类的并行KNN算法

针对WEB文档分类中KNN算法计算复杂度高的缺点,不同于以往从减少训练样本集大小和采用快速算法角度来降低KNN算法的计算复杂度,从并行的角度出发,提出一种在Hyper-cube SIMD模型上的并行算法,其关键部分的时间计算复杂度从O（n²）降为O（log（n））,该算法与传统的串行算法相比,能显著地提高分类速度。     

Multiway merging in parallel

The problem of merging k (k⩾2) sorted lists is considered. We give an optimal parallel algorithm which takes O((n log k/p)+log n) time using p processors on a parallel random access machine that allows concurrent reads and exclusive writes, where n is the total size of the input lists. This algorithm achieves O(log n) time using p=n log k/log n processors. Most of the previous log n research for this problem has been focused on the case when k=2. Very recently, parallel solutions for the case when k=2 have been reported. Our solution is the first logarithmic time optimal parallel algorithm for the problem when k⩾2. It can also be seen as a unified optimal parallel algorithm for sorting and merging. In order to support the algorithm, a new processor assignment strategy is also presented     

A Fast Approximation Algorithm for the Subset-sum Problem

The subset-sum problem (SSP) is defined as follows: given a positive integer bound and a set of n positive integers find a subset whose sum is closest to, but not greater than, the bound. We present a randomized approximation algorithm for this problem with linear space complexity and time complexity of O( n log n ). Experiments with random uniformly-distributed instances of SSP show that our algorithm outperforms, both in running time and average error, Martello and Toth's (1984) quadratic greedy search, whose time complexity is O( n ²). We propose conjectures on the expected error of our algorithm for uniformly-distributed instances of SSP and provide some analytical arguments justifying these conjectures. We present also results of numerous tests.     

Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

大型数据库中利用强化学习改进treap的关联规则挖掘算法

信息的爆炸式增长使数据挖掘分析过程更加困难,针对普通关联规则挖掘算法很难在短运行时间和低关联度的前提下完成大型数据库中变量关系的评估和发现的问题,提出利用强化学习算法改进treap的大型数据库关联规则挖掘算法。提出的算法首先计算数据库中每个变量的优先级;然后,在优先级模型中利用强化学习算法改进的build-treap程序构建treap数据结构;最后,通过遍历程序和generateRule程序完成数据库中所需的关系查找。在对提出的算法进行稳定性分析后进行了仿真验证实验,实验结果表明,提出的算法在其最次和最佳案例分析中分别能够完成O(n log n)次和O(n 2)次挖掘,能够在较短时间内完成低关联度的大型数据库中变量关系挖掘任务,相对于改进型Apriori算法和改进型FP生长算法有较大提升。