Aula 02 – complexidade de algoritmos

toticavalcanti

COMPLEXIDADE DE ALGORITMOS

Complexidade de algoritmos

Voltar para página principal do blog

Se gostarem do conteúdo dêem um joinha 👍 na página do Código Fluente no
Facebook

Esse é o link do código fluente no Pinterest

Meus links de afiliados:

Meu github:
https://github.com/toticavalcanti

Lista de desafios de códigos (Coding Challenges)

Quero aproveitar para deixar essa lista para vocês programadoras e programadores que querem aprimorar suas habilidades com algoritmos e lógica de programação.

Trata-se de uma lista de sites de desafios de códigos, isto é, Competitive Programming Sites, ou ainda, Coding Challenges:

É muito legal e divertido 😉

Pode ser uma opção interessante colocar no seu currículo sua página nesses sites, lá normalmente tem a sua classificação no hancking, os problemas que conseguiu resolver, entre outras informações.

Dessa forma, contratantes interessados no seu trabalho como programador, podem constatar sua capacidade e habilidade, seu nível de nerd, como se fosse um “nerdômetro”.

Agora, voltando a falar de complexidade de algoritmos, vamos a um exemplo prático.

Vamos ver agora como podemos melhorar a eficiência de um código, esse desafio é do Uri Online Judge:

A solução deve ser O(sqrt (n))

Mariazinha sabe que um Número Primo é aquele que pode ser dividido somente por 1 (um) e por ele mesmo. Por exemplo, o número 7 é primo, pois pode ser dividido apenas pelo número 1 e pelo número 7 sem que haja resto. Então ela pediu para você fazer um programa que aceite diversos valores e diga se cada um destes valores é primo ou não. Acontece que a paciência não é uma das virtudes de Mariazinha, portanto ela quer que a execução de todos os casos de teste que ela selecionar (instâncias) aconteçam no tempo máximo de um segundo, pois ela odeia esperar.

Entrada

A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 200), correspondente ao número de casos de teste. Seguem N linhas, cada uma contendo um valor inteiro X (1 < X < 2³¹) que pode ser ou não, um número primo.

Saída

Para cada caso de teste imprima a mensagem “Prime” (Primo) ou “Not Prime” (Não Primo), de acordo com o exemplo abaixo.

Exemplo de Entrada

3
123321
123
103

Exemplo de Saída

Not Prime
Not Prime
Prime

Veja duas soluções, a verde é a mais eficiente.


import time
from math import sqrt
T = int(input())

def isPrime_fast(num):
    for i in range(2, int(sqrt(num)) + 1):
        if num % i is 0:
            return False
    return True


def isPrime_slow(num):
    for i in range(2, num):
        if num % i is 0:
            return False
    return True


for n in range(T):
    num = int(input())
    t0= time.clock()
    print("Prime") if num >= 2 and isPrime(num) else print("Not Prime")
    t1 = time.clock() - t0
    print("Time elapsed: ", t1 - t0)

No código acima, a função em verde é muito mais rápida do que a em vermelho, veja o vídeo do post para ver os resultados.