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 13: | Line 13: | ||
There are two fundamental ways of measuring complexity | There are two fundamental ways of measuring complexity | ||
; Complexity of algorithms | ; Complexity of algorithms | ||
:For an algorithm <math>A</math>, its complexity represents its performance. Let <math>T(A,x)</math> be the running time of the algorithm <math>A</math> on input <math>x</math>. The worst case time complexity is given by <math>T(A)=\max_{x}T(A,x)</math>, where the maximum is taken of the domain of the inputs with the fixed length <math>n</math>, and <math>T(A)</math> is | :For an algorithm <math>A</math>, its complexity represents its performance. Let <math>T(A,x)</math> be the running time of the algorithm <math>A</math> on input <math>x</math>. The worst case time complexity is given by <math>T(A)=\max_{x}T(A,x)</math>, where the maximum is taken of the domain of the inputs with the fixed length <math>n</math>, and <math>T(A)</math> is written as a function of <math>n</math>. | ||
:The complexity of an algorithm tells ''how good a solution is''. Theoretically, we measure the goodness of a solution by its time cost in the worst case. In practice, there might be other criteria that we care about. | |||
;Complexity of problems | |||
: | |||
:The complexity of a problem tells ''how hard a problem is''. | |||
=== Decision problems === | === Decision problems === | ||
Revision as of 08:29, 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].
- The complexity of an algorithm tells how good a solution is. Theoretically, we measure the goodness of a solution by its time cost in the worst case. In practice, there might be other criteria that we care about.
- Complexity of problems
- The complexity of a problem tells how hard a problem is.