little for examples dummies datasheet complexity big algorithm performance big-o

algorithm - for - big-o notation examples



¿Por qué el Tamiz de Eratóstenes es más eficiente que el simple algoritmo "tonto"? (7)

Debido a que con el método de tamiz, dejas de marcar múltiples de los primos en ejecución cuando el primo en ejecución llega a la raíz cuadrada de N.

Digamos que quieres encontrar todos los números primos menos de un millón.

Primero establece una matriz

for i = 2 to 1000000 primetest[i] = true

Entonces iteras

for j=2 to 1000 <--- 1000 is the square root of 10000000 if primetest[j] <--- if j is prime ---mark all multiples of j (except j itself) as "not a prime" for k = j^2 to 1000000 step j primetest[k] = false

No tienes que marcar j después de 1000, porque j * j será más de un millón. Y empiezas desde j * j (no tienes que marcar múltiplos de j menos que j ^ 2 porque ya están marcados como múltiplos de números primos encontrados anteriormente)

Entonces, al final has hecho el bucle 1000 veces y la parte if solo para los j que son primos.

La segunda razón es que con el tamiz, solo haces multiplicación, no división. Si lo haces inteligentemente, solo haces suma, ni siquiera multiplicación.

Y la división tiene mayor complejidad que la suma. La forma habitual de hacer división tiene O(n^2) complejidad, mientras que la adición tiene O(n) .

Si necesita generar números primos de 1 a N, la forma "simple" de hacerlo sería iterar a través de todos los números de 2 a N y verificar si los números se pueden dividir por cualquier número primo encontrado hasta ahora, que es menor que el raíz cuadrada del número en cuestión.

Como lo veo, el tamiz de Eratóstenes hace lo mismo, excepto al revés: cuando encuentra un N primordial, marca todos los números que son múltiplos de N.

Pero si marca X cuando encuentra N, o si comprueba si X es divisible por N, la complejidad fundamental, el big-O permanece igual. Todavía haces una operación de tiempo constante por un par de números primos. De hecho, el algoritmo tonto se interrumpe tan pronto como encuentra un cebado, pero el tamiz de Eratóstenes marca cada número varias veces, una vez por cada cebado se puede dividir. Eso es un mínimo de dos veces más operaciones para cada número, excepto los números primos.

¿Estoy malinterpretando algo aquí?

En el método ingenuo, realiza operaciones O(sqrt(num)) para cada número de num que verifique para primalidad. Ths es O(n*sqrt(n)) total.

En el método de tamiz, para cada número no marcado de 1 a n , realiza n / 2 operaciones al marcar múltiplos de 2 , n / 3 al marcar los de 3 , n / 5 al marcar los de 5 etc. Esto es n*(1/2 + 1/3 + 1/5 + 1/7 + ...) , que es O(n log log n) . Vea here para ese resultado.

Así que la complejidad asintótica no es la misma, como dijiste. Incluso un tamiz ingenuo vencerá el método ingenuo de generación principal bastante rápido. Las versiones optimizadas del tamiz pueden ser mucho más rápidas, pero el big-oh permanece sin cambios.

Los dos no son equivalentes como tú dices. Para cada número, verificará la divisibilidad con los mismos números primos 2, 3, 5, 7, ... en el algoritmo ingenuo de generación principal. A medida que avanzas, verificas la divisibilidad por la misma serie de números (y sigues verificando cada vez más a medida que te acercas a tu n ). Para el tamiz, sigues revisando cada vez menos a medida que te acercas a n . Primero verifica en incrementos de 2 , luego de 3 , luego 5 y así sucesivamente. Esto golpeará n y se detendrá mucho más rápido.

La primera diferencia es que la división es mucho más cara que la suma. Incluso si cada número está ''marcado'' varias veces, es trivial en comparación con la gran cantidad de divisiones necesarias para el algoritmo ''tonto''.

Un Tamiz "ingenuo" de Eratóstenes marcará números no primos varias veces. Pero, si tiene sus números en una lista vinculada y elimina números que son múltiplos (aún tendrá que recorrer el resto de la lista), el trabajo que queda por hacer después de encontrar un número primo es siempre más pequeño de lo que era antes de encontrar el número primo .

