Asymptotic complexity of algorithms: Difference between revisions
Jump to navigation
Jump to search
| Line 22: | Line 22: | ||
## In the '''best case''': by the function <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance is <math>\mathcal{I}(n_1,\ldots,n_k)</math>. | ## In the '''best case''': by the function <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance is <math>\mathcal{I}(n_1,\ldots,n_k)</math>. | ||
## In the '''average case''': For this case, a [[http://en.wikipedia.org/wiki/Probability_distribution probability distribution]] over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. Then the asymptotic average complexity is the function <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm for any instance is <math>\mathcal{I}(n_1,\ldots,n_k)</math>. | ## In the '''average case''': For this case, a [[http://en.wikipedia.org/wiki/Probability_distribution probability distribution]] over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. Then the asymptotic average complexity is the function <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm for any instance is <math>\mathcal{I}(n_1,\ldots,n_k)</math>. | ||
Revision as of 12:32, 28 May 2015
Corresponding page on the original wiki (to be ported asap):
Asymptotic complexity vs. run time
Roughly speaking, the run time of an algorithm is measured by the number of operations executed by the machine. However, in theoretical considerations, the run time is estimated by the algorithm's asymptotic complexity. In asymptotic considerations, constant multiplicative factors are completely disregarded. Therefore, it does not matter how fast the machine and how smart the algorithm's implementation is.
Characterizing parameters
For the inputs of an algorithmic problem, one or more characterizing (numerical) parameters are to be selected, from which the total size of an input can be computed (or, at least, quite tightly bounded from above and from below).
Examples:
- The number of elements in sets, maps, and sequences and the (maximum) size of an element in a set, map, or sequence.
- The number of nodes and the number of edges/arcs in a graph.
Asymptotic complexity
- For a selection of [math]\displaystyle{ k }[/math] characterizing parameters for an algorithmic problem, let [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math] denote the set of all instances for which these parameters assume the values [math]\displaystyle{ n_1,\ldots,n_k }[/math].
- For an algorithm for this algorithmic problem, the asymptotic complexity of the algorithm with respect to this selection of characterizing parameters is defined as follows.
- In the worst case: by the function [math]\displaystyle{ f:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that [math]\displaystyle{ f(n_1,\ldots,n_k) }[/math] is the maximum number of operations executed by the algorithm for any instance is [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math].
- In the best case: by the function [math]\displaystyle{ f:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that [math]\displaystyle{ f(n_1,\ldots,n_k) }[/math] is the minimum number of operations executed by the algorithm for any instance is [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math].
- In the average case: For this case, a [probability distribution] over each set [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math] is required. Then the asymptotic average complexity is the function [math]\displaystyle{ f:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that [math]\displaystyle{ f(n_1,\ldots,n_k) }[/math] is the expected number of operations executed by the algorithm for any instance is [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math].