一种构造Hasse图的高效算法

目前在国内外的文献上,关于Hasse图的构造方法都是基于纯粹的数学矩阵变换方法,而非计算机算法,其缺点是不论最好还是最坏情况,其时间复杂度都是0（n3）,进而无法为特殊情况作出优化。这里给出一种构造Hasse图的通用高效算法。该方法从计算机算法的角度对矩阵中单个元素进行计算,当矩阵中所需计算的元素较少时,算法的时间复杂度会相应的降低,在最好的情况下,时间复杂度将接近O(n2),而在最坏的情况下,时间复杂度仍保持在0（n3）。     

基于粗糙集理论的决策表属性约简算法

属性约简是粗糙集理论的一个重要内容,是进行知识获取中的核心问题之一.本文在粗糙集理论的基础上构造了区分图,在区分图上以属性的重要度作为启发信息,快速缩小搜索空间,求解最小属性约简.给出了一个最坏情况下时间复杂度为max（O（｜C｜^2）,O（｜C‖U｜^2））的快速属性约简算法.该算法统一考虑一致性决策表和不一致性决策表两种情况下的属性约简.     

典型"稳定婚姻问题"的简明矩阵算法实现

对于典型“稳定婚姻问题”,借助矩阵（二维数组）给出了一种简明的实现方法．在本算法中,所采用的存储结构和实现方法灵活巧妙,通俗易懂,方便实现;而且用于存储所要处理数据的内存空间相对于其它一些算法节省了一半,空间复杂度为O（1）;由于存储结构的巧妙性,算法的时间复杂度在最好的情况下为线性时间N,在最坏的情况下为O（N^2）．     

覆盖平面上给定点集的最小凸多边形的算法

研究求覆盖平面上给定的若干个点的最小凸多边形的算法．给出了两种算法，讨论了算法的基本思想，描述了算法步骤，得出了算法的时间复杂度．结果表明，算法的平均计算时间复杂度为平面上给定点的数量的线性函数，即为Ο（ｎｍ），在最坏情况下可为Ο（ｍ２）     

对刚体图象生成算法的分析

对刚体图象生成算法从理论上了探讨。首先建立了该算法的相应的数学模型，多面手推出其复杂度函数Ｓ（ｎ）在最坏情况下所满足的递归系统。     

装箱问题的概率近似算法

研究了一维装箱问题的在线近似算法,给出了一种新的半在线算法：随机适应算法（简称RF算法）,说明了RF算法的时间复杂度是O（n^2）,一般情况下的性能比〈1.75。     

几种求关键路径算法的分析

分别从算法的时间复杂度、空间复杂度、数据结构形式以及实现的难易程度等方面分析了几种求关键路径算法的优劣．表明三种算法的时间复杂度分别为：O（n＋e）,O（n^2）,O（n＋e^2／n）．     

求解凸二次规划的一种二阶Mehrotra型预估一校正算法

给出了求解凸二次规划的一种二阶Mehrotra型预估一校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O（n^3/2log（x^0）^TS^0/ε）.     

分布式选举算法

提出了一种基于任意网络拓扑的分布式选举领导人算法，每一处理机既不知道系统的网络拓扑，也不知道系统中处理机的台数。对于由ｎ台处理机组成的分布式系统，算法的消息复杂度最好为３＃Ｅ，最坏不超过＃Ｅ（２Ｎ＋１）－Ｎ＋ｎ；对于同步分布式系统；其时间复杂度最好不超过３（ｎ－１）Δｔ，最坏不超过４（ｎ－１）Δｔ。     

寻找最小生成树的度优先算法

利用Ｋｒｕｓｋａｌ和Ｐｒｉｍ算法的优点，从图的每个顶点的度数入手，采取删除某些无用边的思想方法，给出了一个寻找最小生成树的算法。算法的最坏复杂度为Ｏ（ｍ－ｎ）ｌｏｇｍ），平均复杂度为Ｏ（（ｍ－ｎ）ｌｏｇｎ），就复杂度的常数因子而言，均优于Ｋｒｕｓｋａｌ算法与ｋｉｍ算法，其中ｍ为图的边数，ｎ为图的顶点数。     

