一类混合算法的时间复杂度分析

近年来,许多学者对设计混合算法求解复杂问题感兴趣。混合算法被越来越多的学者所重视。然而,大部分有关混合算法的工作都集中于实验研究,几乎没有混合算法的理论分析工作。本文分析一类混合算法的时间复杂度。这些混合算法是结合两个基本算法而得。通过分析首达时间向量m的∞-范数,我们得到这类混合算法时间复杂度的上下界。这些界是混合算法参数ω与基本算法相应范数的函数。当ω趋于0或1时,这些界是非平凡的。

Time Complexity Analysis of a Kind of Hybrid Algorithms

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.