一类混合算法的时间复杂度分析（英文）  

Time Complexity Analysis of a Kind of Hybrid Algorithms

作　　者：赖鑫生[1] 

机构地区：[1]上饶师范学院,江西上饶334001

出　　处：《上饶师范学院学报》2014年第6期83-89,共7页Journal of Shangrao Normal University

基　　金：国家自然科学基金(61165003)

摘　　要：近年来,许多学者对设计混合算法求解复杂问题感兴趣。混合算法被越来越多的学者所重视。然而,大部分有关混合算法的工作都集中于实验研究,几乎没有混合算法的理论分析工作。本文分析一类混合算法的时间复杂度。这些混合算法是结合两个基本算法而得。通过分析首达时间向量m的∞-范数,我们得到这类混合算法时间复杂度的上下界。这些界是混合算法参数ω与基本算法相应范数的函数。当ω趋于0或1时,这些界是非平凡的。In recent years,many researchers are interested in designing hybrid algorithms to solve complex problems. Hybrid algorithms are receiving increasingly attention from more and more researchers. However,the bulk of work on hybrid algorithms focus on experimental research,there is rare work on theoretical analysis of hybrid algorithms. In this paper,we analyze the time complexity of a kind of hybrid algorithms. By analyzing the first hitting time vector m＇s ∞- norm,we obtained the upper and lower bounds of the time complexity for this kind of hybrid algorithms. These bounds of the hybrid algorithms combining two base algorithms are functions of the hybrid algorithms＇ parameter ω and the corresponding norms of the base algorithms. These boundaries are nontrivial when ω is close to 0 or 1.

关 键 词：混合算法 时间复杂度 首达时间 马尔科夫链 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]