Las siguientes tablas muestran la complejidad computacional de varios algoritmos utilizados para obtener el resultado de operaciones matemáticas comunes.

En este artículo se hace referencia a la complejidad temporal de realizar cálculos sobre una máquina de Turing multicinta. Consúltese el artículo sobre la cota superior asintótica para obtener una explicación de la notación utilizada.

Nota: Debido a la variedad de algoritmos de multiplicación, a continuación representa la complejidad del algoritmo de multiplicación elegido.

Funciones aritméticas Esta tabla muestra la complejidad de las operaciones matemáticas con enteros.

OperaciónEntradaSalidaAlgoritmoComplejidadSumaDos números de dígitosUn número de dígitosSuma con acarreo manualRestaDos números de dígitosUn número de dígitosResta con acarreo manualMultiplicaciónDos números de dígitosUn número de dígitosMultiplicación larga manualAlgoritmo de KaratsubaMultiplicación de Toom-Cook de 3 víasMultiplicación de Toom-Cook de víasToom-Cook de nivel mixto (Knuth 4.3.3-T)Algoritmo de Schönhage-StrassenAlgoritmo de Harvey-HoevenDivisiónDos números de dígitosUn número de dígitosDivisión larga manualDivisión de divide y vencerás de Burnikel-ZieglerDivisión de Newton-RaphsonMétodo de NewtonUn número de dígitosUn número de dígitosMétodo de NewtonExponenciación modularDos números enteros de dígitos y un exponente de -bitUn número entero de dígitosMultiplicación y reducción repetidasExponenciación binariaExponenciación con la reducción de Montgomery

En modelos computacionales más robustos, específicamente en una máquina de punteros y, por consiguiente, también un máquina de acceso aleatorio de costo unitario, es posible multiplicar dos números de bits en tiempo O(n).

Funciones algebraicas Aquí se consideran operaciones sobre polinomios en los que denota su grado. Para los coeficientes se utiliza un modelo de costo unitario, ignorando el número de bits del número. En la práctica, esto significa que se asume que son enteros de máquina. En esta sección, indica el tiempo necesario para multiplicar dos polinomios de grado como máximo.

OperaciónEntradaSalidaAlgoritmoComplejidadEvaluación polinómicoUn polinomio de grado con coeficientes enterosUn númeroEvaluación directaAlgoritmo de HornerEvaluación multipunto de polinomiosUn polinomio de grado menor que con coeficientes enteros y números como puntos de evaluación númerosEvaluación directaEvaluación multipunto rápidaMáximo común divisor de polinomios (sobre o )Dos polinomios de grado con coeficientes enterosUn polinomio de grado como máximo Algoritmo de EuclidesAlgoritmo euclídeo rápido (Lehmer)

Funciones especiales Muchos de los métodos de esta sección se encuentran descritos en Borwein y Borwein.

Funciones elementales Las funciones elementales se construyen componiendo operaciones aritméticas, como es el caso de la función exponencial (), el logaritmo natural (), las funciones trigonométricas () y sus inversas. La complejidad de una función elemental es equivalente a la de su inversa, ya que todas las funciones elementales son analíticas y, por lo tanto, invertibles mediante el método de Newton. En particular, si o en el dominio complejo se pueden calcular con cierta complejidad, entonces esa complejidad es alcanzable para todas las demás funciones elementales.

A continuación, el tamaño se refiere al número de dígitos de precisión con los que se requiere evaluar la función.

AlgoritmoAplicabilidadComplejidadSeries de Taylor; reducción de argumentos repetidos (como ) y suma directaSeries de Taylor; basadas en la aceleración por la transformada rápida de FourierSeries de Taylor; descomposición binaria + algoritmo de ráfaga de bitsIteración de la media aritmético-geométrica

Se desconoce si representa la complejidad óptima para funciones elementales. El límite inferior más conocido es el límite trivial .

Funciones no elementales FunciónEntradaAlgoritmoComplejidadFunción gammaEntero Aproximación en serie de la función gamma incompletaNúmero racional fijoSerie hipergeométrica, para enteroIteración de la media aritmético-geométricaFunción hipergeométrica Número de dígitos(Según se describe en Borwein y Borwein)Número racional fijoSerie hipergeométrica

Constantes matemáticas Esta tabla muestra la complejidad de calcular aproximaciones a las constantes dadas con dígitos correctos.

