%0 Journal Article %A 李美安 %A 武鹏 %T 具有O(n)时间复杂度的分布式请求集生成算法 %D 2013 %R 10.3724/SP.J.1087.2013.00323 %J 计算机应用 %P 323-360 %V 33 %N 02 %X 在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。 %U http://www.joca.cn/CN/10.3724/SP.J.1087.2013.00323