关于递归算法时间复杂度分析的探讨

通过递归实例,介绍了递归算法时间复杂度的一类分析方法.说明了在分析问题时递归思想的作用,但在问题实现时最好采用非递归算法.     

一类约束满足问题及其算法

针对具有解析约束形式、同一变量多赋值的约束满足问题,提出了一种新的约束满足问题定义·通过一种特殊约束满足问题的研究提出一套建立在这个定义基础之上的概念和三种算法:整数规划法、不等式组法和直接求解不定方程法,详细研究了其中的第三种算法,并给出了最坏情况下的时间复杂度,从而能够比较清晰地描述一类约束满足问题的一般分析过程,揭示了约束满足问题同经典的整数规划、数论和整数环论的联系·     

高码率平滑图像质量自适应量化控制算法

针对MPEG-2纯Ⅰ帧编码情况，在MPEG-2TM5自适应量化控制算法的基础上，提出了一种基于平滑图像质量的高码率下自适应量化控制算法。根据已编码帧的复杂度平滑分配各帧目标码字，利用非线性方法使宏块的量化因子变化平缓，以达到高码率下提高图像质量的目的，仿真结果表明，在相同码率下重建图像质量(PSNR)优于TM5算法。     

二叉树CreateBTree算法的改进

在分析二叉树的CreateBTree算法的基础上，利用线性探测再散列方法对CreateBTree算法的中序遍历序列进行预处理来改进CreateBTree算法，使得改进后的CreateBTree算法在最差情况下，时间复杂度由O(N^2)降为O(N)。     

遍历从N个元素中取M个元素可能组合的最佳算法

从N个相异元素中取M个元素(M≤N)的可能组合的遍历问题是组合数学中重要的基础性问题．关于该问题的现行算法是建立在对于搜索到的每一个节点的诸元素首先进行排序，然后搜索下一个节点．本文对于该问题给出一个全新的算法．新算法中放弃了对于节点诸元食的排序，实现每进行一次数据交换即搜索到一个新的节点，因而成为解决该问题的最佳算法．使用该算法编辑计算机程序，有编程简短、占用机器内存小的特点。     

Valiant并行归并及排序时间复杂性的分析研究

深入分析研究著名的Ｖａｌｉａｎｔ并行归并及排序算法，并推导其关于ＥＲＥＷ（异步读写），ＣＲＥＷ（并发读异步写）和ＣＲＣＷ计算模型的修正的时间复杂性结果。     

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

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

一种新的规则获取增量式算法

对新增样例给出了新的分类,针对此分类提出了新的规则获取的增量式学习算法DLR I,并就该算法与经典算法的复杂性进行了分析比较,得出增量学习算法较经典算法有较低的时间复杂性,可以有效地提高大型数据库的规则维护效率.     

基于树形结构酉空时星座设计的译码方法

针对酉空时码最大似然检测复杂度高的问题，提出了一种酉空时星座的设计及低复杂度译码方法．根据酉空时信号失真测度的定义，依照最邻近原则对星座进行划分，以最小失真准则计算各个星座子集中信号的最佳中心，再通过迭代算法，交替使用两个局部最佳准则，生成由各个信号子集与对应中心所构成的若干子树，形成树形结构的酉空时星座．接收方以接收信号为树根，选择具有最小失真的中心信号．对选定的中心信号对应的子树进行遍历搜索得到对发送信号的估值．该译码方法仅需要对某一中心信号及其对应子树的叶子节点进行计算，避免了最大似然方法对整个星座的全搜索，从而有效地降低了译码复杂度．仿真实验表明，相对于最大似然检测方法，该方法能够以有限的性能损失换取译码计算的有效简化．     

不同麻醉深度下大鼠脑活动的复杂性分析

为了研究大鼠在不同麻醉深度下大脑活动的变化，探测麻醉深度对其脑电信号（EEG）的影响，采用KC复杂度和谱熵对不同麻醉深度下的EEG及其4个主要频段信号进行了复杂性分析．结果发现：随着麻醉深度的加深，EEG的KC复杂度和谱熵的值都随之减小，反之亦然，且KC复杂度在区分麻醉深度的变化方面比谱熵更为灵敏、准确；在麻醉状态下，delta频段是EEG信号的优势频段，正是它的动态变化主导了EEG信号的变化过程．