Aula 02 – complexidade de algoritmos

More videos
Views
   

COMPLEXIDADE DE ALGORITMOS

Complexidade de algoritmos

Complexidade de algoritmos

Quero aproveitar para deixar essa lista para vocês programadores e programadoras 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:

  1. GeeksforGeeks Practice
  2.  LeetCode
  3. Kaggle 
  4. HackerRank
  5. CodeChef
  6. Brilliant
  7. HackerEarth
  8. CodeForces
  9. Codewars
  10. Topcoder
  11. InterviewBit
  12. Project Euler
  13. SPOJ
  14. CodingBat
  15. LintCode
  16. Codingame
  17. CodeFights
  18. Codility
  19. CoderByte
  20. UVA Online Judge
  21. Kattis
  22. CheckiO
  23. Rosalind 
  24. PythonChallenge
  25. SQL-EX.RU
  26. Urionlinejudge

É 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))

URI Online Judge | 1221

Primo Rápido

Por Neilor Tonin, URI  Brasil

Timelimit: 1

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 linhas, cada uma contendo um valor inteiro X (1 < X < 231) 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.

Curta a página do Código Fluente no Facebook
https://www.facebook.com/Codigofluente-338485370069035/

Vou deixar meu link de referidos na digitalocean pra vocês.

Quem se cadastrar por esse link, ganha $100.00 dólares de crédito na digitalocean:

Digital Ocean

Esse outro link é da one.com:

One.com

Obrigado, até a próxima e bons estudos. 😉

 

Increva-se

Inscreva-se agora e receba um e-mail assim que eu publicar novo conteúdo.

Concordo em me inscrever no blog Código Fluente

Você poderá cancelar sua inscrição a qualquer momento.

(Visited 42 times, 1 visits today)
About The Author
-

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>