Complejidad de tiempo de la suma

Wikipedia enumera la complejidad temporal de la suma como , donde es el número de bits. $n$ $n$

¿Es este un límite inferior teórico rígido? ¿O es solo la complejidad del algoritmo actual más rápido conocido? Quiero saber, porque la complejidad de la suma, subraya todas las demás operaciones aritméticas y todos los algoritmos que las utilizan.

¿Es teóricamente imposible obtener un algoritmo de suma que se ejecute en ? ¿O estamos obligados a la complejidad lineal para la suma. $o(n)$

algorithms algorithm-analysis arithmetic Tobi Alafin
fuente

Respuestas:

Si su algoritmo usa asintóticamente menos de tiempo, entonces no tiene tiempo suficiente para leer todos los dígitos de los números que está agregando. Debe imaginar que está manejando números muy grandes (almacenados, por ejemplo, en archivos de texto de 8 MB). Por supuesto, la suma se puede hacer muy rápidamente en comparación con el valor de los números; se ejecuta en tiempo , si es el valor de la suma. $n$ $\mathcal{O}(\log(N))$ $N$

Esto no significa que pueda acelerar un poco las cosas; si su procesador maneja 32 bits en cada operación, entonces usa tiempo, pero eso sigue siendo y no . $\frac{n}{32}$ $\mathcal{O}(n)$ $o(n)$

Lieuwe Vinkhuijzen
fuente

Está leyendo todos los datos teóricamente necesarios. Para la suma de dos números cualquiera y . El cálculo de se puede hacer en la operación , a través del desplazamiento. Anexar un . Considere eso. Si no encuentra una estimación más rápida para la suma, refine esa estimación hasta que sea correcta. En menos de operaciones?

a

$a$

b, a : a \geq b, a + b \leq 2 a

$b, a: a \ge b, a + b \le 2a$

2 a

$2a$

O (1)

$O(1)$

0

$0$

n

$n$

Tobi Alafin

Sí, es una necesidad teórica, porque: cada bit de la entrada se usa no trivialmente en la salida , donde no trivial quiero decir que no es la función de identidad. En su ejemplo , si puede calcularse en tiempo depende del modelo computacional: si agregar un es una operación de tiempo constante, entonces sí. Si tiene acceso a RAM, necesita tiempo para escribir la dirección del bit si ya conoce la duración de , u si tiene que leer todo para averiguarlo. En este ejemplo , muchos bits de salida son funciones triviales de los bits de entrada.

2 a

$2a$

2 a

$2a$

O (1)

$O(1)$

0

$0$

O (\log (n))

$O(\log(n))$

a

$a$

O (n)

$O(n)$

a

$a$

2 a

$2a$

Lieuwe Vinkhuijzen

Tengo un algoritmo que encuentra la longitud de en . Utiliza búsqueda binaria.

a

$a$

O (\log n)

$O(\log n)$

Tobi Alafin

@TobiAlafin Si su modelo admite direccionamiento RAM, entonces su búsqueda binaria se ejecuta en pasos , corrija. En Turing Machine, y en un archivo de texto no cargado en la memoria principal, esto toma tiempo. En cualquier caso, para responder a su pregunta, con o sin direccionamiento RAM para acelerar la búsqueda, su algoritmo tendrá que mirar todos los bits de la entrada para calcular . Suponga que no lo hizo, y en una entrada de bits, no inspecciona el bit. Entonces podría voltear esa parte, y daría la respuesta incorrecta.

O (\log n)

$O(\log n)$

O (n)

$O(n)$

a + b

$a+b$

42

$42$

6

$6$

Lieuwe Vinkhuijzen

Básicamente todas las operaciones son , por este motivo. La única excepción es si se trata de una estructura de datos ordenada de alguna manera: por ejemplo, no tiene que visitar un BST completo para verificar si contiene un cierto valor, pero esto es cierto solo debido a los invariantes que vienen con el BST.

Ω (n)

$\Omega(n)$

Bakuriu

Para que el análisis de complejidad tenga algún sentido formal, debe especificar un modelo computacional formal dentro del cual se ejecuta el algoritmo en el objeto, o, al menos, un modelo de costo , que especifica cuáles son las operaciones básicas y sus costos

En la mayoría de los contextos, se supone que las operaciones aritméticas toman tiempo . Esto suele ser razonable, ya que estamos interesados en la complejidad algorítmica independientemente de los números involucrados. Esto se llama el modelo de costo uniforme . $\Theta(1)$

Si los números pueden crecer sin límites, o si estamos interesados en analizar las propias operaciones, se considera que las operaciones aritméticas tienen un costo , proporcional al tamaño de la entrada. $\Theta(|x|)$

Ahora, ¿pueden las operaciones tener un costo menor? Posiblemente, sin embargo, tendrá que definir formalmente un modelo computacional en el que pueda suceder.

ordenación rápida
fuente

Como ejemplo adicional, un sumador de anticipación de acarreo lleva, bajo supuestos de simplificación apropiados, tiempo para calcular la suma de dos números de bits.

Θ (\log n)

$\Theta(\log n)$

n

$n$

Fabio Somenzi

La entrada a la suma es dos números arbitrarios . Como son arbitrarios, debe leer cada bit y, por lo tanto, el algoritmo es . $\Omega(n)$

Imagine que su algoritmo agrega con éxito 1010100110 y 0010010110 sin leer cada bit. Para que su algoritmo pueda agregar entradas arbitrarias , debería poder voltear aleatoriamente cualquiera de estos bits, y el algoritmo aún genera una adición correcta (pero diferente). Pero si su algoritmo no lee cada bit, ¿cómo podría decir que la entrada invertida fue diferente a la entrada original?

asesinato
fuente

Lo que estaba pensando si era un medio para aproximar la suma en menos de operaciones.

n

$n$

Tobi Alafin

Absolutamente. Solo tiene que definir qué significa "aproximado" en su algoritmo. Dependiendo de esa definición, agregar los dos bits más significativos podría ser una suma aproximada, que podría hacerse en o (n) tiempo. Cuando mencionas el algoritmo de "suma", creo que todos entendemos que la respuesta debe ser exacta.

murrdpirate