热门问题
时间线
聊天
视角

元素唯一性問題

来自维基百科,自由的百科全书

Remove ads

元素唯一性问题(英语: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]

相关条目

参考资料

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads