- Source: Computational complexity of mathematical operations
The following tables list the computational complexity of various algorithms for common mathematical operations.
Here, complexity refers to the time complexity of performing computations on a multitape Turing machine. See big O notation for an explanation of the notation used.
Note: Due to the variety of multiplication algorithms,
M
(
n
)
{\displaystyle M(n)}
below stands in for the complexity of the chosen multiplication algorithm.
Arithmetic functions
This table lists the complexity of mathematical operations on integers.
On stronger computational models, specifically a pointer machine and consequently also a unit-cost random-access machine it is possible to multiply two n-bit numbers in time O(n).
Algebraic functions
Here we consider operations over polynomials and n denotes their degree; for the coefficients we use a unit-cost model, ignoring the number of bits in a number. In practice this means that we assume them to be machine integers.
Special functions
Many of the methods in this section are given in Borwein & Borwein.
= Elementary functions
=The elementary functions are constructed by composing arithmetic operations, the exponential function (
exp
{\displaystyle \exp }
), the natural logarithm (
log
{\displaystyle \log }
), trigonometric functions (
sin
,
cos
{\displaystyle \sin ,\cos }
), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are analytic and hence invertible by means of Newton's method. In particular, if either
exp
{\displaystyle \exp }
or
log
{\displaystyle \log }
in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.
Below, the size
n
{\displaystyle n}
refers to the number of digits of precision at which the function is to be evaluated.
It is not known whether
O
(
M
(
n
)
log
n
)
{\displaystyle O(M(n)\log n)}
is the optimal complexity for elementary functions. The best known lower bound is the trivial bound
Ω
{\displaystyle \Omega }
(
M
(
n
)
)
{\displaystyle (M(n))}
.
= Non-elementary functions
== Mathematical constants
=This table gives the complexity of computing approximations to the given constants to
n
{\displaystyle n}
correct digits.
Number theory
Algorithms for number theoretical calculations are studied in computational number theory.
Matrix algebra
The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic or operations on a finite field.
In 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.
Transforms
Algorithms for computing transforms of functions (particularly integral transforms) are widely used in all areas of mathematics, particularly analysis and signal processing.
Notes
References
Further reading
Kata Kunci Pencarian:
- Daftar masalah matematika yang belum terpecahkan
- Herbert Simon
- Optimisasi multiobjektif
- Computational complexity of mathematical operations
- Computational complexity
- Computational complexity theory
- Computational complexity of matrix multiplication
- Computational mathematics
- Computational topology
- Computational physics
- Model of computation
- Time complexity
- Randomized algorithm
