Asymptotic complexity of algorithms: Difference between revisions
| Line 18: | Line 18: | ||
For a selection <math>n_1,\ldots,n_k</math> of characterizing parameters, the '''asymptotic complexity''' of an [[Algorithms and correctness#Algorithm|algorithm]] is defined as follows. | For a selection <math>n_1,\ldots,n_k</math> of characterizing parameters, the '''asymptotic complexity''' of an [[Algorithms and correctness#Algorithm|algorithm]] is defined as follows. | ||
# In the '''worst case''': by the function <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that the maximum number of operations <math>f(n_1,\ldots,n_k)</math> | # In the '''worst case''': by the function <math>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that the maximum number of operations for any <math>f(n_1,\ldots,n_k)</math> | ||
# best case: | # best case: | ||
# average case: | # average case: | ||
| Line 24: | Line 24: | ||
'''Remar | '''Remar | ||
# An algo may have different complexity bounds, based on different parameters | # An algo may have different complexity bounds, based on different parameters | ||
== Input size and polynomial complexity == | == Input size and polynomial complexity == | ||
Revision as of 12:05, 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 [math]\displaystyle{ n_1,\ldots,n_k }[/math] of characterizing parameters, the asymptotic complexity of an algorithm is defined as follows.
- In the worst case: by the function [math]\displaystyle{ f:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that the maximum number of operations for any [math]\displaystyle{ f(n_1,\ldots,n_k) }[/math]
- best case:
- average case:
Remar
- An algo may have different complexity bounds, based on different parameters
Input size and polynomial complexity
The size of an input is the
For a given input,