n個對象的等價測試

假設我們給了'n'個對象和一個接受兩個輸入的子例程，並說它們是否相等（例如，如果它們相等，它可以給出輸出爲1）。n個對象的等價測試

我需要想出一個算法，它調用上述函數O（n log n）次並決定輸入是否有多於'n/2'的項目彼此等效。

2014-10-02 cardamom

'爲O（n log n）的'通常暗示朝向以某種方式排序。這個子程序真的只是爲了等於還是比較兩個，所以你可以使用它來進行排序？ – Sirko 2014-10-02 09:23:19

有一個解決方案需要O（n）比較。 – 2014-10-02 11:46:13

這裏是一個經典的分而治之溶液其給出爲O（n log n）的

分裂成兩個子集，A1和A2，...，並顯示T（N）是O（n log n）的。如果A具有多數元素v，則v也必須是A1或A2的多數元素或兩者。等價的反向正面重述是立即的:(如果v是< =每個是一半，那麼它是< =總數的一半）。如果兩個部分具有相同的多數元素，則它自動成爲A的主要元素。如果的部分有一個多數元素，計算兩個部分中該元素的重複次數（在O（n）時間）以查看它是否是多數元素。如果兩部分都有多數，你可能需要爲這兩個候選人中的每一個做這個計數，仍然是O（n）。這種分割可以遞歸地完成。基本情況是當n = 1時。一個遞歸關係是T（n）= 2T（n/2）+ O（n），所以T（n）是O（n log n）。

http://anh.cs.luc.edu/363/handouts/MajorityProblem.pdf

來源

2014-10-24 06:21:44 cardamom

-2

考慮到序列是有序的，你可以使用binary search，這需要O(log n)，因爲你必須做的每一個元素，你必須n元素將採取O(n*log n)。

來源

2014-10-02 11:32:05

比較器似乎沒有提供訂購信息。 – 2014-10-02 14:14:53

什麼比較器？「 – 2014-10-02 14:25:17

」子程序需要兩個輸入，並說他們是否等價「 – 2014-10-02 14:25:33

您可以使用Boyer-Moore多數票表決算法，它最多可以進行n-1次比較。

function find_majority(A) 
    majority = None 
    count = 0 
    for a in A: 
     if count == 0 
      majority = a 
     else if a == majority 
      count += 1 
     else 
      count -= 1 
    return majority

如果在數組中出現超過n/2次，它將返回最常見的元素。

如果您需要知道是否有是多數項目，那麼您可以再次通過數組，計算從find_majority函數返回的值的次數。這又增加了n個比較。

來源

2014-10-02 11:42:51

n個對象的等價測試

回答

相關問題