En el algoritmo de división de prueba, la mayor parte del trabajo que puede ser necesario para determinar si un número n es primo, es probar la divisibilidad de los números primos hasta aproximadamente sqrt(n) .

El peor de los casos se cumple cuando n es un primo o el producto de dos primos de casi el mismo tamaño (incluidos los cuadrados de primos). Si n tiene más de dos factores primos, o dos factores primos de tamaño muy diferente, al menos uno de ellos es mucho más pequeño que sqrt(n) , por lo que incluso el trabajo acumulado necesario para todos estos números (que forman la gran mayoría de todos) los números hasta N , para N suficientemente grande) son relativamente insignificantes, lo ignoraré y trabajaré con la ficción de que los números compuestos se determinan sin hacer ningún trabajo (los productos de dos números primos aproximadamente iguales son pocos en número, por lo que aunque individualmente cuestan tanto como una prima de tamaño similar, en conjunto es una cantidad de trabajo insignificante).

Entonces, ¿cuánto trabajo toman las pruebas de los números primos hasta N ?

Según el teorema del número primo, el número de primos <= n es (para n suficientemente grande), aproximadamente n/log n (es n/log n + lower order terms ). A la inversa, eso significa que k -th prime es (para k no demasiado pequeño) sobre k*log k (+ términos de orden inferior).

Por lo tanto, probar k -th prime requiere una división de prueba por pi(sqrt(p_k)) , aproximadamente 2*sqrt(k/log k) , números primos. Sumando que para k <= pi(N) ~ N/log N obtienen aproximadamente 4/3 4/3*N^(3/2)/(log N)^2 divisiones en total. Entonces, al ignorar los compuestos, encontramos que encontrar los primos hasta N por división de prueba (usando solo primos), es Omega(N^1.5 / (log N)^2) . Un análisis más detallado de los compuestos revela que es Theta(N^1.5 / (log N)^2) . Usar una rueda reduce los factores constantes, pero no cambia la complejidad.

En el tamiz, por otro lado, cada compuesto se tacha como un múltiplo de al menos un cebado. Dependiendo de si comienza a tachar en 2*p o en p*p , un compuesto se tacha tantas veces como tiene factores primos distintos o factores primos distintos <= sqrt(n) . Como cualquier número tiene a lo sumo un factor primo que supera a sqrt(n) , la diferencia no es tan grande, no tiene influencia en la complejidad, pero hay muchos números con solo dos factores primos (o tres con uno más grande que sqrt(n) ), por lo tanto, hace una diferencia notable en el tiempo de ejecución. De todos modos, un número n > 0 tiene solo unos pocos factores primos distintos, una estimación trivial muestra que el número de factores primos distintos está delimitado por lg n (logaritmo en base 2), por lo que un límite superior para el número de cruces fuera del tamiz lo hace es N*lg N

Al contar no con qué frecuencia se cruza cada compuesto, sino cuántos múltiplos de cada primo se cruzan, como ya hizo IVlad, uno encuentra fácilmente que el número de cruces es de hecho Theta(N*log log N) . Nuevamente, usar una rueda no cambia la complejidad, sino que reduce los factores constantes. Sin embargo, aquí tiene una influencia más grande que para la división de prueba, por lo que al menos se debe omitir el emparejamiento (además de reducir el trabajo, también reduce el tamaño de almacenamiento, por lo que mejora la ubicación de la memoria caché).

Por lo tanto, incluso ignorar que la división es más costosa que la suma y la multiplicación, vemos que la cantidad de operaciones que requiere el tamiz es mucho menor que la cantidad de operaciones requeridas por la división de prueba (si el límite no es demasiado pequeño).

Resumiendo:
La división de prueba realiza un trabajo inútil al dividir números primos, el tamiz realiza un trabajo inútil al cortar repetidamente los compuestos. Hay relativamente pocos números primos, pero muchos compuestos, por lo que uno podría sentirse tentado a pensar que la división de prueba desperdicia menos trabajo.
Pero: los compuestos tienen solo unos pocos factores primos distintos, mientras que hay muchos números primos debajo de sqrt(p) .