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

A NEW UPPER BOUND OF DELAY TIME IN SELECTION NETWORK

本文通过将递归网络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