8
def isprime(n):
   # 0 and 1 are not prime
   if n < 2:
    return False
   # 2 is prime
   if n == 2:
       return True    
   # even numbers are not prime
   if n % 2 == 0:
       return False
   # test if any odd number between 3 and the square root of n divides n
   # (it suffices to only go up to the square root)
   for i in range(3, int(n**0.5) + 1, 2):
       if n % i == 0:
           return False
   return True

Por que o tempo de execução desse algoritmo é √n (raiz quadrada de n)? Alguém poderia explicar como calcular?

1

1 Resposta 1

9

Complexidade de algoritmo se dá pela quantidade de passos necessários para executar algo baseando-se no número de itens que precisa ser avaliado, que foi convencionado chamar de n. A complexidade de algoritmo costuma ser medida e representada pela chamada notação Big O.

Então se não importando a quantidade de itens uma operação precisa sempre de 1 passo a complexidade é dita 1 ou constante (exemplo é o acesso a um item do array). Mostrando um laço:

for i in range(1, 1, 1):

Se precisa de n passos para avaliar n itens, então a complexidade é n ou linear (exemplo é listar os itens de um array). O laço ficaria assim:

for i in range(1, n, 1):

E se você consegue fazer isso quebrando em frações, geralmente de 2, a complexidade é logarítmica, portanto chamada log n porque usa uma função logarítmica para calcular quantos passos precisam, ou seja, se tiver cerca de 1000 itens levará 10 passos (o exemplo são operações em estruturas de árvores binárias) Laço:

for i in range(1, log(n, 2), 1):

Deu pra perceber que sempre tem uma fórmula das mais simples até as mais complexas para calcular isso. E a fórmula pode ser muito complexa.

No seu caso a fórmula está dada no código. A quantidade de itens que serão avaliados é N elevado à 0.5, então é simples achar a complexidade (veja próximo parágrafo que tem uma pegadinha). O laço vai executar a quantidade de vezes do resultado desta fórmula, igual aos exemplos citados acima. Então:

for i in range(3, int(n ** 0.5) + 1, 2):

Coloquei no GitHub para referência futura.

Mas note que tem dois detalhes extras nesse cálculo. Ele está pegando um item a mais. Então a fórmula toda tem que ser considera se deseja precisão no número. Na maioria dos casos fará pouca diferente real, mas matemática ignorar o + 1 é um erro. Outro problema mais grave é que ele não está pulando de 1 em 1, está pulando de 2 em 2, então a complexidade do algoritmo é N elevado à meio, mais 1 e tudo isso dividido por 2 ((N ** 0.5 + 1) / 2). Por sinal esta fórmula é bem próxima da logarítmica com base 2. E perceba que em alguns casos de N muito baixo nem executará nada.

Note que este é o pior caso, pode ter menos passos em muitos casos.

Talvez esteja confuso com o uso do range() que tem um valor inicial, um valor até onde ele deve ir (o final) e de quanto em quanto deve pular.

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .