排序網絡中的比較器列表

我的作業文檔中有一個問題，我很難花時間來想象和理解問題。問題如下：排序網絡中的比較器列表

我們可以表示一個n輸入比較網絡以c比較器，範圍從1到n的整數的C ^對一個列表。如果兩個對包含一個共同的整數，網絡中相應的比較器的順序由該列表中中對的順序決定。給定這種表示，描述用於確定比較網絡的深度的O（n + c）時間（連續）算法。

在比較網絡的環境中有什麼意思是有整數對的意思？通常我們使用下面的符號來表示比較網絡，其中每條水平線表示一個數字。

enter image description here

來源

2014-05-22 Mert Toka

（2,3）意味着有線2和線之間的比較器3 –

這意味着，如果有一對（1,2），這是那些垂直線中的一個，即所以連接水平線1和2

左上部分中的一個（1，2）（3,4）（1,3）（2,4）。

top left part

只是部分的深度是2

來源

2014-05-22 12:10:57 harold

感謝。但還有一件事，我應該怎麼知道（1,2）和（3,4）是通過查看數字來平行的？他們也可以在整個網絡中的其他地方串行，對嗎？ –

另外，部分「如果兩對共同包含一個整數，則網絡中相應比較器的順序由列表中對的順序決定。」意味着如果在答案中有（1,2）和（1,3），它們的順序應與圖片中的順序相同。我對嗎？ –

@MertToka是的。發生的事情是部分順序是由這些約束引起的，因此（1，2）和（3，4）*可能會被排序，例如，如果您將（1，3）*置於中間*與他們一起下令。在這裏的例子中，（1，2）和（3，4）是無序的，因爲1）它們沒有共同之處，2）它們之間沒有任何內容，它們隱含地命令它們。 – harold

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-22 12:24:10

你有沒有10k代表的帳戶？這是多少錢？ – harold

@harold - 回答[here]（http://stackoverflow.com/questions/23654734/sorting-ipv4-address-with-port-number/23654950#comment36337301_23654950） –

排序網絡中的比較器列表

回答

相關問題