About: Element distinctness problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatPolynomial-timeProblems, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FElement_distinctness_problem

In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation. The problem may be solved by sorting the list and then checking if there are any consecutive equal elements; it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell.

AttributesValues
rdf:type
rdfs:label
  • Element distinctness problem (en)
  • 元素唯一性问题 (zh)
rdfs:comment
  • 元素唯一性问题（英語：element distinctness/uniqueness problem）是計算複雜性理論中判断列表内所有元素是否唯一的问题。关于这一问题的研究已经完备，可以通过许多不同的计算模型解决。其中一种方法就是通过给列表排序，检验是否存在连续相等元素；也可以借由随机化算法将元素插入哈希表中，比较放在哈希表相同位置元素，从而在线性时间复杂度解决这一问题。通过将问题转化为查找问题可以最大程度优化算法的时间复杂度。 (zh)
  • In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation. The problem may be solved by sorting the list and then checking if there are any consecutive equal elements; it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell. (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation. The problem may be solved by sorting the list and then checking if there are any consecutive equal elements; it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell. Several lower bounds in computational complexity are proved by reducing the element distinctness problem to the problem in question, i.e., by demonstrating that the solution of the element uniqueness problem may be quickly found after solving the problem in question. (en)
  • 元素唯一性问题（英語：element distinctness/uniqueness problem）是計算複雜性理論中判断列表内所有元素是否唯一的问题。关于这一问题的研究已经完备，可以通过许多不同的计算模型解决。其中一种方法就是通过给列表排序，检验是否存在连续相等元素；也可以借由随机化算法将元素插入哈希表中，比较放在哈希表相同位置元素，从而在线性时间复杂度解决这一问题。通过将问题转化为查找问题可以最大程度优化算法的时间复杂度。 (zh)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 54 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software