Share
Embed
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
Transcript
30 slides
-
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 -
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 -
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 -
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 -
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 -
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!) -
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 -
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) -
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. -
• 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 -
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 -
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²) -
• 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 -
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 -
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) -
• 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 -
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 -
arr = [6, 5, 4, 3, 2, 1] arr.sort() #
ou sorted(arr) Timsort Código no Python -
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) -
Recomendações de Livros • Entendendo Algoritmos: Um Guia Ilustrado Para
Programadores e Outros Curiosos, Aditya Y. Bhargava • Algoritmos - Teoria e Prática, Thomas Cormen