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

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

一个多元选择算法

本文基于数排序的思想，从高位关键字开始，对ｍ位关键字的ｎ个记录进行扫描，给出了一个多元选择算法，算法的最坏复杂度为Ｏ（ｍ（ｎ＋ｒ）），但平均复杂度为Ｏ（ｎ＋ｒ）。     

关于迷宫排序问题的研究

本文首先把迷宫排序问题推广为ｍ×ｎ迷宫（ｍ＞１，ｎ＞１）的排序问题，证明了ｍ×ｎ迷宫的任一初始状态能经过有限步移动转变成目标状态的充要条件，然后给出了一个ｍ×ｎ迷宫排序的算法，该算法的时间复杂度是Ｏ（ｍｎ（ｍ＋ｎ）），空间复杂度是Ｏ（ｍｎ）．最后还指出了它的时间复杂度的一个下界．这样，关于迷宫排序问题就基本上得到了圆满地解决．     

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

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

确定任意简单多边形平移时碰撞部位的扫描算法

设Ｐ和Ｑ为平面内任意两个互不相交的简单多边形,若Ｐ沿方向ｄ平移时与Ｑ碰撞,采用平面扫描法,通过提取多边形的单调链,给出了求其碰撞部位的算法,最坏情况下,算法的时间复杂性为Ｏ（ｍ＋ｎ）ｌｏｇ（ｍ＋ｎ）,其中ｎ和ｍ分别为多边形Ｐ与Ｑ的边数,与现有的算法相比,降低了时间复杂性。     

基于数据分布特性的快速排序

文中提出了一种基于数据分析特性的快速排序算法，根据被排数据的分布行性，选择数据比较次数和数据移动次数较少的排序算法，当被排数据存在ｍ个有序序列时，其算法的时间复杂度为Ｏ（ｎｌｏｇ２ｍ）其中ｍ∈（１，ｃｆ√ｎ），ｃ为某一常数，其最佳性能为Ｏ（ｎ）。当ｍ≥ｃ（√ｎ）时，保持快速排序的最佳平均性能，使排序运行于较优状态下。     

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

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

N-Star网络中最优的点到多点平行路由算法

Ｃｈｅｎｔ等研究了ｎ－Ｓｔａｒ网络中的点到多点并行路由问题,对前人的工作做了很大的改进,给出了一个几乎最优的时间复杂度为Ｏ（ｎ＾２）的算法,由Ｃｈｅｎ的算法所给出的ｎ－１条路Ｐ２,…,Ｐｎ满足│Ｐｉ│≤ｄｉｓｔ（ｖ１,ｖｉ）＋６,其中Ｐｉ是连续ｖｉ到ｖ１的路,│Ｐｉ│表示路Ｐｉ的长度,ｄｉｓｔ（ｖ１,ｖｉ）表示ｖｉ到ｖ１的最短路的长度。     

线段相交问题的平面扫描型改进算法

本文对计算平面上ｎ个线段所有交点的平面扫描算法及数据结构做了改进。若设这ｎ个线段的交点总数为ｋ，这ｎ个线段中与垂直扫描线相交的最多个数为ｍ，则改进后的算法的计算时间为Ｏ（ｎｌｏｇｍ＋ｋｌｏｇｍ），占用存储空间为Ｏ（ｍ）。     

确定简单多边形旋转时碰撞部位的扫描算法

给定平面内任意两个互不相交的简单多边形Ｐ是Ｑ。若Ｐ在平面内绕０点旋转时与ＡＱ碰撞,讨论其碰撞部位的判定问题,通过分析多边形关于０点的单调边,在平面扫描算法的榧耻提出了曲线扫描法,给这一总理２的Ｏ（（ｍ＋ｎ）ｌｏｇ（ｍ＋ｎ））算法,与现有的算法相比,降低了时间复杂性,这一方法在计算几何和计算机图形学等领域具有一定的理论和实吓价值。     

最长公共子序列问题的改进快速算法

现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<相似文献   

几何算法求解货郎担问题

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

基于SIMD-MCC的二维图象力矩特征提取并行算法

提取图象元件的几何特性在图象的物体识别中是一个非常重要的步骤。文章提出了一个在ＳＩＭＤ－ＭＣＣ计算机上实现的提取图象力矩的并行算法,此算法采用了一种级联部分和的方法来同时计算一个幅图象ｍ个元件力矩特性。这种方法的基本思想是将一个二维力矩分解为许多垂直力矩和一个水平力矩,对前者采用数据并行性、对后者实施任务并行性。对于一幅包含ｍ个元件的ｎ×ｎ图象,计算其ｍ个力矩的时间花费为Ｏ（［ｍ／ｎ］ｎ）。和现有算法相比,其速度有了较大提高。     

基于散列和归并技术的有效并行排序方法

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列，引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序，这一阶段所需的平均时间为Ｏ（ｎ／ｐ）；最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列，归并阶段所需的时间为Ｏ（ｎ－ｎ／
／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓以网络并行机群环境。     

最短路径重构算法

研究了在Ｎ个顶点的图中，仅给出了所有顶点对之间最短路径距离矩阵，而计算任两顶点间最短路径问题。这种算法因没有利用原始图中有关边的信息，被称为重构算法。本研究取得了如下成果：①在单一的顶点对之间最短路径重构的时间复杂度为Ｏ（ｎｌｏｇｎ）；②在所有顶点对之间的最短路径重构的时间复杂度为Ｏ（ｎ＾３）；③在带有ｎ／ｌｏｇｎ个处理器的独占读写并行随机访问器上，单一顶点对之间的最短路径重构时间复杂度为Ｏ（（ｌ     

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

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

基于关系的最粗粒度划分问题的并行算法

关系最粗粒度的划分问题ＰＣＰＰ在并发系统的验证方面起着重要的作用。本文提出了ＲＣＰＰ问题的一种有效的并行算法,其中假设标号转移系统中有ｍ个转移和ｎ个状态,利用ｍ／ｎ＾∈个ＣＲＥＷ处理器算法所需的运行时间为Ｏ（ｎ＾１＋∈）（对于任意固定的∈〈１）。     

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

0-1背包问题的深度优先算法

本文介绍了０－１背包问题的一种深度优先（ＤＦＳ）算法,并用概率分析方法给出了算法的时间复杂度和空间复杂度,一般情况下,其时间复杂度在Ｏ（ｎ）到Ｏ（１．５）之间。工程管理上的一类整数规划问题都可归结为０．１背包问题。     

一个选择算法及其并行化

文中用合并选择的思想及堆上的最佳算法，给出了求解选择问题的一个新算法及其相应的并行化。将串行合并选择算法的复杂度ｎＬｏｇｋ＋Ｏ（ｎ）降低到（ｎＬｏｇｋ）／２＋（ｎＬｏｇＬｏｇｋ）／２＋Ｏ（ｎ），并保持了原并行算法的结构，在ＳＩＭＤ树型机器的并行计算模型上，并行运行