3

宿題のドキュメントに質問があり、質問を視覚化して理解するのに苦労しています。質問は次のとおりです。

1 から n の範囲の c 個の整数ペアのリストとして、c 個の比較器を持つ n 入力比較ネットワークを表すことができます。2 つのペアに共通の整数が含まれている場合、ネットワーク内の対応するコンパレータの順序は、リスト内のペアの順序によって決まります。この表現が与えられたとき、比較ネットワークの深さを決定するための O(n + c) 時間 (シリアル) アルゴリズムを説明してください。

比較ネットワークのコンテキストで整数のペアを持つとはどういう意味ですか? 通常、各水平線が数値を表す比較ネットワークを示すために、以下の表記を使用しました。

ここに画像の説明を入力

4

2 に答える 2

3

これは、ペア (1, 2) がある場合、それは垂直線の 1 つ、つまり水平線 1 と 2 を結ぶ線の 1 つであることを意味します。

したがって、この図の左上部分は (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 に答える