元素唯一性問題
元素唯一性問題（英語：element distinctness/uniqueness problem）是計算複雜性理論中判斷列表內所有元素是否唯一的問題。關於這一問題的研究已經完備，可以通過許多不同的計算模型解決。其中一種方法就是通過給列表排序，檢驗是否存在連續相等元素；也可以藉由隨機化算法將元素插入哈希表中，比較放在哈希表相同位置元素，從而在線性時間複雜度解決這一問題。[1]通過將問題轉化為查找問題可以最大程度優化算法的時間複雜度。
決策樹的複雜度[編輯]
已知對於一組數字列表，其時間複雜度是O(n log n)，或言之其時間複雜度的界限由代數決策樹模型的線性對數所決定[2]，而在決策樹模型中數據不一定需要存入內存（插入哈希表中），只需要計算和比較運算樹節點的代數值，這一解法又被稱之為漸進最優算法。這一算法可以進一步優化為隨機代數決策樹。[3][4]
查找重複元素[編輯]
查找在在含有n項元素的多重集合（multiset）中查找出現超過n/k次的元素所需的時間複雜度為O(n log k)，而元素唯一性問題是前一問題在k=n時的一個特例，決策樹是這種算法的理想解決方案。[5]這種算法可以看成多數投票法（k=2時的特例）的一種歸納推演，兩者在研究歷史上關係相依。[6]
上述算法僅僅依賴於檢驗識別元素，如果可以排序，那麼就可以利用基於順序統計量的搜索算法。比方說，當k=2時，查找中位數的時間複雜度最低，進而方便檢測是否有多餘n/2個中位數元素，這種算法的比較次數比順序統計算法來的少。[6]
相關條目[編輯]
參考資料[編輯]
- ^ 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: 244–253, 1990, doi:10.1145/100216.100247.
- ^ Ben-Or, Michael, Lower bounds for algebraic computation trees, Proc. 15th ACM Symposium on Theory of Computing: 80–86, 1983, doi:10.1145/800061.808735.
- ^ 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.
- ^ Grigoriev, Dima, Complexity lower bounds for randomized computation trees over zero characteristic fields, Computational Complexity, 1999, 8 (4): 316–329, doi:10.1007/s000370050002.
- ^ 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.0 6.1 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.
