首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
可重构造的网孔机器上的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.  相似文献   

2.
完全欧几里德距离变换的最优算法   总被引:12,自引:2,他引:12  
陈Leng 《计算机学报》1995,18(8):611-616
欧几里德距离变换(EDT)对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离,应用于图象分析,计算机视觉,在本文之前,该问题的最好复杂度为O(n^2logn)。本文提出了一个复杂度为O(n^2)的算法,使复杂度达到最优,该算法可以并行化,在有r个处理单元的EREWPRAM计算模型上,若rlogr≤22/6n,则时间复杂度为O(n/r)否则为O(nlogr)。  相似文献   

3.
并行归并排序算法   总被引:3,自引:0,他引:3  
构造效率为O(1)的并行算法是一个引人注目的问题。[1]和[2]分别提出了并行度为O(logn)和O(n^1/2)的、效率为O(1)的并行排序算法。本文提出一种新的并行排序算法,其效率为O(1),而并行步数小于[1]和[2]的算法的并行步数。经过改进后,在保持效率为O(1)的情况下,可进一步将并行度扩大到O(n^1/2log n)。  相似文献   

4.
基于散列和归并技术的有效并行排序方法   总被引:1,自引:1,他引:1       下载免费PDF全文
本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法:将长度为n的待排序数据划分成p个长度为n/p的子序列,引入散列技术并行地对这p个子序列的数据进行二次散列排序,这一阶段所需的平均时间为O(n/p);最后并行地将p个有序子序列归并成一个长度为n的有序序列,归并阶段所需的时间为O(n-n/
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。  相似文献   

5.
基于数据分布特性的快速排序   总被引:2,自引:0,他引:2  
文中提出了一种基于数据分析特性的快速排序算法,根据被排数据的分布行性,选择数据比较次数和数据移动次数较少的排序算法,当被排数据存在m个有序序列时,其算法的时间复杂度为O(nlog2m)其中m∈(1,cf√n),c为某一常数,其最佳性能为O(n)。当m≥c(√n)时,保持快速排序的最佳平均性能,使排序运行于较优状态下。  相似文献   

6.
研究了在N个顶点的图中,仅给出了所有顶点对之间最短路径距离矩阵,而计算任两顶点间最短路径问题。这种算法因没有利用原始图中有关边的信息,被称为重构算法。本研究取得了如下成果:①在单一的顶点对之间最短路径重构的时间复杂度为O(nlogn);②在所有顶点对之间的最短路径重构的时间复杂度为O(n^3);③在带有n/logn个处理器的独占读写并行随机访问器上,单一顶点对之间的最短路径重构时间复杂度为O((l  相似文献   

7.
二维模式近似匹配的快速算法   总被引:1,自引:0,他引:1       下载免费PDF全文
给定一个大小为n×n的文本T和一个大小为m×m的模板P,如果文本T中存在一个m×m的子块与模板P能够逐点匹配,称为精确匹配。如果最多有k个元素不同,称为带有最多k个误差的近似匹配。对于精确匹配,本文给出了一个时间复杂性为O(n2log|∑|)的算法,∑={a1,2,…,a|∑|},是模板的字符集。对于近似匹配,快速算法分为两步:(1)预选。利用精确匹配算法找出能精确匹配的s×s(0≤s≤m)子块,得到h个候选的对准点;(2)验证。把模板对准候选点,逐点比较,以确定不相同的元素是否不超过k个。近似匹配的时间复杂性为O(n2log|∑|+hm2)。  相似文献   

8.
本文给出了满足三角不等式的货郎担问题的并行启发式算法,在SIMD CREV PRAM并行机上该算法使用O(n^3/log^2n)台处理器需O熄log^2n)时间,这里n是给定城市的个数,因而该并行算法是最优的。  相似文献   

9.
以比较为基础的快速排序(quicksort)算法,其复杂性为O(NlogN)。本文结合概率论知识,提出分组散列查找算法,给出算法描述,其算法复杂性为O(N),从而优于快速排序算法。最后给出实验结果和BASIC程序。  相似文献   

10.
针对分布式数据库系统的并发控制,文章提出了一种新算法。本算法根据新事务与本地节点上已启动但还未完成的事务信息的比较,动态地在一种称为EWL(exclusivewriterprotocolwithlockingoption)的乐观并发控制算法与一种称为PSL(primarysitelocking)的悲观并发控制算法之中选择一种算法来实现对该新事务的并发控制。本算法是在文[1]中提出的EWL算法的基础上修改而成的,它比原来的EWL算法具有更强的自适应性,不仅适合冲突较少的情形,也适合冲突较多的情形。  相似文献   

11.
分“档”快速排序算法研究   总被引:3,自引:0,他引:3  
文章在文献[1]的基础上,提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法——分“档”快速排序法。算法分析和实验结果都表明:在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到O(n),而附加存储空间开销却仅仅为[(n+1)/2],同时排序速度明显优于Quick Sort[2]、快速分组排序[5]、分“档”统计插入排序[1]和 Proportion  Split Sort[4]等算法。  相似文献   

12.
EasyPack/S 8052F仿真器是MICETEK公司在Easy-Pack 8052F基础之上开发的新一代产品。 EasyPack/S8052F仿真器继续支持8051系列的处理器,并在此基础上扩展了Bank Switch功能。每个Bank为64KB,最多可将程序区扩大到256KB。其比较数据如表1所示。IEasxPack/S 8052F主模块 EasyPack和EasvPack/S主模块适用B前所有的EasyPack ICE cable仿真头。主模块包括仿真控制模块(分别为ECBllSA-8052或…  相似文献   

13.
区间索引是随着对约束数据库的实用化的研究而提出的。文中在Meta-树的基础上提出了DM-树和相应算法,它对区间索引保持了存储为O(n),查询I/O时间为O(logn+t/B)的性能,  相似文献   

14.
一类扩展的Steiner树优化问题及其应用   总被引:1,自引:0,他引:1  
本文提出了一个计算机网络通信和分布式系统中的一类扩展的Steiner树问题.对此问题设计了两个求其最优解的算法.这两个算法的时间复杂性分别是O(3(k-1)·n+2(k-1)·n2)和O(2(n-k)·n2).其中,k是一棵Steiner树需支撑的给定顶点的个数.  相似文献   

15.
随着Internet及Web技术的普及、应用和迅速发展,Web页面创作已成为广大网友关注的焦点。几年前,本人乘兴而来,涉足网海,如今致力于创作属于自己的Web。日久天长,搜寻并积累了一些经验技巧,略加赘述,期望达到抛砖引玉的目的。一、页面链接1.链接控制返回前页:使用OnClick=″history.go(-1)″返回主页:使用OnClick=′top.location.href=″../chinamail.html″′2.链接提示在链接语句中增加OnMouseOver=″window.st…  相似文献   

16.
武继刚 《微机发展》1995,5(3):11-13
本文基于数排序的思想,从高位关键字开始,对m位关键字的n个记录进行扫描,给出了一个多元选择算法,算法的最坏复杂度为O(m(n+r)),但平均复杂度为O(n+r)。  相似文献   

17.
ECRMKnockOut4550获大奖ECRMKnockOut4550被《印前新闻》(PrePressNews)评为“96年输出机之星”。最近在伦敦CommonwealthInstitute由《印前新闻》杂志主办的96印前活动中,ECRM最新的Kno...  相似文献   

18.
其中所有的参数都取自EnumSes-sions,系统每收到一个回复的消息便调用一次EnumSession,并在结构LPDPSE-SSIONDESC中添入适当的值。以下是EnumSessionsCallback的程序实例。BOOLFARPASCALEnumsession(LPDPSESSIONDESClpDPGameDesc,LPVOIDlpContext,LPDWORDlpdwTimeout,DWORDdwFlags){LONGilndex:HWNDhwnd=(HWND)lpCon-text;/…  相似文献   

19.
至今为止,帝国时代系列游戏全球销量已经达到850万美元。帝国时代系列游戏由EnsembleStudios工作组开发制作、Microsoft公司发行的即时战略游戏,包括:《帝国时代》(Age ofEmpires简称AOE)、《罗马复兴》(The RiseofRome简称ROR)、《帝王时代》(Age of Kings,简称AOK)和《征服者》(The Conquerors简称AOC)四个版本。 Microsoft的《帝国时代》(Age ofEmpires)发行于1997年,EnsembleStudios…  相似文献   

20.
毛张燕 《计算机应用》1999,19(11):62-62
Delphi中按钮(Button)事件有单击(OnClick,鼠标左键单击)、按下鼠标(OnMouseDown)、放开鼠标(OnMouseUp)等。如何响应鼠标右键单击和左右键同时按下的事件呢?下面用简单的例子作以介绍。·区分鼠标左、右键单击事件鼠标最常用事件是单击,但若想使程序具有个人特色,可以考虑让鼠标响应各种不同的事件。建一个窗口Form1,其中含有一个按钮Button1和一个标签Label1(其初始Caption为“Init”)。在Button1的OnClick事件中写语句:Label…  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号