共查询到19条相似文献,搜索用时 531 毫秒
1.
并行归并排序算法 总被引:3,自引:0,他引:3
来智勇 《计算机研究与发展》1995,32(6):46-49,54
构造效率为O(1)的并行算法是一个引人注目的问题。[1]和[2]分别提出了并行度为O(logn)和O(n^1/2)的、效率为O(1)的并行排序算法。本文提出一种新的并行排序算法,其效率为O(1),而并行步数小于[1]和[2]的算法的并行步数。经过改进后,在保持效率为O(1)的情况下,可进一步将并行度扩大到O(n^1/2log n)。 相似文献
2.
可重构造的网孔机器上的k-选择 总被引:2,自引:0,他引:2
对于一个 m ×n(m ≤k)的列有序矩阵,文中在 n × n 可重构造的网孔机器上提出了一个并行 k选择算法,其时间复杂度为 O(log2m + logm log2 n+ log3 n),而对于一般的l元集,文中在相同的模型下提出了一个时间复杂度为 O log2 ln + log ln log2 n+ log3n+ ln log ln 的并行 k选择算法.当时 l≥ O(nlog3n/log logn,该时间复杂度为 O ln log ln .特别地,当l= O(n1+ ε)(ε> 0 为常数),则时间复杂度为 O ln logn .此时达到的加速比为 n/logn. 相似文献
3.
本文给出了满足三角不等式的货郎担问题的并行启发式算法,在SIMD CREV PRAM并行机上该算法使用O(n^3/log^2n)台处理器需O熄log^2n)时间,这里n是给定城市的个数,因而该并行算法是最优的。 相似文献
4.
完全欧几里德距离变换的最优算法 总被引:12,自引:2,他引:12
欧几里德距离变换(EDT)对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离,应用于图象分析,计算机视觉,在本文之前,该问题的最好复杂度为O(n^2logn)。本文提出了一个复杂度为O(n^2)的算法,使复杂度达到最优,该算法可以并行化,在有r个处理单元的EREWPRAM计算模型上,若rlogr≤22/6n,则时间复杂度为O(n/r)否则为O(nlogr)。 相似文献
5.
本文在一个EREW PRAMexclusive read exclusive write paralled random access machine)上提出一个并行快速排序算法,这个算法用K个处理器可将N个项目在平均O(n/k+logn)logn)时间内排序,所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是O(nlogn)。 相似文献
6.
7.
一类扩展的Steiner树优化问题及其应用 总被引:1,自引:0,他引:1
本文提出了一个计算机网络通信和分布式系统中的一类扩展的Steiner树问题.对此问题设计了两个求其最优解的算法.这两个算法的时间复杂性分别是O(3(k-1)·n+2(k-1)·n2)和O(2(n-k)·n2).其中,k是一棵Steiner树需支撑的给定顶点的个数. 相似文献
8.
本文利用Toeplitz矩阵可分解为循环阵与斜循环阵之和的特点2,借助于卷积的FFT算法,推导出计算两个Toeplitz矩阵之积的一种新的快速算法,其乘法复杂性为2n^2+O(nlog2n)。 相似文献
9.
最短路径树的计算与修改算法 总被引:3,自引:0,他引:3
在有向赋权图G=(V,E,COST)上,给出了求解以每个顶点为根的向前/向后最短路径树(FBSPT)算法。当G中的边被删除或边权增加时,证明了在这种情况下,不可能存在高效的对FBSPT的修改算法;而对边添加和边权减少的情况,本文给出时间复杂性为O(n ̄2)的修改算法。此外,本文也讨论了对上述算法的并行实现问题。 相似文献
10.
几何算法求解货郎担问题 总被引:5,自引:1,他引:4
周培德 《计算机研究与发展》1995,32(10):63-65
本文提出求解货郎担问题的一种几何算法。它的时间复杂性为:O(n^3/m)次比较,O(n^2)次乘法,其中n,m分别是点集的点数和凸包顶点数。 相似文献
11.
12.
Eitan Zemel 《Information Processing Letters》1984,18(3):123-128
We present an O(n) algorithm for the Linear Multiple Choice Knapsack Problem and its d-dimensional generalization which is based on Megiddo's (1982) algorithm for linear programming. We also consider a certain type of convex programming problems which are common in geometric location models. An application of the linear case is an O(n) algorithm for finding a least distance hyperplane in Rd according to the rectilinear norm. The best previously available algorithm for this problem was an O(n log2n) algorithm for the two-dimensional case. A simple application of the nonlinear case is an O(n) algorithm for finding the point at which a ‘pursuer’ minimizes its distance from the furthest among n ‘targets’, when the trajectories involved are straight lines in Rd. 相似文献
13.
提出了一种计算图像几何矩的快速算法.根据图像区域边界的顶点链码,给出了图像几何矩的计算公式.该算法可以看作是格林理论的离散版本的一个推广,对低阶几何矩,算法的复杂度为O(n).与原有的几何矩算法比较,该方法具有实现简单、计算量小、计算结果精确等优点. 相似文献
14.
Prasad S.K. Das S.K. Chen C.C.-Y. 《Parallel and Distributed Systems, IEEE Transactions on》1994,5(9):995-1008
We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log2 n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms 相似文献
15.
深度优先稳定原地归并排序的高效算法 总被引:1,自引:0,他引:1
基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。 相似文献
16.
Ka Wong Chong Stavros D. Nikolopoulos Leonidas Palios 《Theory of Computing Systems》2004,37(4):527-546
In this paper we consider the problem of computing
the connected components of the complement of a given graph.
We describe a simple sequential algorithm for this problem,
which works on the input graph and not on its complement,
and which for a graph on n vertices and m edges
runs in optimal O(n+m) time.
Moreover, unlike previous linear co-connectivity algorithms,
this algorithm admits efficient parallelization, leading to
an optimal O(log n)-time and O((n+m)log n)-processor
algorithm on the EREW PRAM model of computation.
It is worth noting that, for the related problem
of computing the connected components of a graph, no optimal
deterministic parallel algorithm is currently available.
The co-connectivity algorithms find applications in
a number of problems.
In fact, we also include a parallel recognition algorithm
for weakly triangulated graphs, which takes advantage of
the parallel co-connectivity algorithm and achieves
an O(log2 n) time complexity using
O((n+m2) log n) processors on the EREW PRAM model of computation. 相似文献
17.
18.
19.
Ari Rappoport 《Computer Graphics Forum》1992,11(4):235-240
The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log2 n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log2 n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure. 相似文献