¿Cómo podemos suponer que las operaciones básicas en números toman tiempo constante?

74

Normalmente en los algoritmos no nos importa la comparación, la suma o la resta de números, suponemos que se ejecutan en el tiempo . Por ejemplo, suponemos esto cuando decimos que la clasificación basada en la comparación es , pero cuando los números son demasiado grandes para caber en los registros, normalmente los representamos como matrices, por lo que las operaciones básicas requieren cálculos adicionales por elemento.O ( n log n )O(1)O(nlogn)

¿Hay alguna prueba que muestre que la comparación de dos números (u otras funciones aritméticas primitivas) se puede hacer en ? Si no, ¿por qué decimos que la ordenación basada en la comparación es ?O ( n log n )O(1)O(nlogn)


Me encontré con este problema cuando contesté una pregunta SO y me di cuenta de que mi algoritmo no es porque tarde o temprano debería hacer frente a las grandes int, también no era algoritmo de tiempo seudo polinómica, que era .PO(n)P

Rafael
fuente
3
Si va a contar la complejidad de comparar números, también debe escribir sus límites de complejidad en términos del tamaño de bits de la entrada. Entonces, dados los números de bit, el tamaño de bit de la entrada es y la clasificación se puede hacer en tiempo . w n = N w O ( N w log N ) = O ( n log n )N wn=NwO(NwlogN)=O(nlogn)
Sasho Nikolov
2
Básicamente existen dos "reinos" o "regímenes" de estudio de la complejidad. generalmente se suponen operaciones operaciones de "ancho fijo", que es una aproximación razonable para la mayoría de los lenguajes de computadora que tienen representaciones de números de ancho fijo, incluso para coma flotante, por ejemplo, 2-4 bytes (ver, por ejemplo, estándares IEEE). entonces hay una "aritmética de precisión arbitraria" donde los números tienen un tamaño arbitrario y hay un estudio más cuidadoso / preciso de la complejidad de las operaciones. el primer contexto es más en análisis aplicado y el segundo es más en análisis teórico / abstracto. O(1)
vzn

Respuestas:

75

Para las personas como yo que estudian algoritmos para ganarse la vida, el modelo estándar de computación del siglo XXI es la RAM entera . El modelo está destinado a reflejar el comportamiento de las computadoras reales con mayor precisión que el modelo de máquina de Turing. Las computadoras del mundo real procesan enteros de múltiples bits en tiempo constante utilizando hardware paralelo; no enteros arbitrarios , pero (debido a que el tamaño de las palabras crece constantemente con el tiempo) tampoco son enteros de tamaño fijo .

El modelo depende de un único parámetro , llamado tamaño de palabra . Cada dirección de memoria contiene un único número entero de bit, o palabra . En este modelo, el tamaño de entrada es el número de palabras en la entrada, y el tiempo de ejecución de un algoritmo es el número de operaciones en palabras . Las operaciones aritméticas estándar (suma, resta, multiplicación, división de enteros, resto, comparación) y operaciones booleanas (bit a bit y, o, xor, shift, rotate) en palabras requieren tiempo por definición .w n O ( 1 )wwnO(1)

Formalmente, el tamaño de palabra NO es una constantew para fines de análisis de algoritmos en este modelo. Para que el modelo sea coherente con la intuición, necesitamos , ya que de lo contrario ni siquiera podemos almacenar el entero en una sola palabra. Sin embargo, para la mayoría de los algoritmos no numéricos, el tiempo de ejecución es realmente independiente de , porque esos algoritmos no se preocupan por la representación binaria subyacente de su entrada. Mergesort y heapsort se ejecutan en tiempo ; la mediana de 3 clasificaciones rápidas se ejecuta en tiempo en el peor de los casos. Una excepción notable es la ordenación de radix binaria, que se ejecuta en tiempo .wlog2nnwO(nlogn)O(n2)O(nw)

Establecer nos da el modelo tradicional de RAM de costo logarítmico. Pero algunos algoritmos de RAM entera están diseñados para tamaños de palabras más grandes, como el algoritmo de clasificación de enteros de tiempo lineal de Andersson et al. , que requiere .w=Θ(logn)w=Ω(log2+εn)

Para muchos algoritmos que surgen en la práctica, el tamaño de palabra simplemente no es un problema, y ​​podemos (y lo hacemos) recurrir al modelo de RAM de costo uniforme mucho más simple. La única dificultad seria proviene de la multiplicación anidada, que puede ser usado para construir muy grandes números enteros muy rápidamente. Si pudiéramos realizar operaciones aritméticas en enteros arbitrarios en tiempo constante, podríamos resolver cualquier problema en PSPACE en tiempo polinómico .w

Actualización: también debo mencionar que hay excepciones al "modelo estándar", como el algoritmo de multiplicación de enteros de Fürer , que utiliza máquinas de Turing multitapa (o equivalente, el "bit RAM"), y la mayoría de los algoritmos geométricos, que se analizan teóricamente modelo limpio pero idealizado de "RAM real" .

