元素唯一性問題

元素唯一性問題（英語：element distinctness/uniqueness problem）是計算複雜性理論中判斷列表內所有元素是否唯一的問題。關於這一問題的研究已經完備，可以通過許多不同的計算模型解決。其中一種方法就是通過給列表排序，檢驗是否存在連續相等元素；也可以藉由隨機化算法將元素插入哈希表中，比較放在哈希表相同位置元素，從而在線性時間複雜度解決這一問題。^[1]通過將問題轉化為查找問題可以最大程度優化算法的時間複雜度。

決策樹的複雜度

已知對於一組數字列表，其時間複雜度是O(n log n)，或言之其時間複雜度的界限由代數決策樹（英語：algebraic decision tree）模型的線性對數所決定^[2]，而在決策樹模型中數據不一定需要存入內存（插入哈希表中），只需要計算和比較運算樹節點的代數值，這一解法又被稱之為漸進最優算法。這一算法可以進一步優化為隨機代數決策樹（英語：algebraic decision tree）。^[3][4]

查找重複元素

查找在在含有n項元素的多重集合（multiset）中查找出現超過n/k次的元素所需的時間複雜度為O(n log k)，而元素唯一性問題是前一問題在k=n時的一個特例，決策樹是這種算法的理想解決方案。^[5]這種算法可以看成多數投票法（k=2時的特例）的一種歸納推演，兩者在研究歷史上關係相依。^[6]

上述算法僅僅依賴於檢驗識別元素，如果可以排序，那麼就可以利用基於順序統計量的搜索算法。比方說，當k=2時，查找中位數的時間複雜度最低，進而方便檢測是否有多餘n/2個中位數元素，這種算法的比較次數比順序統計算法來的少。^[6]

相關條目

• 碰撞問題（英語：Collision problem）

參考資料

1. Gil, J.; Meyer auf der Heide, F.; Wigderson, A., Not all keys can be hashed in constant time, Proc. 22nd ACM Symposium on Theory of Computing（英語：Symposium on Theory of Computing）: 244–253, 1990, doi:10.1145/100216.100247.
2. Ben-Or, Michael, Lower bounds for algebraic computation trees, Proc. 15th ACM Symposium on Theory of Computing（英語：Symposium on Theory of Computing）: 80–86, 1983, doi:10.1145/800061.808735.
3. Grigoriev, Dima; Karpinski, Marek; Heide, Friedhelm Meyer; Smolensky, Roman, A lower bound for randomized algebraic decision trees, Computational Complexity, 1996, 6 (4): 357, doi:10.1007/BF01270387.
4. Grigoriev, Dima, Complexity lower bounds for randomized computation trees over zero characteristic fields, Computational Complexity, 1999, 8 (4): 316–329, doi:10.1007/s000370050002.
5. Misra, J.; Gries, D., Finding repeated elements, Science of Computer Programming, 1982, 2 (2): 143–152, doi:10.1016/0167-6423(82)90012-0, hdl:1813/6345 .
6. Boyer, R. S.; Moore, J S., MJRTY - A Fast Majority Vote Algorithm, Boyer, R. S. (編), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers: 105–117, 1991.