¿Cuál es la complejidad de Big-O para algoritmos generalizados de operaciones aritméticas básicas como multiplicación, raíz cuadrada, logaritmo, escalar y producto de matriz?Gran O complejidad de las operaciones aritméticas básicas
¿Existen algoritmos exóticos que son más eficientes, en términos de complejidad de Big-O, pero no están muy extendidos en soluciones prácticas (por ejemplo, no implementadas en bibliotecas de software populares)?
Ver http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations producto
Matriz de matrices cuadradas:
También hay un O (N 2,38) Coppersmith–Winograd algorithm pero no creo que es ampliamente extendida debido a la constante oculta enormes.
Big-int multiplicación:
También hay un n log n & middot; 2 Algoritmo O (log * n) publicado en 2008 pero que era demasiado nuevo para ser generalizado.
Por lo general, el método ingenuo es suficiente para una entrada de tamaño normal.
Es interesante, qué tan rápido es O (N 2.38) que O (N³). – psihodelia
Desafortunadamente, la respuesta a eso es "depende". Como el artículo de wikipedia menciona, el algoritmo no se usa ampliamente porque solo resulta en una reducción en el tiempo de ejecución para entradas enormemente poco prácticas. –
En la práctica, el algoritmo O (N^2.38) no es más rápido en absoluto, porque hay más en la velocidad que la complejidad algorítmica. – Pillsy
Las operaciones no tienen complejidad, los algoritmos sí. Por ejemplo, hay varios algoritmos de raíz cuadrada, y tendrán diferente complejidad.
La multiplicación es un algoritmo entre dos matrices de bits. Con complejidad O (n²), si no estoy equivocado. – Tronic
@Skilldrick: OP está hablando de los algoritmos más comúnmente utilizados, por lo que en cierto sentido esta respuesta es irrelevante. –
@Moron: Creo que la pregunta ha sido ligeramente editada desde que contesté. – Skilldrick
Considerará las operaciones más simples como O (1) porque su tamaño de entrada suele ser fijo (es decir, 32 o 64 bits).
En condiciones normales, su plataforma realizará exactamente la misma operación para multiplicación, raíz cuadrada, logaritmo, etc. independientemente del "tamaño" de su entrada (es decir, int a = 0; int b = Int32.MaxValue son ambos enteros de 32 bits).
Se vuelve interesante una vez que comienzas a mirar matrices o representa números de precisión arbitraria, pero alguien ya vinculó el resumen de wikipedia, así que no entraré en eso.
Simplemente no use Schönhage–Strassen para multiplicar números pequeños "normales". Me hará llorar. El hecho de que un algoritmo es O (n ) no significa que sea malo - sobre todo cuando n es casi siempre 2 o 2 .
Ese es un muy buen punto en las operaciones en las entradas de 32 bits. – Skilldrick
En la práctica, tiene razón sobre las operaciones simples. Sin embargo, como teórico, quiero decir que todavía se puede hablar de la complejidad en términos del número de bits en el número. El mismo algoritmo está bien para 32b, pero se vuelve lento para 64b, o cuando finalmente llegamos a 1024b o algo ... De nuevo, en realidad tienes razón, pero sigue siendo una pregunta interesante. –
* asiente *, es absolutamente una pregunta interesante tan pronto como salga del mundo seguro de las entradas de longitud fija. –
La raíz cuadrada y el logaritmo se pueden implementar de varias maneras, lo que afecta en gran medida la complejidad (a juzgar por la precisión requerida).
Si se implementan con tablas de búsqueda (y algún tipo de interpolación), el requisito de memoria realmente explota ya que se requiere más precisión pero la complejidad es buscar el valor en la matriz y posiblemente aplicar la interpolación.
Más popularmente parecen ser implementados por sus definiciones de serie. Repita o repita una afirmación para varias rondas hasta que alcance la precisión requerida. Aquí el número de rondas puede ser muy alto ya que se necesita más precisión, y también los cálculos se ven afectados por la mayor precisión.
+1 Interesante. ¿Eso significa que N se convierte en la precisión? – Skilldrick
@skilldrick definitivamente puede hacerlo de esa manera. Hay algoritmos que se miden en el tamaño de su SALIDA en lugar de su entrada. Tienen un nombre, pero es viernes, así que no puedo molestarme en recordarlo B-) –
Hay un algoritmo de tipo Fourier que hace la multiplicación de enteros, así (Schonhage-Strassen)
pensé que había una versión del algoritmo de Strassen que hace un poco mejor de lo normal para la multiplicación de enteros, pero ahora que lo pienso, ese termina siendo el mismo que el simple ...
Sumar y restar son más o menos, solo sumas y restas. Sin embargo, la división y la raíz cuadrada son probablemente interesantes ...
TAMBIÉN: Tenga en cuenta que hasta ahora todo el mundo ha hablado sobre la aritmética INTEGER. Una vez que llegue a flotantes/dobles, todas las apuestas estarán apagadas. Entonces te metes en el mundo de numerical analysis, y eso es todo un campo propio ...
Echa un vistazo a BigInteger, en enteros de longitud arbitraria. Todo ahora tiene un costo, en términos del tamaño de la entrada, que es el número de bits (típicamente O(log K) bits para un número K). Utilizaré N para la cantidad de bits a continuación.
Por ejemplo, la suma y la resta ahora es O(N). La multiplicación es O(N^2) (ingenua) o O(n (log n)^(2+epsilon) ) con FFT.
Otros algoritmos incluyen la función de "potencia", que requiere una multiplicación de O(N). (¡excepto que ahora cada multiplicación tiene un costo!)
Y hay complejidades adicionales para BigDecimales, que es el equivalente decimal de longitud arbitraria, y más allá de algunas de las operaciones más básicas, algunas de las cosas también son más interesantes (especialmente si quieres saber cuánta precisión quieres). Puede echar un vistazo a la implementación de Java.
Una implementación ingenua de la función de potencia requiere O (n) multiplicaciones, pero las implementaciones inteligentes son O (log n): http://en.wikipedia.org/wiki/Exponentiation_by_squaring – Juliet
Como mencioné, 'N' es la cantidad de bits. Sin embargo, el encendido es 'O (log K)' para un cierto número de 'K'. – Larry
Las divisiones y raíces cuadradas para una gran cantidad de bits no son mucho más complejas que la multiplicación. Para ambas operaciones, la iteración simple de Newton puede organizarse de tal forma que la iteración de Newton solo tenga multiplicaciones. Dado que el número de dígitos correctos se duplica en cada paso, podemos duplicar la precisión del cálculo en cada paso.
+1 Interesante pregunta. Para aclarar, presumiblemente él quiere decir complejidad con un número creciente de bits. – Tronic
@Tronic: ¿usted piensa bits? El producto Matrix probablemente sería en términos de tamaño de la matriz, presumiblemente ... – Skilldrick
¿Wiki de la comunidad? –