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.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 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çõesEntradaSaídaAlgoritmoComplexidadeAdiçãoDois números com n dígitosUm número com n + 1 dígitosSchoolbook adição com estouroΘ(n)SubtraçãoDois números com n dígitosUm número com n + 1 dígitosSchoolbook subtração com empréstimoΘ(n)MultiplicaçãoDois números com n dígitosUm número com 2n dígitosSchoolbook multiplicaçãoO(n2)Algoritmo KaratsubaO(n1.585)3-forma de multiplicação de Toom–CookO(n1.465)k-forma de multiplicação de Toom–CookO(nlog (2k − 1)/log k)Nível mixado de Toom–Cook (Knuth 4.3.3-T)D. Knuth. The Art of Computer Programming, Volume 2. Terceira edição, Addison-Wesley 1997.O(n 2 log n)Algoritmo Schönhage–StrassenO(n log n log log n)Algoritmo de FürerMartin Fürer. Faster Integer Multiplication . 39º ano do Simpósio sobre Teoria da Computação, San Diego, California, USA, 11 a 13 de Junho, 2007, pp. 55–67.O(n log n 2O(log* n))Algoritmo de Harvey e van der HoevenO(n log n)DivisãoDois números com n dígitosUm número com n dígitosSchoolbook divisãoO(n2)divisão de Newton–RaphsonO(M(n))Raiz quadradaUm número com n dígitosUm número com n dígitosmétodo de NewtonO(M(n))Exponenciação modularDois números com n dígitos e um expoente com k-bitUm número com n dígitosMultiplicação repetida e reduçãoO(M(n) 2k)Exponenciação por raiz quadradaO(M(n) k)Exponenciação com redução MontgomeryO(M(n) k)
Funções algébricas
OperaçõesEntradaSaídaAlgoritmoComplexidadeAvaliação polinomial Um polinômio de grau n com coeficientes do polinômio de tamanho fixo Um número de tamanho fixoAvaliaçã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 EuclidesO(n2)Algoritmo de Euclides Rápido http://planetmath.org/fasteuclideanalgorithmO(n (log n)2 log log n)
Funções especiais Muitos dos métodos desta seção são dadas em Borwein & Borwein.J. Borwein & P. Borwein. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. John Wiley 1987.
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.
AlgoritmoAplicabilidadeComplexidadeSérie de Taylor; repetida redução do argumento (e.g. exp(2x) = [exp(x)]2) e soma diretaexp, log, seno, cosseno, arctanO(M(n) n1/2)Série de Taylor; TFR-aceleração baseadaexp, log, seno, cosseno, arctanO(M(n) n1/3 (log n)2)Série de Taylor; divisão binária + estouro de bit métodoDavid and Gregory Chudnovsky. Approximations and complex multiplication according to Ramanujan. Ramanujan revisited, Academic Press, 1988, pp 375–472.exp, log, sin, cos, arctanO(M(n) (log n)2)Média aritmética-geométrica iteraçãoRichard 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.exp, log, seno, coss, arctanO(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çãoEntradaAlgoritmoComplexidadeFunção Gamman número de digitosAproximação da série da função gama incompletaO(M(n) n1/2 (log n)2)Número racional fixoSerie hipergeométricaO(M(n) (log n)2)m/24, m um inteiroMédia aritmética-geométrica iteraçãoO(M(n) log n)Função hipergeométrican pFqn número de digitos(Como descrito em Borwein & Borwein)O(M(n) n1/2 (log n)2)Número racional fixoSerie hipergeométricaO(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. ConstanteAlgoritmoComplexidaderazão de ouro, φMétodo NewtonO(M(n))Raiz quadrada de 2, Método de NewtonO(M(n))número de Euler, edivisão binária de série de Taylor para a função exponencialO(M(n) log n)Inversão do logaritmo natural de NewtonO(M(n) log n)Pi, πDivisão binária da série arctan em fórmula de MachinO(M(n) (log n)2)Algoritmo de Salamin–BrentO(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çãoEntradaSaídaAlgoritmoComplexidadeMDCTwo n número de dígitosUm número com, no máximo, n dígitosAlgoritmo EuclideanoO(n2)Algoritmo MDC binárioO(n2)Algoritmo binário MDC- esquerda/direita k- ario O(n2/ log n)Algoritmo de Stehlé–ZimmermannR. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Segunda edição, Springer 2005.O(M(n) log n)Algoritmo de descida euclidiana controlada por SchönhageO(M(n) log n)Símbolo de Jacobidois n número de dígitos0, −1, ou 1Algoritmo de descida euclidiana controlada por SchönhageO(M(n) log n) Algoritmo de Stehlé–ZimmermannO(M(n) log n)FatorialUm número de tamanho fixo mUm O(m log m) número de dígitosMultiplicação de baixo para cimaO(m2 log m)Divisão bináriaO(M(m log m) log m)Exponenciação dos fatores primos de mO(M(m log m) log log m),P. Borwein. "On the complexity of calculating factorials". Journal of Algorithms 6, 376-380 (1985)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çãoEntradaSaídaAlgoritmoComplexidadeMatriz de multiplicaçãoDuas matrizes n×nUma matrizn×nSchoolbook matriz de multiplicaçãoO(n3)Algoritmo de StrassenO(n2.807)Algoritmo de Coppersmith–WinogradO(n2.376)Algoritmos CW-like otimizadoO(n2.373)Matriz de multiplicaçãoUma matriz n×m &
uma matrizm×pUma matriz n×pSchoolbook matriz de multiplicaçãoO(nmp)Matriz de inversãoUma matriz n×nUma matrizn×nEliminação de Gauss–JordanO(n3)Algoritmo de StrassenO(n2.807)Algoritmo de Coppersmith–WinogradO(n2.376)Algoritmo CW-like otimizadoO(n2.373)DeterminanteUma matriz n×nUm númeroExpansão de LaplaceO(n!)Decomposição LUO(n3)Algoritmo de BareissO(n3)Matriz de multiplicação rápidaO(n2.373)Substituição regressivaMatriz triangularn soluçõesSubstituição regressivaO(n2)J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.
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.Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. . Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
Por causa da possibilidade de por blocos inverter uma matriz, onde uma inversão de uma 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 operações,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. . 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.T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009, §28.2.
Bibliografia
Categoria:Complexidade Categoria:Listas de matemática