3

我的作业文档中有一个问题，我很难想象和理解这个问题。问题如下：

我们可以将具有 c 个比较器的 n 输入比较网络表示为从 1 到 n 范围内的 c 对整数的列表。如果两个对包含一个共同的整数，则网络中相应比较器的顺序由列表中对的顺序决定。给定这个表示，描述一个 O(n + c) 时间（串行）算法来确定比较网络的深度。

在比较网络的上下文中，整数对意味着什么？通常我们使用下面的符号来表示一个比较网络，其中每条水平线代表一个数字。

在此处输入图像描述

4

2 回答 2

3

这意味着如果你有一对 (1, 2)，那就是其中一条垂直线，即连接水平线 1 和 2 的那条。

所以这张图片的左上部分将表示为 (1, 2) (3, 4) (1, 3) (2, 4)。

左上部分

仅该部分的深度为 2。

于 2014-05-22T12:10:57.687 回答
2 
for i = 1, n 
  depth[i] = 0

total_depth = 0
for j = 1, c
  i1 = comparators[j].entry1
  i2 = comparators[j].entry2
  new_depth = 1 + max(depth[i1], depth[i2])
  depth[i1] = new_depth
  depth[i2] = new_depth
  total_depth = max(total_depth, new_depth)

print(total_depth)
于 2014-05-22T12:24:10.040 回答