¿Cómo es que la multiplicación por suma repetida (por ejemplo, sumar el número 41, 42 veces) tiene una complejidad exponencial de O (2 ^ n)?

Answer 1

Si el libro dice eso, entonces puede ser la complejidad de la suma paralela siendo n la base de registro 2 de los números (número de dígitos en binario. Para números decimales es el mismo número de dígitos en decimal o [matemáticas] log_ {10} (N) [/ math]) para multiplicar o, en otras palabras, n son los bits necesarios para codificar los números que se multiplicarán (o el número de dígitos decimales necesarios).

En C = A * B

[matemáticas] \, \, \, \, \, \, \, \, n = max (ceil (log_2 (A)), ceil (log_2 (B)), ceil (log_2 (C))) [/ math ]

por ejemplo son 11 bits

[matemáticas] \, \, \, \, \, \, \, \, 2 ^ {11} = 2048 = int (log_2 (1722) +. 5) [/ matemáticas]

Llamemos 42 veces y agregue 41, el “algoritmo de jardín de infantes” o KA, y cada suma se realiza en un solo paso (complejidad de suma paralela = O (1)), por lo que N suma complejidad O (1) O (N) = O ( N) que es igual a [matemáticas] O (2 ^ n) [/ matemáticas] Entonces:

[matemáticas] \, \, \, \, \, \, \, \, KA \ en O (N) = O (2 ^ n) = O (10 ^ {n}) [/ matemáticas]

[math] \, \, \, \, \, \, \, \, being \, \, n = log_2 (N) \, \, \, \, bits necesarios para codificar el resultado [/ math]

Si la suma es la suma KS del jardín de infantes (adición del libro escolar), entonces la complejidad es

[matemáticas] KS \ en O (N) = O (2 ^ n) [/ matemáticas]

[matemáticas] KA_s \ en O (N ^ 2) = O (2 ^ {2n}) [/ matemáticas]

Otros algoritmos pueden tener diferentes valores de complejidad.

Answer 2

Está tomando n como número dado (como 41), pero n aquí es el número de bits en el número. Por ejemplo, si tomamos 41 * 42, entonces n aquí es 5, porque estamos multiplicando dos números de 6 bits.
Ahora tenemos que agregar un número de 6 bits (41) varias veces, y que varias veces aquí es 42, que es aproximadamente [matemática] 2 ^ 6 [/ matemática] (Si un número puede representarse en n bits, entonces está entre los números [matemática] 2 ^ {n-1} [/ matemática] y [matemática] 2 ^ {n} [/ matemática]).
Entonces, en general, para dos números de n bits, estamos sumando [math] \ theta (2 ^ n) [/ math] veces.

Answer 3

De hecho, tiene una complejidad de tiempo exponencial con respecto al número de bits utilizados para representar los números (no con respecto a los números mismos). El valor máximo que puede representar un número con n bits es 2 ^ ny este es el número máximo de adiciones que tendría que realizar (en el peor de los casos). El único error que puedo detectar es que usted escribió “… estaríamos haciendo Θ (2n) adiciones …” que no es correcto y debería ser exponencial en su lugar. Pero supongo que esto fue solo un error tipográfico …

Como nota al margen, es bastante fácil realizar dicha multiplicación en pasos O (n ^ 2) utilizando el método del libro escolar para la multiplicación, solo se aplica a números binarios en lugar de números de base 10. Además, hay muchos métodos interesantes que logran un rendimiento aún mejor (con respecto a la complejidad computacional y no necesariamente para aplicaciones prácticas).

Answer 4

Considere multiplicar por 1024 = 2 ^ 10.
Este número requiere n = 10 bits para representar, pero realizar 1024 adiciones requerirá 2 ^ n adiciones. También tenga en cuenta que su estimación de complejidad O (2 ^ n) solo es correcta si cada suma se realiza en tiempo O (1), mientras que para un número de n bits, pasará tiempo O (n).