Sí, esta es una lata de gusanos.

JeffE
fuente
3
Sé que se supone que debo votar, pero no puedo evitar decirlo: esta es la mejor respuesta. El truco es que (1) las operaciones aritméticas son, por definición, tiempo constante y eso está bien porque, en teoría, puede elegir cualquier modelo, y (2) debe tener algunas razones para elegir un determinado modelo, y esta respuesta explica cuáles son.
rgrig
Estoy de acuerdo con rgig, (también se supone que debo votar), pero un pequeño problema es que el tamaño de entrada no está relacionado con los números de entrada, por ejemplo, si tengo una entrada mi número más grande es , y si elijo el modelo de cálculo como a mi me gusta, esto hace que el algoritmo de tiempo pseudo polinomial se convierta en , ¿estoy en lo cierto? nmP
1
Si su entrada consiste en números con más de bits, entonces para ajustar el modelo, debe dividirlos en fragmentos bit, como en la vida real. Por ejemplo, si su entrada consiste en enteros entre y , entonces su verdadero tamaño de entrada es . Por lo tanto, los tiempos de ejecución pseudopolinomiales como el tiempo siguen siendo exponenciales en el tamaño de entrada cuando es grande. w N 0 M N log w M = ( N lg M ) / ( lg w ) O ( N M ) MwwN0MNlogwM=(NlgM)/(lgw)O(NM)M
JeffE
¿Hay algún algoritmo analizado en el modelo de RAM real que no sea un algoritmo secreto de "RAM de tipo de pedido"? Nunca lo he pensado mucho, pero no puedo encontrar rápidamente un ejemplo que no lo sea.
Louis
1
@Louis: Sí, lotes: diagramas de Voronoi, caminos más cortos euclidianos, esquejes recursivos, árboles de partición simples, ... Pero el mejor ejemplo es la eliminación gaussiana, que se ejecuta en tiempo en el modelo RAM real (o la RAM entera de costo unitario, pero necesita tiempo en la RAM entera.O ( n 4 )O(n3)O(n4)
JeffE
24

Solo depende del contexto. Cuando se trata de la complejidad del nivel de bits de los algoritmos, no decimos que la suma de dos números de bits es , decimos que es . Del mismo modo para la multiplicación, etc.O ( 1 ) O ( n )nO(1)O(n)

Massimo Cafaro
fuente
De su artículo referenciado: "se puede medir de dos maneras diferentes: una en términos de los números enteros que se prueban o multiplican, y otra en términos del número de dígitos binarios (bits) en esos números enteros", pero esto no es cierto, nosotros siempre debe medir por tamaño de entrada.
1
@SaeedAmiri: solo depende de la codificación utilizada. En el artículo, por ejemplo, si la entrada es un entero especificado usando codificación unaria, la división de prueba requerirá solo . ¡Esto es polinomial en el tamaño de la entrada! ¿Esto significa que la factorización por división de prueba está en ? No, el algoritmo es pseudopolinomial . Usando la codificación binaria común, obtienes un algoritmo exponencial, nuevamente en el tamaño de la entrada. Como se indicó, esto sucede porque el número de bits en la entrada ha vuelto exponencialmente menor cambiando su codificación. nθ(n1/2)Pn
Massimo Cafaro
Por cierto, los algoritmos pseudo-polinomiales pueden ser realmente útiles, si el orden de magnitud de sus parámetros en casos reales es razonablemente bajo. El ejemplo más famoso es probablemente el algoritmo pseudopolinomial para resolver el problema de la mochila.
Massimo Cafaro
Primero, debo mencionar que su página wiki referenciada no es buena porque no tiene buenas referencias. Además, no sé por qué cree que estoy hablando de algoritmos de tiempo pseudo-polinomiales, puede deberse a que el tamaño de entrada normalmente es buttleneck en estos casos? pero no estoy hablando de ellos, estoy hablando principalmente de problemas que están en incluso asumiendo el tamaño de entrada, como ordenar, de todos modos porque no podemos hacer trampa y decir que el problema de NPC está en Creo que no deberíamos digamos que la ordenación es excepto que tenemos una prueba formal para ignorar la comparación. PPO(nlogn)
Estoy discutiendo algoritmos pseudo-polinomiales para enfocar su atención en el tamaño de la entrada, para mostrarle que puede ser engañosa. Aquí hay otro ejemplo. Se le da un número natural como entrada, digamos , y el algoritmo ejecuta un ciclo en el que realiza operaciones de tiempo para iteraciones. La complejidad de este algoritmo de bucle simple medido en función del tamaño de entrada es . ¡Como es el tamaño de entrada, el algoritmo es exponencial en el tamaño de entrada! Piensa sobre esto. Ahora puede entender lo que quiero decir con "Solo depende del contexto". nO(1)nO(n)=O(2lgn)lgn
Massimo Cafaro
16

Para responder la pregunta como se indica: los algoritmos simplemente lo hacen, con bastante frecuencia, utilizando el modelo RAM. Para ordenar, en muchos casos, las personas incluso analizan el modelo de comparación más simple , que discuto un poco más en la respuesta vinculada.

Para responder a la pregunta implícita sobre por qué lo hacen: diría que este modelo tiene un poder predictivo bastante bueno para ciertos tipos de algoritmos combinatorios, en los que los números son todos "pequeños" y, en máquinas reales, caben en registros.

Para responder al seguimiento implícito sobre algoritmos numéricos: No, el modelo RAM simple y antiguo no es el estándar aquí. Incluso la eliminación gaussiana puede requerir algunos cuidados. Por lo general, para los cálculos de rango, ingresará el Lema de Schwartz (por ejemplo, la Sección 5 aquí ). Otro ejemplo canónico es el análisis del algoritmo elipsoide, que requiere un poco de cuidado para analizar.

Y finalmente: la gente había pensado en la clasificación de cadenas antes , incluso recientemente.

Actualización: El problema con esta pregunta es que "nosotros" y "asumir" no se especifican con tanta precisión. Yo diría que las personas que trabajan en el modelo RAM no están haciendo algoritmos numéricos o teoría de la complejidad (donde determinar la complejidad de la división fue un resultado celebrado ).

Louis
fuente
Hmmmm, parece que es una respuesta interesante ...
¿Hay alguna razón por la que no responde completamente la pregunta?
Louis
7

No pude encontrar ningún estudio sobre esto, pero Kozen dice en la introducción de "El diseño y análisis de algoritmos" que el modelo "refleja la observación experimental con mayor precisión [que el modelo de costo logarítmico] para datos de moderado tamaño (ya que la multiplicación realmente toma una unidad de tiempo) ". También da una referencia a este documento como un ejemplo de cómo se puede abusar del modelo .O(1)O(1)

Esta no es una evaluación legítima (sobre todo porque es Python), pero aquí hay algunos números python -mtimeit "$a * $b"para ejecutar $aen y . (Paré en 66 porque ahí es cuando la sintaxis de Python deja de aceptar literales enteros y tendría que cambiar ligeramente mi código de evaluación, así que no lo hice.: P)10{1,2,...,66}$b = 2*$a

Cada número es la media de 10,000,000 bucles, donde toma el mejor tiempo de 3 carreras en cada bucle. Haría barras de error o algo así, pero eso sería más esfuerzo. : p En cualquier caso, me parece bastante constante, incluso hasta , algo sorprendente, ya que es 43, lo que refuerza mi sospecha de que tal vez esta evaluación es particularmente falsa y debería hacerlo en C.1050log10(sys.maxint)

Dougal
fuente
Puede que tenga experiencia laboral en este caso especial, tiene razón (pero no estoy seguro :), pero, por ejemplo, eche un vistazo a esto , parece que es pero no lo es, también es un problema práctico. ¿También viste algún documento que dijera que la clasificación es ? O(n)O(nlognlogm)
7

Tienes razón, en general no podemos asumir que son .O(1)

Hablando estrictamente, si queremos ordenar una matriz con N números usando comparaciones, y el número más grande es M, entonces, en el peor de los casos, cada comparación puede involucrar comparaciones en el nivel de bits. Y si nuestro algoritmo hace comparaciones , entonces su complejidad total será .O(logM)O(NlogN)O(NlogNlogM)

Sin embargo, notará la diferencia solo para valores muy grandes de , que no pueden almacenarse en un solo registro, como puede ver en el experimento de Dougal.M

Erel Segal-Halevi
fuente
O(logm) no , quiero decir que el mayor número en el conjunto es . O(logn)m
Sí, pero si hay N DIFERENTES números para ordenar, entonces el tamaño del más grande es bits. O(logN)
Erel Segal-Halevi
No, no está relacionado con el número de entrada, también si desea relacionarlo con el número de entrada, tengo número de entrada y el más grande esn n nnnnn
Tienes razón, corrigí mi respuesta.
Erel Segal-Halevi
4

Diría que normalmente asumimos operaciones aritméticas O (1) porque generalmente estamos haciendo cosas en el contexto de enteros de 32 bits o enteros de 64 bits o números de punto flotante IEEE 754. O (1) es probablemente una aproximación bastante buena para ese tipo de aritmética.

Pero en general, eso no es cierto. En general, necesita un algoritmo para realizar sumas, restas, multiplicaciones y divisiones. La lógica y la computabilidad de Boolos, Burgess and Jefferies se me viene a la mente como una forma de comprender las pruebas de eso, en términos de un par de sistemas formales diferentes, funciones recursivas y máquinas de ábaco, al menos, en mi cuarta edición.

Puede ver los términos de cálculo lambda para sustracción y división con Números de iglesia para obtener una explicación fácil de ver por qué esas dos operaciones no son O (1). Es un poco más difícil de ver para la suma, multiplicación y exponenciación, pero está ahí si consideras la forma de los números de la iglesia.

Bruce Ediger
fuente