选择网络延迟时间的一个新上界  

A NEW UPPER BOUND OF DELAY TIME IN SELECTION NETWORK

作　　者：沈鸿[1] 陈国良[1] 

机构地区：[1]中国科学技术大学计算机系

出　　处：《计算机学报》1990年第2期88-100,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(技-85217)

摘　　要：本文通过将递归网络E′(m,n)按树形展开,应用组合计数方法导出了(m,n)选择网络(1≤m<n)延迟时间的一个新的上界。(当n≤4m),(当n》m)和O(log^2m)(当2m≤n≤4m),该止界改进了选择网络目前所如最好的A.C.Yao的时间上界)当(n>m)和(当n》m)。Through tree representation of the recursive network E(m, n) and the combinatorial enumeration, a new upper bound of delay time in the (m,n) selection network (1≤m≤n) is derived which is logn+logm log log (n/m)+ 0(log2mloglogm + log mlogloglog n/m) when n > 4m, log n+log mloglog(n/m) + O(logloglogn) when n》m, and O (log2m) when 2m≤n≤4m. It is an improvement over A. C. Yao's best result

关 键 词：选择网络 延迟时间 

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