跳至內容

元素唯一性問題

維基百科,自由的百科全書

元素唯一性問題(英語: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]

相關條目

參考資料

  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. ^ 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 .