# Complexidade computacional de operações matemáticas

As tabelas a seguir listam o tempo de execução de vários algoritmos para operações matemáticas comuns.
Aqui, a complexidade refere-se à complexidade de tempo de execução de cálculos em uma máquina de Turing multifita. Ver a notação de Grande-O para uma explicação sobre a notação usada.
Nota: Em virtude da variedade de algoritmos de multiplicação, M(n) fica abaixo na complexidade do algoritmo de multiplicação escolhido.

## Funções aritméticas

| Operações | Entrada | Saída | Algoritmo | Complexidade |
| Adição | Dois números com n dígitos | Um número com n + 1 dígitos | Schoolbook adição com estouro | Θ(n) |
| Subtração | Dois números com n dígitos | Um número com n + 1 dígitos | Schoolbook subtração com empréstimo | Θ(n) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | Schoolbook multiplicação | O(n$^2$) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | Algoritmo Karatsuba | O(n$^{1.585}$) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | 3-forma de multiplicação de Toom–Cook | O(n$^{1.465}$) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | k-forma de multiplicação de Toom–Cook | O(n$^{log(2k−1)/logk}$) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | Nível mixado de Toom–Cook (Knuth 4.3.3-T) | O(n 2$^{√2logn}$ log n) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | Algoritmo Schönhage–Strassen | O(n log n log log n) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | Algoritmo de Fürer | O(n log n 2) |
| Multiplicação | Dois números com n dígitos | Um número com 2n dígitos | Algoritmo de Harvey e van der Hoeven | O(n log n) |
| Divisão | Dois números com n dígitos | Um número com n dígitos | Schoolbook divisão | O(n$^2$) |
| Divisão | Dois números com n dígitos | Um número com n dígitos | divisão de Newton–Raphson | O(M(n)) |
| Raiz quadrada | Um número com n dígitos | Um número com n dígitos | método de Newton | O(M(n)) |
| Exponenciação modular | Dois números com n dígitos e um expoente com k-bit | Um número com n dígitos | Multiplicação repetida e redução | O(M(n) 2$^k$) |
| Exponenciação modular | Dois números com n dígitos e um expoente com k-bit | Um número com n dígitos | Exponenciação por raiz quadrada | O(M(n) k) |
| Exponenciação modular | Dois números com n dígitos e um expoente com k-bit | Um número com n dígitos | Exponenciação com redução Montgomery | O(M(n) k) |

## Funções algébricas

| Operações | Entrada | Saída | Algoritmo | Complexidade |
| Avaliação polinomial | Um polinômio de grau n com coeficientes do polinômio de tamanho fixo | Um número de tamanho fixo | Avaliação direta | Θ(n) |
| Avaliação polinomial | Um polinômio de grau n com coeficientes do polinômio de tamanho fixo | Um número de tamanho fixo | Método de Horner | Θ(n) |
| Mdc polinomio (mais que Z[x] ou F[x]) | Dois polinômios de grau n com coeficientes do polinômio de tamanho fixo | Um polinômio de grau no máximo n | algoritmo de Euclides | O(n$^2$) |
| Mdc polinomio (mais que Z[x] ou F[x]) | Dois polinômios de grau n com coeficientes do polinômio de tamanho fixo | Um polinômio de grau no máximo n | Algoritmo de Euclides Rápido | O(n (log n)$^2$ log log n) |

## Funções especiais

Muitos dos métodos desta seção são dadas em Borwein & Borwein.

### Funções elementares

As funções elementares são construídas através da composição de operações aritméticas, a função exponencial (exp), o logaritmo natural (log), funções trigonométricas (seno, cosseno), e seus inversos. A complexidade de uma função primária é equivalente ao do seu inverso, uma vez que todas as funções elementares são analíticas e, portanto, invertidas por meio do método de Newton. Em particular, se quer exp ou log no domínio dos complexos, pode ser calculado com alguma complexidade, em seguida, que a complexidade é atingível para todas as outras funções elementares.
A seguir, o tamanho n refere-se ao número de dígitos de precisão em que a função será avaliada.
| Algoritmo | Aplicabilidade | Complexidade |
| Série de Taylor; repetida redução do argumento (e.g. exp(2x) = [exp(x)]$^2$) e soma direta | exp, log, seno, cosseno, arctan | O(M(n) n$^{1/2}$) |
| Série de Taylor; TFR-aceleração baseada | exp, log, seno, cosseno, arctan | O(M(n) n$^{1/3}$ (log n)$^2$) |
| Série de Taylor; divisão binária + estouro de bit método | exp, log, sin, cos, arctan | O(M(n) (log n)$^2$) |
| Média aritmética-geométrica iteração | exp, log, seno, coss, arctan | O(M(n) log n) |
Não se sabe se o O (M (n) log n) é a complexidade óptima para as funções elementares. O mais conhecido é o limite inferior trivial Ω ligado (M (n)).

### Funções não-elementares

| Função | Entrada | Algoritmo | Complexidade |
| Função Gamma | n número de digitos | Aproximação da série da função gama incompleta | O(M(n) n$^{1/2}$ (log n)$^2$) |
| Função Gamma | Número racional fixo | Serie hipergeométrica | O(M(n) (log n)$^2$) |
| Função Gamma | m/24, m um inteiro | Média aritmética-geométrica iteração | O(M(n) log n) |
| Função hipergeométrican $_p$F$_q$ | n número de digitos | (Como descrito em Borwein & Borwein) | O(M(n) n$^{1/2}$ (log n)$^2$) |
| Função hipergeométrican $_p$F$_q$ | Número racional fixo | Serie hipergeométrica | O(M(n) (log n)$^2$) |

