Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
AmirOnWiki (talk | contribs) |
||
Line 15:
==Decision tree complexity==
The number of comparisons needed to solve the problem of size <math>n</math>, in a comparison-based model of computation such as a [[decision tree]] or [[algebraic decision tree]], is <math>\Theta(n\log n)</math>. Here, <math>\Theta</math> invokes [[Big O notation|big theta notation]], meaning that the problem can be solved in a number of comparisons proportional to <math>n\log n</math> (a [[linearithmic function]]) and that all solutions require this many comparisons.<ref>{{citation|first=Michael|last=Ben-Or|contribution=Lower bounds for algebraic computation trees|title=[[Symposium on Theory of Computing|Proc. 15th ACM Symposium on Theory of Computing]]|year=1983|pages=80–86|doi=10.1145/800061.808735|doi-access=free}}.</ref> In these models of computation, the input numbers may not be used to index the computer's memory (as in the hash table solution) but may only be accessed by computing and comparing simple algebraic functions of their values. For these models, an algorithm based on [[comparison sort]] solves the problem within a constant factor of the best possible number of comparisons. The same lower bound applies as well to the [[expected value|expected number]] of comparisons in the [[randomized complexity|randomized]] [[algebraic decision tree]] model.<ref>{{citation|doi=10.1007/BF01270387|title=A lower bound for randomized algebraic decision trees|year=1996|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=6|pages=357|last2=Karpinski|first2=Marek|author2-link=Marek Karpinski|last3=Heide|first3=Friedhelm Meyer|last4=Smolensky|first4=Roman|issue=4}}.</ref><ref>{{citation|doi=10.1007/s000370050002|title=Complexity lower bounds for randomized computation trees over zero characteristic fields|year=1999|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=8|pages=316–329|issue=4}}.</ref>
==Real RAM Complexity==
If the elements in the problem are [[real number|real numbers]], the decision-tree lower bound extends to the [[real RAM|real random-access machine]] model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor")<ref>{{citation|doi=10.1137/S0097539797329397|title=Topological Lower Bounds on Algebraic Random Access Machines|year=2001|last1=Ben-Amram|first1=Amir M.|journal=SIAM Journal on Computing|volume=31|issue=3|pages=722-761|last2=Galil|first2=Zvi|author2-link=Zvi Galil}}.</ref>. This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions.
==Quantum complexity==
| |||