Asymptotic complexity of algorithms: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(32 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Corresponding page on the original wiki (to be ported asap):
[[Category:Videos]]
 
{{#ev:youtube|https://www.youtube.com/watch?v=dpgkYeSXSPI|500|right||frame}}
http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Asymptotic_complexity_of_algorithms.html
 
== Asymptotic complexity vs. run time ==
== Asymptotic complexity vs. run time ==


Roughly speaking, the run time of an algorithm is measured by the number of [[Algorithms and correctness#Operations and instructions|operations]] executed by the machine. However, in theoretical considerations, the run time is estimated by the algorithm's '''asymptotic complexity'''. In [[Asymptotic comparison of functions|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.
# Roughly speaking, the run time of an algorithm is measured by the number of [[Algorithms and correctness#Instructions, operations and subroutines|operations]] executed by the machine.
# However, in theoretical considerations, the run time is estimated by the algorithm's '''asymptotic complexity'''. In [[Asymptotic comparison of functions|asymptotic]] considerations, constant multiplicative factors are completely disregarded. For that, it does not matter how fast the machine and how smart the algorithm's implementation is.


== Characterizing parameters ==
== Characterizing parameters ==


For the inputs of an [[Algorithms and correctness#Algorithmic problem|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).
For the inputs of an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], one or more (numerical) '''characterizing 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:'''
'''Examples:'''
Line 15: Line 14:
# The number of nodes and the number of edges/arcs in a [[Basic graph definitions#Directed and undirected graphs|graph]].
# The number of nodes and the number of edges/arcs in a [[Basic graph definitions#Directed and undirected graphs|graph]].


== Asymptotic complexity ==
== Asymptotic complexity of an algorithm ==


# For a selection of <math>k</math> characterizing parameters for an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], let <math>\mathcal{I}(n_1,\ldots,n_k)</math> denote the set of all instances for which these parameters assume the values <math>n_1,\ldots,n_k</math>.
# For a selection of <math>k</math> characterizing parameters for an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], let <math>\mathcal{I}(n_1,\ldots,n_k)</math> denote the set of all [[Algorithms and correctness#Algorithmic problem|instances]] for which these parameters assume the values <math>n_1,\ldots,n_k</math>.
# For an [[Algorithms and correctness#Algorithm|algorithm]] for this algorithmic problem,  the '''asymptotic complexity''' of the algorithm with respect to this selection of characterizing parameters is defined as follows.
# For an [[Algorithms and correctness#Algorithm|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>f:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f(n_1,\ldots,n_k)</math> is the ''maximum'' number of operations executed by the algorithm for any instance is <math>\mathcal{I}(n_1,\ldots,n_k)</math>.
## In the '''worst case''': by the function <math>f_\max:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\max} (n_1,\ldots,n_k)</math> is the ''maximum'' number of operations executed by the algorithm for any instance in <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 '''best case''': by the function <math>f_\min:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\min}(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.
## In the '''average case''':
## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.
 
== Bounds on the asymtptotic complexity ==
 
Consider an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], a selection of <math>k</math> [[#Characterizing parameters|characteristizing parameters]], and an [[Algorithms and correctness#Algorithm|algorithm]] for this algorithmic problem.  Moreover, let <math>f_\max</math>, <math>f_\min</math>, and <math>f_P</math> be defined as [[#Asymptotic complexity of an algorithm|above]].


== Input size and polynomial complexity ==
For a function <math>f_1:\mathbb{N}^k\rightarrow\mathbb{R}^+</math>, we say that the algorithm's complexity (the algorithm, for short) is in <math>\oplus(g)</math>
# in the worst case, if <math>f_{\max}\in\oplus(g)</math>,
# in the best case, if <math>f_{\min}\in\oplus(g)</math>,
# in the average case with respect to <math>P</math>, if <math>f_P\in\oplus(g)</math>,
where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".


The size of an input is the
== Asymptotic complexity analysis of an algorithm ==


For a given [[Algorithms and correctness#Algorithmic problem|input]],
An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.

Latest revision as of 05:54, 25 April 2016

Asymptotic complexity vs. run time

  1. Roughly speaking, the run time of an algorithm is measured by the number of operations executed by the machine.
  2. However, in theoretical considerations, the run time is estimated by the algorithm's asymptotic complexity. In asymptotic considerations, constant multiplicative factors are completely disregarded. For that, 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 (numerical) characterizing 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:

  1. The number of elements in sets, maps, and sequences and the (maximum) size of an element in a set, map, or sequence.
  2. The number of nodes and the number of edges/arcs in a graph.

Asymptotic complexity of an algorithm

  1. 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].
  2. 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.
    1. In the worst case: by the function [math]\displaystyle{ f_\max:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that [math]\displaystyle{ f_{\max} (n_1,\ldots,n_k) }[/math] is the maximum number of operations executed by the algorithm for any instance in [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math].
    2. In the best case: by the function [math]\displaystyle{ f_\min:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that [math]\displaystyle{ f_{\min}(n_1,\ldots,n_k) }[/math] is the minimum number of operations executed by the algorithm for any instance in [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math].
    3. In the average case: For this case, a probability distribution [math]\displaystyle{ P_{n_1,\ldots,n_k} }[/math] over each set [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math] is required. For short, let [math]\displaystyle{ P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}} }[/math]. Then the asymptotic average complexity is the function [math]\displaystyle{ f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that [math]\displaystyle{ f_P(n_1,\ldots,n_k) }[/math] is the expected number of operations executed by the algorithm, taken over all instances in [math]\displaystyle{ \mathcal{I}(n_1,\ldots,n_k) }[/math], with respect to the distribution [math]\displaystyle{ P_{n_1,\ldots,n_k} }[/math].

Bounds on the asymtptotic complexity

Consider an algorithmic problem, a selection of [math]\displaystyle{ k }[/math] characteristizing parameters, and an algorithm for this algorithmic problem. Moreover, let [math]\displaystyle{ f_\max }[/math], [math]\displaystyle{ f_\min }[/math], and [math]\displaystyle{ f_P }[/math] be defined as above.

For a function [math]\displaystyle{ f_1:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math], we say that the algorithm's complexity (the algorithm, for short) is in [math]\displaystyle{ \oplus(g) }[/math]

  1. in the worst case, if [math]\displaystyle{ f_{\max}\in\oplus(g) }[/math],
  2. in the best case, if [math]\displaystyle{ f_{\min}\in\oplus(g) }[/math],
  3. in the average case with respect to [math]\displaystyle{ P }[/math], if [math]\displaystyle{ f_P\in\oplus(g) }[/math],

where "[math]\displaystyle{ \oplus }[/math]" is one of "[math]\displaystyle{ \mathcal{O} }[/math]", "[math]\displaystyle{ o }[/math]", "[math]\displaystyle{ \Omega }[/math]", and "[math]\displaystyle{ \Theta }[/math]".

Asymptotic complexity analysis of an algorithm

An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of function class ([math]\displaystyle{ \mathcal{O} }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math], [math]\displaystyle{ o }[/math]) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.