Aula 02 – complexidade de algoritmos

COMPLEXIDADE DE ALGORITMOS

Complexidade de algoritmos

Complexidade de algoritmos

Voltar para página principal do blog

Todas as aulas desse curso

Aula 01           Aula 03

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:

Hostinger

Digital Ocean

One.com

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:

  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.

Ficamos por aqui, valeu, até mais. 🙂

Aula 01           Aula 03

Todas as aulas desse curso

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:

Hostinger

Digital Ocean

One.com

Meu github:

https://github.com/toticavalcanti

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

 

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>