Aula 01 – complexidade de algoritmos

More videos
Views
   

COMPLEXIDADE DE ALGORITMOS

Complexidade de algoritmos

Complexidade de algoritmos

Vivemos uma época em que os dados são gerados em enxurradas, hoje em dia quase todo dispositivo gera dados:

  • Celulares
  • Geladeiras
  • GPS
  • Sensores
  • Cameras
  • Luminárias urbanas
  • Medidores de poluição
  • etc

Cada vez mais, empresas buscam encontrar indicativos, indícios de coisas, preferencia dos clientes, entre outras coisas, em seus dados.

É preciso usar algoritmos muito otimizados para um processamento tão massivo como é exigido hoje em dia.

Então, é muito importante para um programador, saber um pouco sobre complexidade de algoritmos e como é medido o desempenho de um código.

Notação assintótica

  • O-grande, ou Big O, é a notação assintótica mais utilizada para determinar a eficiência de um algoritmo
  • O Big O descreve o comportamento geral (também chamado de assintótico, pois é o comportamento no limite conforme os dados crescem) do algoritmo em termos do crescimento do número de operações conforme cresce o número de elementos processados (a quantidade de itens é descrita, genericamente, por n)
  • É usada para limites assintóticos superiores

O GRÁFICO A SEGUIR ILUSTRA AS CURVAS DE CRESCIMENTO MAIS COMUNS

CURVAS DE CRESCIMENTO MAIS COMUNS

CURVAS DE CRESCIMENTO MAIS COMUNS

 

DESEMPENHO

  • O (n!)(fatorial) o número de instruções executadas cresce muito rapidamente para um pequeno crescimento do número de itens processados. É o caso da implementação ingênuo do problema do caixeiro viajante ou de um algoritmo que gere todas as possíveis permutações de uma lista.
  • O (2^n)(exponencial) também é bem ruim, pois o número de instruções também cresce muito rapidamente (exponencialmente), ainda que numa taxa menor do que o anterior. É o caso de algoritmos que fazem busca em árvores binárias não ordenadas
  • O (n^2) (quadrático) é factível, mas tende a se tornar muito ruim quando a quantidade de dados é suficientemente grande. É o caso de algorítmos que têm dois laços (for) encadeados, como, por exemplo, o processamento de itens em uma matriz bidimensional.
  • O (n log n) (sub-quadrático ou super-linear) é melhor do que o quadrático. É o caso do algoritmo de ordenação QuickSort, tem complexidade C(n) = O(n²) no pior caso e C(n) = O(n log n) no melhor e médio caso.
  • O (n) (linear) é aquele cujo crescimento no número de operações é diretamente proporcional ao crescimento do número de itens. É o caso de algoritmos de busca em uma matriz unidimensional não ordenada.
  • O (log n) (logaritmo) é aquele cujo crescimento do número de operações é menor do que o do número de itens. É o caso de algoritmos de busca em árvores binárias ordenadas (Binary Search Trees).
  • O (1) (constante) é aquele em que não há crescimento do número de operações, pois ele independente do volume de dados de entrada (n). É o caso do acesso direto a um elemento de uma matriz.

COMPLEXIDADE DE ALGORITMOS O(1):


arr = [4, 5, 3, 9, 7]
arr[4]
7

Outro exemplo:


arr = {"odd":1, "even":2}
arr["odd"]
1

COMPLEXIDADE DE ALGORITMOS O(log n):

Na busca binária é necessário ordenação. Então considere a lista ordenada a seguir.

lst = [1, 3, 45, 59, 60, 83, 90]

Suponha que o elemento desejado é o número 83.

A busca tenta encontrar no meio da lista ordenada o 83, mas encontra o 59.

lst = [1, 3, 45, 59, 60, 83, 90]

A busca verifica se o 83 é maior ou menor do que o 59 e constata que é maior.

A busca verifica se o 83 é maior ou menor do que o 59 e constata que é maior.

O espaço de busca agora foi reduzido pela metade

lst = [1, 3, 45, 59, 60, 83, 90]

A busca agora se restringe a lista da posição 4 à 6, ou seja, do 60 ao 90.

A busca tenta encontrar no meio da lista ordenada o 83, e dessa vez encontra o 83.

lst = [1, 3, 45, 59, 60, 83, 90]

COMPLEXIDADE DE ALGORITMOS O(n):


arr = [4, 5, 3, 9, 7]
for item in arr:
    print(item)

Outro exemplo:


def summ(n):
    if n <=0:
        return 0
    return n + summ(n - 1)

COMPLEXIDADE DE ALGORITMOS O(n^2)


arr = [1,3,5,7]
for i in arr:
    for j in arr:
        print(i+j)

COMPLEXIDADE DE ALGORITMOS O(√n)


def func_a(n):
    s = i = 1
    while s <= n:
        i += 1
        s += i
        print(" Olá ")

s – 1, 3, 6, 10, 15, 21, … n

i – 1, 2, 3,  4,   5,    6,  …

O loop vai parar depois k iterações.

Ou seja, depois de k iterações o valor de s será maior ou igual a n.

O loop vai parar depois k iterações.

Qual o valor de s depois de k iterações?

Ou seja, depois de k iterações o valor de s será maior ou igual a n

O loop vai parar depois que:

k(k + 1) / 2 > n

O loop vai parar depois que:

k(k + 1) / 2 > n

k^2 + k / 2 > n

k = O(√n)

Outro exemplo de complexidade O(√n)


a(){
    i = 1
    for(i = 1; i^2 <= n; i++)
        printf("Toti")
}

for(i = 1; i <= √n; i++)

COMPLEXIDADE DE ALGORITMOS O(n!)


def factorial(n):
    if (n == 1):
        return 1
    else:
        return n * factorial(n-1)

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 15 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>