Selection Networks
Selection Networks
复制标题
选择网络
DOI：
10.1137/0220054
复制
发表时间：
1990
影响因子：
10.7
通讯作者：
N. Pippenger
中科院分区：
文献类型：
--
作者：
N. Pippenger
为网络中所需的比较器数量建立渐近至 2n log n 的上限，该网络将 n 个值分为两类，每类包含 n/2 个值，一类中的每个值小于或等于另一类中的每个值。 （该问题已知的最佳下界渐近于 (n/2) log2 n。）关键词、比较器、分类器、扩展图、随机游走 AMS(MOS) 主题分类。 68E05、94C10
An upper bound asymptotic to 2n log n is established for the number of comparators required in a network that classifies n values into two classes, each containing n/2 values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to (n/2) log2 n.) Key words, comparator, classifier, expanding graph, random walk AMS(MOS) subject classifications. 68E05, 94C10