共查询到20条相似文献,搜索用时 15 毫秒
1.
几何算法求解货郎担问题 总被引:5,自引:1,他引:4
周培德 《计算机研究与发展》1995,32(10):63-65
本文提出求解货郎担问题的一种几何算法。它的时间复杂性为:O(n^3/m)次比较,O(n^2)次乘法,其中n,m分别是点集的点数和凸包顶点数。 相似文献
2.
确定多边形凸凹顶点的快速算法及其应用 总被引:13,自引:0,他引:13
提出一种确定任意多边形凸凹顶点的快速算法,该算法的时间复杂性为O(n)次乘法和O(n)次比较。还介绍把该算法用于求平面点集的凸包以及对任意的平面多边形进行Delaunay三角剖分。 相似文献
3.
并行归并排序算法 总被引: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)。 相似文献
4.
基于数据分布特性的快速排序 总被引:2,自引:0,他引:2
文中提出了一种基于数据分析特性的快速排序算法,根据被排数据的分布行性,选择数据比较次数和数据移动次数较少的排序算法,当被排数据存在m个有序序列时,其算法的时间复杂度为O(nlog2m)其中m∈(1,cf√n),c为某一常数,其最佳性能为O(n)。当m≥c(√n)时,保持快速排序的最佳平均性能,使排序运行于较优状态下。 相似文献
5.
6.
7.
一类扩展的Steiner树优化问题及其应用 总被引:1,自引:0,他引:1
本文提出了一个计算机网络通信和分布式系统中的一类扩展的Steiner树问题.对此问题设计了两个求其最优解的算法.这两个算法的时间复杂性分别是O(3(k-1)·n+2(k-1)·n2)和O(2(n-k)·n2).其中,k是一棵Steiner树需支撑的给定顶点的个数. 相似文献
8.
可重构造的网孔机器上的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. 相似文献
9.
基于有向生成树的分布式选举算法 总被引:1,自引:0,他引:1
吴辉 《计算机研究与发展》1995,32(8):15-19
本文提出了一种在任意网络拓扑下的分布式选举算法,假定系统存在一个网络拓扑的有向生成树,将此有向生成树作为一个同步机械,减少了不必要的消息传送。对于由n台处理机组成的分布式系统,算法的消息复杂度为O(n)。该算法在常量因子下是最优的。 相似文献
10.
钟诚 《计算机工程与科学》1998,20(4):42-45
本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法:将长度为n的待排序数据划分成p个长度为n/p的子序列,引入散列技术并行地对这p个子序列的数据进行二次散列排序,这一阶段所需的平均时间为O(n/p);最后并行地将p个有序子序列归并成一个长度为n的有序序列,归并阶段所需的时间为O(n-n/
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。 相似文献
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。 相似文献
11.
完全欧几里德距离变换的最优算法 总被引:12,自引:2,他引:12
欧几里德距离变换(EDT)对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离,应用于图象分析,计算机视觉,在本文之前,该问题的最好复杂度为O(n^2logn)。本文提出了一个复杂度为O(n^2)的算法,使复杂度达到最优,该算法可以并行化,在有r个处理单元的EREWPRAM计算模型上,若rlogr≤22/6n,则时间复杂度为O(n/r)否则为O(nlogr)。 相似文献
12.
13.
事务内存是一种新的易于使用的同步技术,能使多线程程序高效地并行执行,目前大多数事务内存系统都处于研究实验阶段,尚未具备实际应用价值,或需要依赖特殊硬件实现。针对该现状,提出一种利用C#语言设计与实现的纯软件的事务内存系统,包括事务对象定义以及对事务对象的并行访问方法,并给出处理事务冲突的策略。实验结果表明,该系统是一种高效简洁的同步实现机制。 相似文献
14.
针对我们提出的以最小代价为目标的分布式数据库数据分布模型,进行适当的数据分组,并对部份组进行排序,使单目运算,双目运算的计算复杂度分别提高了O(n)和O(n^2)。更新运算分解后计算复杂度提高O(n)。 相似文献
15.
最长公共子充列问题的改进快速算法 总被引:1,自引:0,他引:1
现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(mp))。这里M、n为两个待比较字符串的长度,P是最长公共子串的长度。给出一种时间复杂度为O(p(mp)),空间复杂度为O(m+n)的算法。与以前的算法相比,不管在P〈〈m的情况下,还是在P接近M时,这种算法都有更快的速度。 相似文献
16.
17.
最小生成树的高效异步并行算法 总被引:1,自引:0,他引:1
在MIMD-SM并行计算模型上,本文给出了时间复杂性为O(n(n/p+logp))的最小生成树的异步并行算法,其中n,p(1≤p≤n)分别表示图的顶点数和处理机的个数。 相似文献
18.
19.
判定点集是否在多边形内部的算法 总被引:4,自引:0,他引:4
周培德 《计算机研究与发展》1997,34(9):672-674
本文提出了判定n个点的点集S是否落入多边形L内部的算法,该算法的复杂性为:max(O(mn),O(ln log n))比比较和O(ln)次乘法,其中m是L的顶点数,l为S的凸包层数。 相似文献
20.
本文在一个EREW PRAMexclusive read exclusive write paralled random access machine)上提出一个并行快速排序算法,这个算法用K个处理器可将N个项目在平均O(n/k+logn)logn)时间内排序,所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是O(nlogn)。 相似文献