计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2013年
2期
323-325,360
,共4页
分布式互斥%请求集%松弛差集%时间复杂度
分佈式互斥%請求集%鬆弛差集%時間複雜度
분포식호척%청구집%송이차집%시간복잡도
在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的.在基于松弛差集的相关原理上,引入了二次松弛差集的概念.经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程；进而利用“求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n).与时间复杂度同为O(n2)的其他经典算法相比,生成的请求集长度仍保持在2√n的数量级.
在大規模完全分佈式繫統的互斥問題上,快速生成請求集是必要的.在基于鬆弛差集的相關原理上,引入瞭二次鬆弛差集的概唸.經分析相關概唸及定理,將原本“求差”的過程變為“求和”的過程；進而利用“求和”步驟間的遞推關繫,大大減少瞭求和步驟,使整箇算法的時間複雜度控製在O(n).與時間複雜度同為O(n2)的其他經典算法相比,生成的請求集長度仍保持在2√n的數量級.
재대규모완전분포식계통적호척문제상,쾌속생성청구집시필요적.재기우송이차집적상관원리상,인입료이차송이차집적개념.경분석상관개념급정리,장원본“구차”적과정변위“구화”적과정；진이이용“구화”보취간적체추관계,대대감소료구화보취,사정개산법적시간복잡도공제재O(n).여시간복잡도동위O(n2)적기타경전산법상비,생성적청구집장도잉보지재2√n적수량급.
