Complexidade computacional de operações matemáticas
 | A tradução deste artigo está abaixo da qualidade média aceitável. (Setembro de 2021) |
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.[1] 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
[editar | editar código-fonte]| 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(n2) |
| Algoritmo Karatsuba | O(n1.585) | |||
| 3-forma de multiplicação de Toom–Cook | O(n1.465) | |||
| k-forma de multiplicação de Toom–Cook | O(nlog (2k − 1)/log k) | |||
| Nível mixado de Toom–Cook (Knuth 4.3.3-T)[2] | O(n 2√2 log n log n) | |||
| Algoritmo Schönhage–Strassen | O(n log n log log n) | |||
| Algoritmo de Fürer[3] | O(n log n 2O(log* n)) | |||
| Algoritmo de Harvey e van der Hoeven[4][5] | O(n log n) | |||
| Divisão | Dois números com n dígitos | Um número com n dígitos | Schoolbook divisão | O(n2) |
| 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) 2k) |
| Exponenciação por raiz quadrada | O(M(n) k) | |||
| Exponenciação com redução Montgomery | O(M(n) k) |
Funções algébricas
[editar | editar código-fonte]| 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) |
| 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(n2) |
| Algoritmo de Euclides Rápido [6] | O(n (log n)2 log log n) |
Funções especiais
[editar | editar código-fonte]Muitos dos métodos desta seção são dadas em Borwein & Borwein.[7]
Funções elementares
[editar | editar código-fonte]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) n1/2) |
| Série de Taylor; TFR-aceleração baseada | exp, log, seno, cosseno, arctan | O(M(n) n1/3 (log n)2) |
| Série de Taylor; divisão binária + estouro de bit método[8] | exp, log, sin, cos, arctan | O(M(n) (log n)2) |
| Média aritmética-geométrica iteração[9] | 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
[editar | editar código-fonte]| 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) n1/2 (log n)2) |
| Número racional fixo | Serie hipergeométrica | O(M(n) (log n)2) | |
| m/24, m um inteiro | Média aritmética-geométrica iteração | O(M(n) log n) | |
| Função hipergeométrican pFq | n número de digitos | (Como descrito em Borwein & Borwein) | O(M(n) n1/2 (log n)2) |
| Número racional fixo | Serie hipergeométrica | O(M(n) (log n)2) |
Constantes matemáticas
[editar | editar código-fonte]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) |
| 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) |
| 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
[editar | editar código-fonte]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(n2) |
| Algoritmo MDC binário | O(n2) | |||
| Algoritmo binário MDC- esquerda/direita k- ario [10] | O(n2/ log n) | |||
| Algoritmo de Stehlé–Zimmermann[11] | O(M(n) log n) | |||
| Algoritmo de descida euclidiana controlada por Schönhage[12] | O(M(n) log n) | |||
| Símbolo de Jacobi | dois n número de dígitos | 0, −1, ou 1 | ||
| Algoritmo de descida euclidiana controlada por Schönhage[13] | O(M(n) log n) | |||
| Algoritmo de Stehlé–Zimmermann[14] | 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(m2 log m) |
| Divisão binária | O(M(m log m) log m) | |||
| Exponenciação dos fatores primos de m | O(M(m log m) log log m),[15] O(M(m log m))[1] |
Matriz algébrica
[editar | editar código-fonte]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(n3) |
| Algoritmo de Strassen | O(n2.807) | |||
| Algoritmo de Coppersmith–Winograd | O(n2.376) | |||
| Algoritmos CW-like otimizado[16][17][18] | O(n2.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(n3) |
| Algoritmo de Strassen | O(n2.807) | |||
| Algoritmo de Coppersmith–Winograd | O(n2.376) | |||
| Algoritmo CW-like otimizado | O(n2.373) | |||
| Determinante | Uma matriz n×n | Um número | Expansão de Laplace | O(n!) |
| Decomposição LU | O(n3) | |||
| Algoritmo de Bareiss | O(n3) | |||
| Matriz de multiplicação rápida[carece de fontes] | O(n2.373) | |||
| Substituição regressiva | Matriz triangular | n soluções | Substituição regressiva | O(n2)[19] |
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.[20]
↑ * 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,[21] 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.[22]
Referências
- ↑ a b A. Schönhage, A.F.W. Grotefeld, E. Vetter: Algoritmos rápidos—Uma implementação de uma máquina de Turing multifita, BI Wissenschafts-Verlag, Mannheim, 1994
- ↑ D. Knuth. The Art of Computer Programming, Volume 2. Terceira edição, Addison-Wesley 1997.
- ↑ Martin Fürer. Faster Integer Multiplication Arquivado em 25 de abril de 2013, no Wayback Machine.. 39º ano do Simpósio sobre Teoria da Computação, San Diego, California, USA, 11 a 13 de Junho, 2007, pp. 55–67.
- ↑ Harvey, David. «Integer multiplication in time O(n log n)». web.maths.unsw.edu.au. Consultado em 24 de novembro de 2021
- ↑ Harvey, David; Van Der Hoeven, Joris (2020). «Integer multiplication in time O(n log n)». Princeton University, Department of Mathematics. Annals of Mathematics. Consultado em 24 de novembro de 2021
- ↑ http://planetmath.org/fasteuclideanalgorithm
- ↑ J. Borwein & P. Borwein. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. John Wiley 1987.
- ↑ David and Gregory Chudnovsky. Approximations and complex multiplication according to Ramanujan. Ramanujan revisited, Academic Press, 1988, pp 375–472.
- ↑ Richard P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, in: Analytic Computational Complexity (J. F. Traub, ed.), Academic Press, New York, 1975, 151–176.
- ↑ J. Sorenson. (1994). «Two Fast GCD Algorithms». Journal of Algorithms. 16 (1): 110–144. doi:10.1006/jagm.1994.1006
- ↑ R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Segunda edição, Springer 2005.
- ↑ Möller N (2008). «On Schönhage's algorithm and subquadratic integer gcd computation» (PDF). Mathematics of Computation. 77 (261): 589–607. doi:10.1090/S0025-5718-07-02017-0
- ↑ Bernstein D J. «Faster Algorithms to Find Non-squares Modulo Worst-case Integers»
- ↑ Richard P. Brent; Paul Zimmermann (2010). «An O(M(n) log n) algorithm for the Jacobi symbol». arXiv:1004.2091
- ↑ P. Borwein. "On the complexity of calculating factorials". Journal of Algorithms 6, 376-380 (1985)
- ↑ Davie, A.M.; Stothers, A.J. (2013), «Improved bound for complexity of matrix multiplication», Proceedings of the Royal Society of Edinburgh, 143A: 351–370, doi:10.1017/S0308210511001648
- ↑ Vassilevska Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier (PDF)
- ↑ Le Gall, François (2014), «Powers of tensors and fast matrix multiplication», Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), arXiv:1401.7714
- ↑ J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.
- ↑ Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. Arxiv. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
- ↑ Ran Raz . No complexidade do produto da matriz. Em Anais do trigésimo quarto simpósio ACM anual sobre Teoria da computação. ACM Press, 2002. doi: 10,1145 / 509.907,509932.
- ↑ T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009, §28.2.
Bibliografia
[editar | editar código-fonte]- Brent, Richard P.; Zimmermann, Paul (2010). Modern Computer Arithmetic. [S.l.]: Cambridge University Press. ISBN 9780521194693
- Knuth, Donald Ervin (1997). The Art of Computer Programming. Volume 2: Seminumerical Algorithms 3rd ed. [S.l.]: Addison-Wesley. ISBN 0201896842