Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop No edit summary |
imported>WikiSysop No edit summary |
||
| Line 18: | Line 18: | ||
:A computational problem can be formalized as a mapping from inputs to outputs. For a problem <math>f</math>, its time complexity <math>T(f)</math> is defined as the <math>T(A)</math> for the best possible algorithm <math>A</math> that computes <math>f</math>. That is <math>T(f)=\min\{T(A)\mid A\mbox{ computes }f\}</math>. Again, <math>T(f)</math> is represented as a function of the length of the input <math>n</math>. | :A computational problem can be formalized as a mapping from inputs to outputs. For a problem <math>f</math>, its time complexity <math>T(f)</math> is defined as the <math>T(A)</math> for the best possible algorithm <math>A</math> that computes <math>f</math>. That is <math>T(f)=\min\{T(A)\mid A\mbox{ computes }f\}</math>. Again, <math>T(f)</math> is represented as a function of the length of the input <math>n</math>. | ||
The complexity of an algorithm tells ''how good a solution is'', yet the complexity of a problem tells ''how hard a problem is''. While the former is what we care mostly about in practice, the later | The complexity of an algorithm tells ''how good a solution is'', yet the complexity of a problem tells ''how hard a problem is''. While the former is what we care mostly about in practice, the later tells fundamental truths of computation. | ||
=== Decision problems === | === Decision problems === | ||
Revision as of 08:48, 8 January 2010
Computational Models
Upper bounds, lower bounds
Bounds are just inequalities. In Computer Science, when talking about upper or lower bounds, people really mean the upper or lower bounds of complexity.
Complexity is measured by the resource costed by the computation. Our most precious resource is time (life is short!). Besides time complexity, there are other measures of complexity we may care about, including:
- space;
- communication;
- number of random bits;
- number of queries to the input;
- amount of information provided by an oracle.
There are two fundamental ways of measuring complexity
- Complexity of algorithms
- For an algorithm [math]\displaystyle{ A }[/math], its complexity represents its performance. Let [math]\displaystyle{ T(A,x) }[/math] be the running time of the algorithm [math]\displaystyle{ A }[/math] on input [math]\displaystyle{ x }[/math]. The worst case time complexity is given by [math]\displaystyle{ T(A)=\max_{x}T(A,x) }[/math], where the maximum is taken of the domain of the inputs with the fixed length [math]\displaystyle{ n }[/math], and [math]\displaystyle{ T(A) }[/math] is written as a function of [math]\displaystyle{ n }[/math].
- Complexity of problems
- A computational problem can be formalized as a mapping from inputs to outputs. For a problem [math]\displaystyle{ f }[/math], its time complexity [math]\displaystyle{ T(f) }[/math] is defined as the [math]\displaystyle{ T(A) }[/math] for the best possible algorithm [math]\displaystyle{ A }[/math] that computes [math]\displaystyle{ f }[/math]. That is [math]\displaystyle{ T(f)=\min\{T(A)\mid A\mbox{ computes }f\} }[/math]. Again, [math]\displaystyle{ T(f) }[/math] is represented as a function of the length of the input [math]\displaystyle{ n }[/math].
The complexity of an algorithm tells how good a solution is, yet the complexity of a problem tells how hard a problem is. While the former is what we care mostly about in practice, the later tells fundamental truths of computation.