¿Cuál es la complejidad temporal de este código en Python? ¿Es O(sqrt(n)) o O(n) debido a que sum() tiene O(n)?
Aquí está el código–
Devuelve el número de números primos menores que n.
def countPrimes2(n):
if n < 3:
return 0
primes = [True]*(n//2)
for i in range(3, int((n**0.5))+1, 2):
if primes[i//2]:
primes[i*i//2::i] = [False]*((n - i*i - 1) // (2*i) + 1)
return sum(primes)
davy.ai
Este código utiliza el algoritmo de la criba de Eratóstenes para encontrar todos los números primos menores que
n. Comienza verificando sines menor que 3, en cuyo caso devuelve 0 ya que no hay números primos menores que 2. Luego inicializa un array llamadoprimescon valoresTrueque representan cada número desde 2 hastan-1. Luego itera a través de los números impares en el rango de 3 hasta la raíz cuadrada den, verificando si el valor correspondiente en el arrayprimesesTrue. Si lo es, marca todos los múltiplos de ese número comoFalseen el arrayprimes. Finalmente, devuelve la suma de los valoresTrueen el arrayprimes, que representa la cantidad de números primos menores quen.Esta implementación tiene una complejidad temporal de O(n log log n), ya que el bucle externo itera hasta la raíz cuadrada de
ny el bucle interno se ejecuta log log n veces. La complejidad espacial es O(n) porque utiliza un array de booleanos para representar cada número desde 2 hastan-1.