C语言常用排序算法讨论

在平时的程序设计中,排序是我们通常使用的一种数据处理手法,如何巧妙的运行各种排序方法是讨论的问题。     

算法的时间复杂度分析

算法的时间复杂度是衡量一个算法优劣的重要指标.在总结教学经验的基础上,提出了几种计算时间复杂度的方法.     

一种改进的计数排序算法

提出了一种改进的计数排序算法。首先找到待排序记录应该存放的位置,然后在原数组空间上进行交换。与传统的计数排序算法相比,在不改变时间复杂度的同时,降低了空间复杂度,提高了算法性能。     

一种求解矩形packing问题的智能枚举算法

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路（VLSI）布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如：遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明：该算法对求解矩形packing问题是行之有效的。     

电路板布线问题的改进算法

本文针对电路板布线问题的动态规划解法进行了讨论,在给出一般常见的时间和空间复杂度均为o(n2)的算法描述后,进一步讨论了在时间和空间复杂度上都有显著提高的算法(其时间复杂度为o(n*log(k)),空间复杂度为o(n).     

一种判定树同构的BULT算法

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.     

排序算法的分析与比较实现

本文论述了内部排序的几种算法,在思想、时间复杂度、空间复杂度及稳定性方面进行了比较。最后用C#语言比较了几种算法在大量数据中进行排序的比较次数和花费的时间。     

结合优先指派规则的车间作业问题的枚举算法

车间作业调度问题是一个典型的NP完全问题,这种问题的精确求解算法的计算时间会随着问题实例规模的增大而呈指数增加.针对车间作业调度问题的难解性,给出了一个求解该问题的快速枚举算法.该算法是按照枚举算法的一般步骤来进行设计的,在设计过程中对于算法所涉及到的初始解问题、分枝问题以及剪枝策略等问题给出了旨在减少算法计算时间的解决方案.该算法找到了所测试的9个标准算例中4个算例的精确最优解.     

砝码称重问题的多种算法分析与探究

针对算法设计中的砝码称重问题,提出了四种不同的算法,重点从时间复杂度方面对各种算法进行了深入的效率分析,并给出了各种算法的pascal主程序,对其他算法问题的分析解决具有重要的指导意义和实用价值.     

利用多种方法求解数据结构算法问题的评析

2009年计算机专业硕士研究生考试同以往有所改变，数据结构作为一门重要的专业课在考试中占有较高的地位。对于改革后的第一次考试，算法问题在试卷中体现的较为灵活与新颖，其基本目的就是考察学生在不断总结与理解的过程中寻求一个又好又快的算法。本文以09年硕士研究生考试的算法综合题为例，利用多种方法求解并进行综合比较，最终得出既优秀又快捷的算法。     

两个组合计数公式的推广

设x一门，2，…，，；）为一，王元集，组合数【．怖示集合X的是元子集的个数．文献卜」提到一＼k］两个应用问题：问题1求集合X的不含相邻整数的k元子集的个数人，I，足）．问题2从集合X中选八个元素组成子集，要求子集中任二元素之差均不与1模n合同，求这种足元子集的选取方式数g（，；，k）．为便于研究，将上述两问题转化为：问题l’假定有，。个元素排成一行，现从中取出k个，并要求在行中这是个元素中的任意两个之间至少包含1个元．设其选取方式数为人（，。，A），则问题2’假定有，l个元素排成圆圈，现从中取出k个，并要求在圆圈…     

基于容斥原理的群Sn中累计计数问题的探讨

讨论了容斥原理及其推广，在此基础上研究了在限制条件下对称群Sn中累计计数问题及其推广。     

图论算法复杂性问题(一)

本文论述了图论算法复杂性的基本理论和分析方法。由它的表示式和阶的运算,可以分析一个具体问题的算法复杂性,进而明确某一具体算法的有效性。     

一类限位数排列的计数问题

讨论了与客观实际问题密切相关的一类限位圆排列问题，利用广容斥原理，给出了求解这类排列数的一般公式，并讨论了几种特殊情况下的具体解答．     

遍历从N个相异元素中取M个元素可能排列的新算法

给出了遍历从N个相异元素中取M个(N≥M)元素可能排列的新算法．新算法中放弃了首先将全部可能节点进行字典排序，然后按序逐个生成的传统思想，实现了每进行一次数据交换即产生一个新节点，从而极大地提高了遍历的效率。     

Algorithmic criteria for permutation orthogonal systems over finite fields

Two criteria for orthogonal systems over finite fields are presented. The first one is an algorithm by use of Grobner bases. The second one is a formula of the numbers of adjoint morphisms.     

Performance Prediction for Performance-Sensitive Queries Based on Algorithmic Complexity

Performance predictions for database queries allow service providers to determine what resources are needed to ensure their performance. Cost-based or rule-based approaches have been proposed to optimize database query execution plans. However, Virtual Machine （VM）-based database services have little or no sharing of resources or interactions between applications hosted on shared infrastructures. Neither providers nor users have the right combination of visibility/access/expertise to perform proper tuning and provisioning. This paper presents a performance prediction model for query execution time estimates based on the query complexity for various data sizes. The user query execution time is a combination of five basic operator complexities： O（1）, O（log（n））, O（n）, O（nlog（n））, and O（n2）. Moreover, tests indicate that not all queries are equally important for performance prediction. As such, this paper illustrates a performance-sensitive query locating process on three benchmarks： RUBiS, RUBBoS, and TPC-W. A key observation is that performance-sensitive queries are only a small proportion （20%） of the application query set. Evaluation of the performance model on the TPC-W benchmark shows that the query complexity in a real life scenario has an average prediction error rate of less than 10% which demonstrates the effectiveness of this predictive model.     

单人最优巡回路问题算法研究

基于生活实例,引出问题讨论,建立了理论模型及实用简化模型,在BORLANDC环境中编程实现了最小生成树算法和递归穷举法.最后,分析了理论模型的缺陷,并运用递归穷举法对结果进行检验.     

对称旅行售货员问题局部搜索邻域的计数

旅行售货员问题(TSP)是图论、组合最优化和计算机科学中所熟知的.为了分析局部搜索算法的效果而提出如下的计数问题:给定完全图K_n的一个哈密顿圈C??,通过替换其中λ条边,可以得到多少个不同的哈密顿圈呢?[3]的作者已对非对称TSP解决了上述计数问题.本文将就对称TSP这一更困难情形给出相应的结果.