Asymptotic complexity of algorithms: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 9: Line 9:
== Input parameters ==
== Input parameters ==


For the inputs of an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], one or more characterizing (numerical) parameters are needed, from which the total size of an input can be computed.
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).
# The number of elements in [[Sets and sequences|sets, maps, and sequences]]
# The number of elements in [[Sets and sequences|sets, maps, and sequences]]
# The (maximum) size of an element in a set, map, or sequence.
# The (maximum) size of an element in a set, map, or sequence.


== Asymptotic complexity ==
== Asymptotic complexity ==

Revision as of 11:59, 28 May 2015

Corresponding page on the original wiki (to be ported asap):

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

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.

Input 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).

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

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.

  1. In the worst case: by the function [math]\displaystyle{ f:\mathbb{N}^k\rightarrow\mathbb{R}^+ }[/math] such that the maximum number of operations [math]\displaystyle{ f(n_1,\ldots,n_k) }[/math]
  2. best case:
  3. average case:

Remar

  1. 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,