ConstanteAlgoritmoComplejidadNúmero áureo, Método de NewtonRaíz cuadrada de dos, Método de NewtonNúmero e, Descomposición binaria de la serie de Taylor para la función exponencialInversión de Newton del logaritmo naturalNúmero π, Descomposición binaria de la serie arctan en las fórmulas de MachinAlgoritmo de Gauss-LegendreConstante de Euler, El método de Sweeney (aproximación en términos de la integral exponencial)

Teoría de números Los algoritmos para cálculos relacionados con la teoría de números se estudian mediante la teoría de números computacional.

OperaciónEntradaSalidaAlgoritmoComplejidadMáximo común divisor qqDos enteros de dígitosUn entero con como máximo dígitosAlgoritmo de EuclidesAlgoritmo binario del máximo común divisor (MCD)Algoritmo del MCD binario k-ario de izquierda/derechaAlgoritmo de Stehlé-ZimmermannAlgoritmo de descenso euclídeo controlado de SchönhageSímbolo de JacobiDos enteros de dígitos, o Algoritmo de descenso euclídeo controlado de SchönhageAlgoritmo de Stehlé-ZimmermannFactorialUn entero positivo menor que Un entero de dígitosMultiplicación ascendenteDescomposición binariaExponenciación de los factores primos de ,Test de primalidadUn número entero de dígitosVerdadero o falsoTest de primalidad AKS, asumiendo la conjetura de AgrawalTest de primalidad por curvas elípticas heurísticamenteTest de primalidad de Baillie-PSWTest de primalidad de Miller-RabinTest de Solovay-StrassenFactorización de enterosUn número entero de entrada de bitsUn conjunto de factoresCriba general del cuerpo de númerosEsta forma de tiempo subexponencial es válida para todo . Una forma más precisa de la complejidad se puede expresar como: Algoritmo de Shor, en computación cuántica

Álgebra matricial Las siguientes cifras de complejidad asumen que la aritmética con elementos individuales tiene una complejidad O(1), como ocurre con datos de coma flotante de precisión fija o con operaciones sobre un cuerpo finito.

OperaciónEntradaSalidaAlgoritmoComplejidadMultiplicación de matricesDos matrices de Una matriz de Multiplicación de matrices manualAlgoritmo de StrassenAlgoritmo de Coppersmith-Winograd (algoritmo galáctico)Algoritmos optimizados tipo CW (algoritmos galácticos)Una matriz de y una matriz de Una matriz de Multiplicación de matrices manualUna matriz de y una matriz de , para algún k ≥ 0</math>Una matriz de Algoritmos descritos por Le Gall, donde los límites superiores de se dan enInversión de una matrizUna matriz de Una matriz de Eliminación de Gauss-JordanAlgoritmo de StrassenAlgoritmo de Coppersmith-WinogradAlgoritmos rápidos para la multiplicación de matrices para , Sect. 11, pp. 413-414 .Descomposición en valores singularesUna matriz de Una matriz de , una matriz de y una matriz de Bidiagonalización y algoritmo QR ()Una matriz de , una matriz de y una matriz de Bidiagonalización y algoritmo QR ()Descomposición QRUna matriz de Una matriz de y una matriz de Algoritmos descritos por Knight, mediante multiplicación rápida de matrices ()DeterminanteUna matriz de Un númeroExpansión de LaplaceAlgoritmo sin divisiónDescomposición LUAlgoritmo de BareissMultiplicación rápida de matricesSustitución hacia atrásMatriz triangular solucionesSustitución hacia atrásPolinomio característicoUna matriz de Un polinomio de grado Algoritmo de Faddeev-LeVerrierAlgoritmo de Samuelson-Berkowitz (factor constante menor)Algoritmo de Preparata-Sarwate, in which the term is reducedMediante la multiplicación rápida de matrices

En 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy y Chris Umans demostraron que cualquiera de dos conjeturas diferentes implicaría que el exponente de la multiplicación de matrices es 2.

Transformaciones Los algoritmos para calcular transformadas de funciones (en particular, la transformada integral) se utilizan ampliamente en todas las áreas de las matemáticas, especialmente en análisis y procesado de señales.

OperaciónEntradaSalidaAlgoritmoComplejidadTransformada discreta de FourierSecuencia finita de datos de tamaño Conjunto de números complejosMétodo manualTransformada rápida de Fourier

Notas

Referencias

Categoría:Algoritmos de precisión arbitraria Categoría:Complejidad computacional Categoría:Anexos:Matemáticas Categoría:Problemas no resueltos de las ciencias de la computación