算法的复杂性分析方法通常有两种:(1)最坏情况分析;(2)平均情况分析。最坏情况分析给出的是算法关于某一最坏输入实例的复杂性估计。如果算法的最坏输入实例在实际应用中很少遇到,那么仅用算法的最坏情况分析结果来说明算法在实际应用中的性能就不够了。另一方面,算法的平均情况分析所考虑的随机输入实例具有某一假设的概率分布,如果这样的概率分布在实际应用中难以遇到或无法确定,那么,用算法的平均情况分析结果来说明算法在实际应用中的性能就缺乏说服力。Spielman和Teng提出了算法的复杂性平滑分析方法。算法的复杂性平滑分析方法不同于最坏情况分析和平均情况分析。对算法的复杂性进行平滑分析时,考虑算法的输入实例受到某种程度的随机扰动(例如方差很小的高斯随机扰动)并作为输入实例提供给算法。因此,算法的复杂性与输入的规模和扰动的幅度有关,通常把它表示成输入规模和扰动幅度的函数,称为算法的平滑复杂性。从直观上来说,算法的平滑复杂性是算法关于各输入实例受到某种随机扰动后所产生的随机邻域上的平均复杂性的上确界。由于在实际的计算环境中存在着随机干扰(即随机扰动),因此,如果在算法的复杂性分析中所考虑的随机扰动模型切合实际,那么,算法的复杂性平滑分析可以从理论上更好地说明算法在实际应用中的性能。Spielman和Teng对“两阶段投影顶点”单纯形算法的时间复杂性进行平滑分析,合理地解释了单纯形算法有指数阶的最坏时间复杂性与它在实际应用中却很有效之间的矛盾。除了单纯形算法外,还有许多的算法,这些算法的最坏情况复杂性很糟但在实际应用中却很有效。算法的复杂性平滑分析开辟了算法复杂性分析研究领域的新方向。本文在算法的复杂性分 I<WP=5>析研究领域所做的研究工作涉及以下三个方面:算法的复杂性平滑分析、在线调度算法的竞争比分析和最小击中集问题的随机近似算法的设计与分析。主要工作陈述如下:(1)求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法)。用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3)。如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行算法。需要如此高的精度是因为在消元过程中可能产生异常大的中间项。然而,在实际应用中,这样的现象是罕见的。矩阵条件数和增长因子是高性能计算中求解大规模线性系统Ax = b 时需要考虑的重要因 ˉ素。这是因为异常大的条件数和增长因子是导致矩阵Aˉ病态继而导致消元过程中产生异常大中间项的主要根源。本文在高斯随机扰动模型下,对矩阵条件数和运行高斯算法所需机器精度位数的平滑分析做进一步的研究,提出并证明了两个不等式,简化了Sankar等人关于矩阵条件数平滑分析的结果,部分解决了Sankar等人提出的有关改进矩阵条件数平滑分析结果的猜想。在此基础上降低了Sankar等人关于运行高斯算法所需机器精度位数的平滑复杂性,并通过实验进行比较说明。(2)本文在0-保留高斯随机扰动模型下,进一步研究了对称矩阵条件数及运行高斯算法所需的机器精度位数的平滑分析。简化了Sankar等人关于对称矩阵条件数的平滑分析结果。部分解决了Sankar等人提出的关于改进矩阵条件数平滑分析结果的猜想。并分别用简化前和简化后的对称矩阵条件数平滑分析结果,分析了运行高斯算法求解线性系统Ax = b(其中A为对称矩阵)所需机器精度位数的平滑复杂性,并通过实验进行比较说明。(3)本文在离散算法的复杂性平滑分析方面进行了研究,并从实际的应用背景出发,提出一个随机扰动模型(在本文中简称TSSP模型),用于对算法的输入实例是一个元素序列而算法的复杂性主要取决于其输入实例中的元素排列顺序这样一类离散算法的复杂性平滑分析。并证明快速排序算法在TSSP模型下其时间平滑复杂性为O(λn · log(n)),其中λ表示随机扰 2动的幅度。 II<WP=6>(4)由于在线算法的竞争分析通常对最坏输入实例进行的,其分析结果与实际应用中观察到的竞争比往往相差太大。因此,Becchetti等人指出,对在线算法竞争比进行平滑分析是很有必要的。可见,在线算法分析在算法复杂性平滑分析研究中有重要意义。为此,本文研究多处理机环境下的作业调度问题。在线作业调度算法的竞争比分析中,作业的流动时间及作业的延迟比是用来度量调度算法性能优劣的两个主要指标。作业的延迟比是指作业从进入系统到完成所需要的时间与作业的执行时间之比。作业的平均延迟比是作业的延迟比总和与作业数之比值(等价地,作业的延迟比总和)。作业的平均延迟比能更直观更合理地反映在线调度算法性能的优劣。本文证明了Avrahami等人提出的在线调度算法IMD对于最小化作业平均延迟比具有常数竞争比。 (5)本文研究随机扰动模型M(m,n,k)产生的随机k ? SAT实例的若干性质及子句密度与可满足性之间的关系,证明了当子句密度足够大时,随机k ? SAT实例的不可满足性判定可以归结到最小k ? Hitting Sets问题的求解。 (6)Franco等人在文[62]中给出基于平均度数的最小3?Hitting