¿Cuál es la comparación en algoritmo de Sieve of Sundaram y Sieve of Eratosthenes con tiempo-complejidad?
- Cree una lista de N enteros positivos (1,2 …, N)
- Iterar sobre ellos usando el bucle anidado de i, j donde [matemática] 1 <= i <= j para todo i, j ε N [/ matemática]
- Marque [matemáticas] i + j + 2 * i * j [/ matemáticas] como no primo.
- Los números restantes se duplican y se incrementan en uno, es decir, [matemáticas] n = 2 * k + 1 [/ matemáticas]
- Salida: Esto dará todos los enteros primos impares, es decir, enteros primos, excepto 2
- Complejidad del tiempo:
- Tiempo necesario para iterar sobre N números y marcar no primos, [matemática] T (N) = N + T (N – 1) [/ matemática]
- La operación anterior reducirá la lista de tamaños a la mitad.
- Por lo tanto, el tiempo empleado en el siguiente paso (N – 1) será, [matemática] T (N – 1) = N / 2 + T (N – 2) [/ matemática]
- Cuando i, j es máximo, no quedan más no primos. Entonces el caso trivial sería [matemática] T (1) = k [/ matemática]
- Para duplicar el resto e incrementar en uno, el tiempo será constante para cada uno. Total de [matemática] O (N) [/ matemática] que es definitivamente menor que el tiempo necesario para eliminar los no primos.
- Por lo tanto, [matemáticas] T (N) = N + N / 2 + N / 3 +… + 1 = [/ matemáticas] [matemáticas] O (N log N) [/ matemáticas]
- Cree una lista de N enteros positivos a partir de 2 (2 …, N)
- Iterar sobre la lista en bucle anidado por i, j donde [matemática] 2 <= i <= j para todo i, j ε N [/ matemática]
- Para cada primo [matemático] i [/ matemático], marque [matemático] i * j [/ matemático] como no primo.
- Los números restantes se imprimen tal como están.
- Salida: todos los enteros primos incluyendo 2
- Complejidad del tiempo:
- Tiempo necesario para iterar sobre N no primo, [matemática] T (N) = N + T (N – 1) [/ matemática]
- En el siguiente paso, encontrar el número primo inmediato lleva algo de tiempo t y [matemáticas] T (N – 1) = t * N / 2 + t * T (N – 1) [/ matemáticas]
- El caso trivial, encontrar el último no primo es nuevamente [matemática] T (1) = k [/ matemática]
- Iterar sobre el descanso tomará tiempo constante para cada uno, es decir, la complejidad total sería [matemática] O (N) [/ matemática] que es menor que la búsqueda.
- Por lo tanto, [matemáticas] T (N) = N + N / 2 * (1 + 1/2 +… + 1 / N) + N / 3 * (1 + 1/2 +… + 1 / N) +… + 1 = O (N log (log N)) [/ math]