识别三种非环数据库模式的分布式算法

对α－，β－，Ｂ－这几种非环数据库模式，在分布式环境给出如何识别它们的算法ＤＢＦＰＲＵＮＥ。该算法最坏的消息复杂度是Ｏ（ｎ＾２＋ｍ），而最坏的时间复杂度是Ｏ（ｎ＾２），其中ｎ是网络中结点的个数，ｍ是网络上边的个数。     

一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位，这个问题的最直接解法是先将序列排序，从而能得到第K个元素，最少需O(nlogn)次比较，即时间复杂度为O(nlogn)．比较好的方法是采用分治策略解决该同题，但其最坏时间复杂度为O(n^2)，平均时间复杂度为O(2n)．本文提出一种Byte解决第K个元素问题的算法，该算法的平均时间复杂度为O(n n／255)，优于以前对该问题的求解方法，而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集．     

分布式选举算法

提出了一种基于任意网络拓扑的分布式选举领导人算法。每一处理机既不知道系统的网络拓扑，也不知道系统中处理机的台数。对于由ｎ台处理机组成的分布式系统，算法的消息复杂度最好为３＃Ｅ，最坏不超过＃Ｅ（２Ｎ＋１）－Ｎ＋ｎ；对于同步分布式系统，其时间复杂度最好不超过３（ｎ－１）△ｔ，最坏不超过４（ｎ－１）△ｔ。     

基于超立方体Q_n节点编码的边不交最优路径

基于超立方体节点编码的特点,得到了n维超立方体Qn中任意两节点s、t之间的两条并行最优路径算法.该算法共包括了11步骤,在最坏的情况下需要执行2n2+4n2次运算,它的时间计算复杂度为O(n2),属于多项式算法.     

按位归"档"排序算法研究

针对传统排序算法的比较思想 ,提出了一种简单而快速的排序算法 ,尤其在非均匀分布下的数据效果更加明显 ,该算法在最坏情况下待排数据较多较大时的时间复杂度为O(n) .     

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

基于灰度统计值的遥感影像快速中值滤波算法

提出一种新的遥感影像快速中值滤波算法,并对不同的中值滤波算法进行比较分析。普通快速中值滤波算法利用相邻窗口的相关性,减少排序次数。本算法抛开排序,通过构造长度与滤波窗口大小相同的一维数组,利用各灰度级的统计值,由中值特性获取窗口中值,从而大大提高算法的效率。对于n＊n的滤波窗口,本算法可将算法复杂度由O（n4）降至O（n2）,进一步利用相邻窗口的相关性,可将复杂度降低至O（n）。     

利用矩阵搜索求所有最长公共子序列的算法

利用动态规划法求出二维数组的情况下,使用矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法．该算法将通常认为的指数量级的时间复杂度降低到了max{O（cmn）,O（ck）}．随后对此算法的正确性以及效率做了证明．     

删除值相同元素的时间复杂度的改进算法

一个顺序表中的数据按元素非递减有序排列,对删除此顺序表中的值相同的元素算法进行了改进,使算法时间复杂度由O（n2）变成O（n）.并用C语言给出了算法的详细实现。     

自由作业问题的一种启发式算法及最坏性能比分析

研究具有准备时间的自由作业问题，给出一种简单的启发式算法，证明 在此启发式算法上，最坏性能比是2－1／m（其中m是机器的参数），且上界是紧的。从而证明了对该问题的猜想：即在贪婪算法的情况下其最坏性能比是2－1／m（其中m是机器的台数），且上界是紧的。特别当m＝2时，具有准备时间的自由作业问题，利用该启发式算法得到最坏性能比是3／2，其上界也是紧的。