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 11: | Line 11: | ||
* amount of information provided by an oracle. | * amount of information provided by an oracle. | ||
There are two fundamental ways of | There are two fundamental ways of measuring complexity | ||
;Complexity of | ; 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> | |||
;Complexity of problems: | |||
=== Decision problems === | === Decision problems === | ||
Revision as of 08:16, 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]
- Complexity of problems