### Constantes matemáticas

Esta tabela mostra a complexidade da computação aproximações às constantes dadas a n dígitos corretos.
| Constante | Algoritmo | Complexidade |
| razão de ouro, φ | Método Newton | O(M(n)) |
| Raiz quadrada de 2, √2 | Método de Newton | O(M(n)) |
| número de Euler, e | divisão binária de série de Taylor para a função exponencial | O(M(n) log n) |
| número de Euler, e | Inversão do logaritmo natural de Newton | O(M(n) log n) |
| Pi, π | Divisão binária da série arctan em fórmula de Machin | O(M(n) (log n)$^2$) |
| Pi, π | Algoritmo de Salamin–Brent | O(M(n) log n) |
| constante de Euler, γ | Método de Sweeney's(Aproximação em termos de integral exponencial) | O(M(n) (log n)$^2$) |

## Teoria dos números

Algoritmos para número teórico cálculos são estudadas em teoria dos números computacional.
| Operação | Entrada | Saída | Algoritmo | Complexidade |
| MDC | Two n número de dígitos | Um número com, no máximo, n dígitos | Algoritmo Euclideano | O(n$^2$) |
| MDC | Two n número de dígitos | Um número com, no máximo, n dígitos | Algoritmo MDC binário | O(n$^2$) |
| MDC | Two n número de dígitos | Um número com, no máximo, n dígitos | Algoritmo binário MDC- esquerda/direita k- ario | O(n$^2$/ log n) |
| MDC | Two n número de dígitos | Um número com, no máximo, n dígitos | Algoritmo de Stehlé–Zimmermann | O(M(n) log n) |
| MDC | Two n número de dígitos | Um número com, no máximo, n dígitos | Algoritmo de descida euclidiana controlada por Schönhage | O(M(n) log n) |
| Símbolo de Jacobi | dois n número de dígitos | 0, −1, ou 1 |
| Símbolo de Jacobi | dois n número de dígitos | 0, −1, ou 1 | Algoritmo de descida euclidiana controlada por Schönhage | O(M(n) log n) |
| Símbolo de Jacobi | dois n número de dígitos | 0, −1, ou 1 | Algoritmo de Stehlé–Zimmermann | O(M(n) log n) |
| Fatorial | Um número de tamanho fixo m | Um O(m log m) número de dígitos | Multiplicação de baixo para cima | O(m$^2$ log m) |
| Fatorial | Um número de tamanho fixo m | Um O(m log m) número de dígitos | Divisão binária | O(M(m log m) log m) |
| Fatorial | Um número de tamanho fixo m | Um O(m log m) número de dígitos | Exponenciação dos fatores primos de m | O(M(m log m) log log m), O(M(m log m)) |

## Matriz algébrica

As seguintes figuras de complexidade assumem que a aritmética com elementos individuais tem complexidade O (1), como é o caso com precisão fixa aritmética de ponto flutuante.
| Operação | Entrada | Saída | Algoritmo | Complexidade |
| Matriz de multiplicação | Duas matrizes n×n | Uma matrizn×n | Schoolbook matriz de multiplicação | O(n$^3$) |
| Matriz de multiplicação | Duas matrizes n×n | Uma matrizn×n | Algoritmo de Strassen | O(n$^{2.807}$) |
| Matriz de multiplicação | Duas matrizes n×n | Uma matrizn×n | Algoritmo de Coppersmith–Winograd | O(n$^{2.376}$) |
| Matriz de multiplicação | Duas matrizes n×n | Uma matrizn×n | Algoritmos CW-like otimizado | O(n$^{2.373}$) |
| Matriz de multiplicação | Uma matriz n×m & uma matrizm×p | Uma matriz n×p | Schoolbook matriz de multiplicação | O(nmp) |
| Matriz de inversão | Uma matriz n×n | Uma matrizn×n | Eliminação de Gauss–Jordan | O(n$^3$) |
| Matriz de inversão | Uma matriz n×n | Uma matrizn×n | Algoritmo de Strassen | O(n$^{2.807}$) |
| Matriz de inversão | Uma matriz n×n | Uma matrizn×n | Algoritmo de Coppersmith–Winograd | O(n$^{2.376}$) |
| Matriz de inversão | Uma matriz n×n | Uma matrizn×n | Algoritmo CW-like otimizado | O(n$^{2.373}$) |
| Determinante | Uma matriz n×n | Um número | Expansão de Laplace | O(n!) |
| Determinante | Uma matriz n×n | Um número | Decomposição LU | O(n$^3$) |
| Determinante | Uma matriz n×n | Um número | Algoritmo de Bareiss | O(n$^3$) |
| Determinante | Uma matriz n×n | Um número | Matriz de multiplicação rápida$^[$ | O(n$^{2.373}$) |
| Substituição regressiva | Matriz triangular | n soluções | Substituição regressiva | O(n$^2$) |
Em 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy e Chris Umans mostraram que qualquer uma das duas conjecturas diferentes implicaria que o expoente da multiplicação de matrizes seria 2.
↑ * Por causa da possibilidade de por blocos inverter uma matriz, onde uma inversão de uma n × n matriz requer inversão de duas matrizes com metade do tamanho e seis multiplicações entre duas matrizes com metade do tamanho, e uma vez que a multiplicação de matrizes tenha um limite inferior de Ω ( n $^2$ Predefinição:Var log) operações, pode ser demonstrado que o algoritmo de dividir e conquistar que usa a inversão por blocos para inverter uma matriz é executado com a mesma complexidade de tempo que o algoritmo de multiplicação de matrizes que é usado internamente.