考慮整數對 (x,y)。我們施加一個偏序使得 (x,y) ≤ (x',y') wrt。x ≤ x' 和 y ≤ y' 的偏序。如果 (x,y) ≤ (x',y') 和 (x',y') ≤ (x,y)，我們就說 (x,y) 和 (x',y') 是不可比的。
現在，我有一個ls這樣對的串列。我想檢查該串列的順序是否優化了上面定義的偏序；即，我需要檢查串列中任何元素的右側，沒有更小的元素。
當然，我可以執行以下操作：
def leq_po(u,v):
return all(a <= b for a, b in zip(u,v))
def le_po(u,v):
return leq_po(u,v) and u != v
def list_refines_po(ls):
return all(not le_po(ls[j], ls[i])
for i in range(len(ls)) for j in range(i 1, len(ls)))
但是，然后給我某種 O(n2) 復雜度，同時檢查串列是否已排序。總訂單需要 O(n) 時間。
現在，可能，這就是我所期望的：部分訂單概括了總訂單，所以可能，我應該期望檢查更一般的概念具有更糟糕的復雜性。但：
我能做得比 O(n2) 更好嗎？
編輯 試試，你可以使用以下資料：
ls_in_order = [(0, 1), (2, 1), (3, 0), (2, 1)]
ls_not_in_order = [(0, 1), (2, 1), (3, 0), (1, 1)]
在這里，沒有一對連續的條目ls_not_in_order是降序的，但串列沒有按順序排列（因為(2,1) ≥ (1,1)）。
uj5u.com熱心網友回復：
使用Kahn 演算法對偏序進行排序，在每一步都嘗試選擇全序中的下一個。如果成功，則總訂單將細化偏序。如果你失敗了，那就不會了。
的時間將是O(v e)其中v是頂點的數目，并且e是定義偏序向邊的數量。
uj5u.com熱心網友回復：
您可以O(n log n)使用平衡的 BST以及該BST的前驅/后繼輔助雙鏈表及時完成此操作。
這個想法是按全序遍歷點，維護一個資料結構，可以及時告訴你log n我們是否看到了一個點，其 x 和 y 值至少與我們當前的點一樣大。我們將保持一個有序的點序列，這些點(p1, p2, ... pk)的 x 值增加而 y 值減少，形成一種對角線向下和向右階梯線。要添加一個點P = (x,y)（暫時忽略關系），請根據 x 進行二分搜索，然后將 P 插入 BST 和鏈表中，以便 x 值仍在增加。
如果讓 P.left 和 P.right 表示我們序列中點 P 的前驅和后繼，我們可以通過測驗是否 P.right.y >= Py 來檢查 P 是否導致順序違規：如果是，因為 P.right具有更高或相等的 x 值和更高或相等的 y 值，這違反了偏序（再次，現在忽略精確關系）。否則，為了保持 y 值的降序，我們反復從樹和我們的串列中洗掉 P.left，只要 P.left.y <= Py 總的來說，這需要n log n時間，因為我們最終最多執行一次搜索、插入或洗掉每個節點，但某些步驟可能需要比其他步驟更長的時間。
為了處理 x 的系結值，如果 y 的值也系結，我們只檢查偏序違規，并且不更改樹或串列（也不插入 P 的副本）。如果 Py 的值小于舊點的 y，則存在違規。否則，洗掉舊點并像往常一樣檢查違規/更新樹。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/333889.html