Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Aprendendo sobre Complexidade de Algoritmos com...

Ana Paula Mendes
November 02, 2023
81

Aprendendo sobre Complexidade de Algoritmos com o Timsort

Esta palestra visa uma introdução sobre Análise de Complexidade de Algoritmos utilizando o Algoritmo Timsort como exemplo.

- Introdução
- Análise de Complexidade
- Algoritmo Insertion Sort
- Algoritmo Merge Sort
- Algoritmo Timsort

Ana Paula Mendes

November 02, 2023
Tweet

Transcript

  1. Ana Paula Mendes • Cientista da Computação - UFPI •

    Engenheira de Software Sênior no Jusbrasil • Mestranda em Computação Inteligente na UFPI • PyLady, Diabética Tipo 1 e Artista de Pole
  2. Esta palestra visa uma introdução sobre Análise de Complexidade de

    Algoritmos utilizando o Algoritmo Timsort como exemplo. • Introdução • Análise de Complexidade • Algoritmo Insertion Sort • Algoritmo Merge Sort • Algoritmo Timsort Sumário
  3. Timsort é um algoritmo de ordenação híbrido, ou seja, combina

    outras técnicas, neste caso o Insertion Sort e o Merge Sort. Foi inventado pelo Tim Peters em 2002 para o Python e é usado desde a versão 2.3. Também é utilizado no Java para arrays. Tim percebeu que os dados no mundo real contêm blocos já ordenados, seja na ordem crescente ou decrescente e que os outros algoritmos de ordenação em casos ideais não levam isso em consideração. Sua abordagem se baseou em identificar esses blocos e ordená-los usando Insertion e juntá-los com o Merge. Ele utiliza de blocos já ordenados para otimização de performance. Introdução
  4. Tim Peters • Autor do Zen do Python (import this)

    • Criador do Timsort • Contribuiu com os módulos doctest e timeit do Python • Contribuiu com o capítulo de algoritmos do livro Python Cookbook • De 2001 a 2014 foi membro ativo da diretoria da Python Software Foundation • Em 2017 recebeu o prêmio da Python Software Foundation, Distinguished Service Awards
  5. A Análise de Complexidade de Algoritmos é um campo que

    se concentra em entender e avaliar o desempenho dos algoritmos, envolvendo a análise teórica do tempo de execução e de espaço utilizado de um algoritmo em relação ao tamanho da entrada. O objetivo é determinar como o desempenho de um algoritmo é afetado pelo aumento do tamanho do problema. Análise de Complexidade de Algoritmos
  6. A notação Big O é usada para descrever o limite

    superior do crescimento assintótico de um algoritmo. Ela representa a ordem de complexidade do algoritmo em termos do tamanho da entrada. Notação Big O Notação Big O Alternativa • O(1) = O(yeah) • O(log n) = O(nice) • O(n) = O(ok) • O(n²) = O(no) • O(2ⁿ) = O(sh*t) • O(n!) = O(mg!)
  7. Notação Assintótica Melhor Caso • Ω (Omega) • Limite inferior

    Pior Caso • Notação Big O • Limite superior Caso Médio • Θ (Theta) • Limite superior ajustado ou limite assintoticamente restrito Imagens do livro Introduction to Algorithms do Cormen
  8. Operações Elementares São as operações mais básicas executadas em um

    algoritmo que serão contadas para determinar a complexidade do algoritmo. Podem variar dependendo do contexto, sendo elas: atribuições, comparações, operações matemáticas básicas e acesso a um elemento em uma estrutura de dados. def soma_vetor(vetor): soma = 0 # (1) operação de atribuição for num in vetor: # (n) operações de iteração (onde n é o tamanho do vetor) soma = soma + num # (n) operações de adição e atribuição return soma # (1) operação de retorno Total de Operações Elementares => 1 + n + n + 1 = 2n + 2 Análise de Complexidade => O(n)
  9. Considerações a serem feitas • Podemos computar a quantidade de

    operações no melhor e pior caso em outros exemplos de algoritmos; • Analisando laços de repetição mais complexos com condições de parada específicas, podemos utilizar somatórios da matemática; • Existem análises mais complexas chamadas Recorrências para algoritmos recursivos que necessitam de métodos específicos (Método da Substituição, Método da Árvore de Recorrência, Método Mestre, etc); Estes não serão abordados na palestra pelo limite de tempo e foco em abordar de forma resumida o conteúdo, mas são assuntos que valem a pena serem aprofundados para melhor entendimento deste tema.
  10. • Também conhecido como algoritmo de ordenação por inserção; •

    Similar ao funcionamento de como pessoas organizam o baralho num jogo de cartas; • Eficiente para problemas com pequenas entradas; • In-place: Não utiliza memória auxiliar; • Estável: Não muda a ordem de elementos iguais; • É o melhor método quando a entrada está parcialmente ordenada; • O custo é alto quando há movimentação de elementos. Algoritmo Insertion Sort
  11. Passo Inicial: O primeiro elemento da lista é considerado uma

    sublista ordenada de um elemento. Iteração: Para cada elemento subsequente na lista, o algoritmo encontra o local adequado na sublista ordenada movendo os elementos maiores para a direita e inserindo o elemento na posição correta. Repetição: O processo é repetido até que todos os elementos tenham sido inseridos na sublista ordenada, resultando na lista ordenada. Insertion Sort Método de Solução
  12. Insertion Sort Análise de Complexidade Melhor Caso • A lista

    já está ordenada, só faz comparações e não tem movimentações no array; • O(n) Pior Caso • A lista está inversamente ordenada e faz o máximo de comparações e de movimentações no array; • O(n²)
  13. • Algoritmo de ordenação do tipo dividir-para-conquistar; • Utiliza memória

    auxiliar, portanto não é in-place; • É estável, ou seja, não troca posições de valores iguais; • Utiliza funções recursivas; • A eficiência é consistente porque ele tem a mesma complexidade em todos os casos; • Para conjuntos de dados muito pequenos não é bom por conta da recursão e uso de memória adicional que em caso como o Insertion sort performa melhor; • Mais adequado para conjuntos de dados muito grandes. Algoritmo Merge Sort
  14. Divisão: Divide a lista não ordenada em n sublistas de

    um único elemento. Conquista: Recursivamente ordena as sublistas criadas no passo anterior. Combinação (Merge): Mescla as sublistas ordenadas para criar novas sublistas ordenadas até que haja apenas uma sublista contendo todos os elementos ordenados. Merge Sort Método de Solução
  15. Merge Sort Análise de Complexidade Melhor Caso • A lista

    já está ordenada; • O(n log n) Pior Caso • A lista está inversamente ordenada; • O(n log n)
  16. • Eficiente para diferentes tamanhos de dados de entrada, pequenos

    ou grandes; • É estável, portanto não troca valores iguais; • É adaptável aos diferentes padrões de dados devido seu método híbrido; • É mais complexo de implementar se comparado aos outros algoritmos de ordenação; • Os subarrays gerados são chamados runs; • Timsort tem uma complexidade de tempo de pior caso de O(n log n), que é a mesma de outros algoritmos de classificação populares, como Merge Sort e Quick Sort. Algoritmo Timsort
  17. Checa o tamanho da lista: Se for menor que 64

    elementos, utiliza o Insertion sort. O Insertion é altamente eficiente na faixa de 23 a 64 elementos. Se maior que 64: Vai procurar runs (blocos já ordenados crescente ou decrescente) e também definir minruns, entre 32-64 porque o Insertion é eficiente para ser aplicado. Não pode ser maior que 256 nem menor que 8 ou se n/minrun for uma potência de 2. Mergear os runs ordenados: Os sub-vetores ordenados são mergeados utilizando o Merge Sort. Timsort Método de Solução
  18. arr = [6, 5, 4, 3, 2, 1] arr.sort() #

    ou sorted(arr) Timsort Código no Python
  19. Timsort Análise de Complexidade Melhor Caso • A lista já

    está ordenada; • O(n) Pior Caso • A lista não está ordenada e vai fazer n log n comparações até ordenar o vetor de tamanho n. • O(n log n)
  20. Recomendações de Livros • Entendendo Algoritmos: Um Guia Ilustrado Para

    Programadores e Outros Curiosos, Aditya Y. Bhargava • Algoritmos - Teoria e Prática, Thomas Cormen