锐客网

  1. 首页 > 睿知 > it技术 > >

图论（比较网络）

IT知识

比较网络由电线和比较器组成。比较器是具有两个输入x和y以及两个输出x’ 和y’ 的设备, 其中
x’ =最小值（x, y）y’ =最大值（x, y）
在“比较网络”中, 输入出现在左侧, 输出出现在右侧, 最小的输入值出现在顶部的输出中, 最大的输入值出现在底部的输出。每个比较器以O（1）时间运行。换句话说, 我们认为输入值x和y的出现与输出值x’ 和y’ 的产生之间的时间是恒定的。
电线从一个地方传送一个值。一个比较网络包含n条输入线a1, a2, … . an, 要通过其排序的收益进入网络, n条输出线b1, b2, … bn产生结果由网络计算。

图论（比较网络）

文章图片
比较网络是一组通过电线互连的比较器。比较器的运行时间可以定义深度。
线的深度：比较网络的输入线的深度为0。现在, 如果比较器的两条输入线的深度为dx和dy’ , 则其输出线的深度为max（dx, dy）+ 1。
排序网络是一个比较网络, 对于该比较网络, 每个输入序列的输出序列都将单调递增（即b1≤b2≤… . bn）。
【图论（比较网络）】图：基于插入排序的排序网络
图论（比较网络）

文章图片

    推荐阅读


    上一篇：图论（最大二分匹配）

    下一篇：双调的排序网络