Complexidade de Algoritmos

Estruturas de DadosMsc. Marcelo Aires

➢ Introdução➢ Algoritmos ótimos➢ Exemplos de algoritmos ótimos

Relembrando

➢ Introdução➢ Estruturas lineares➢ Pilha e Fila➢ Árvores

Agenda

INTRODUÇÃO ÀSESTRUTURAS DE DADOS

5

➢ Algoritmos manipulam conjuntos de dados que podem crescer, diminuir ou sofrer diversas modificações durante sua execução.

➢ Uma estrutura de dados é uma implementação de um tipo abstrato de dados○ tipo abstrato de dados: conjunto de dados, as relações entre

eles e as operações que podem ser aplicadas aos dados.

Introdução

➢ O segredo dos algoritmos eficientes é a escolha de uma boa estrutura de dados que pode ter grande impacto na velocidade de um programa.

➢ Cada estrutura possui suas especificações:○ Estruturas diferentes suportam operações diferentes em

tempos diferentes, de forma que nenhuma estrutura funciona bem em todas as circunstâncias.

➢ Importante conhecer as qualidades e limitações de cada estrutura de dados.

Introdução

O QUE SÃOESTRUTURAS LINEARES?

8

➢ São estruturas que mantém os itens em uma única linha, sendo as mais simples e clássicas, e formam a base para vários algoritmos.

➢ Exemplos:○ vetor○ lista encadeada

Estruturas Lineares

➢ É uma coleção de itens de um mesmo tipo que são referenciados por um identificador único (índice).

➢ Os elementos ocupam posições próximas na memória, permitindo acesso direto (Θ(1)) através de um índice.

➢ Para um vetor A[1..n] ou A = (a1, a2, . . . , an), considera-se A[i] o elemento que está armazenado na i-ésima posição de A, para todo i com 1 ≤ i ≤ n.

Vetor

➢ O tempo da busca linear em um vetor de tamanho n é O(n) -> no pior caso, acessa todos os elementos do vetor.

➢ A inclusão de um novo elemento em um vetor pode ser feita em tempo constante Θ(1) ao inseri-lo na primeira posição disponível.

➢ A remoção de algum elemento do vetor envolve inicialmente uma busca pela posição, por isso, leva tempo O(n).

Vetor

➢ Se vetor ordenado, mudam-se tempos.○ pode-se usar busca binária (O(log n)).○ a inserção, no entanto, precisa garantir que o vetor

continue ordenado, podendo ter que mover vários elementos do vetor (O(n)).

○ a remoção precisa de O(n) para mover os elementos à direita do elemento removido e manter o vetor ordenado.

Vetor

➢ É uma estrutura de dados onde cada elemento é armazenado em um nó○ armazena endereços para outros nós da lista.

➢ Cada nó de uma lista pode estar em uma posição diferente da memória, sendo diferente de um vetor.

➢ Na forma mais simples, têm-se acesso apenas ao primeiro nó da lista.

Lista encadeada

➢ Em qualquer variação, têm-se acesso a um número constante de nós apenas (o primeiro nó, o último nó).

➢ Listas não permitem acesso direto a um elemento:○ para acessar o k-ésimo elemento da lista, deve-se acessar o

primeiro, depois os próximos, até ter acesso ao k-ésimo.➢ Consideramos que cada nó contém um atributo chave e,

como sempre, pode conter outros atributos importantes (endereços, quantidade e significado).

Lista encadeada

➢ Em uma lista encadeada simples existe apenas um atributo de endereço, chamado próximo○ acesso ao nó imediatamente após o nó atual.

➢ Em uma lista duplamente encadeada existe, o atributo próximo e o atributo anterior○ acesso ao nó imediatamente antes do nó atual.

➢

Lista encadeada

Lista encadeada

Lista encadeadaO(n)

Θ(1)

Θ(1) O(n)

O QUE SÃOPILHAS E FILAS?

18

➢ É uma coleção dinâmica de dados cuja operação de remoção, remove o elemento mais recente.○ política LIFO (last in, first out).

➢ Tipo abstrato de dados que oferece as operações de adicionar e remover um elemento em tempo Θ(1).

➢ Existem inúmeras aplicações para pilhas:○ verificação de palíndromo;○ operação “desfazer”;○ algoritmos de busca em profundidade em grafos.

Pilha

Pilha

➢ P. topo é o índice do elemento inserido por último.➢ P. capacidade contém a capacidade total do vetor.

➢ É uma coleção dinâmica de dados cuja operação de remoção, remove o elemento mais antigo.○ política FIFO (first in, first out)

➢ Tipo abstrato de dados que oferece as operações de adicionar e remover um elemento em tempo Θ(1).

➢ Existem inúmeras aplicações para filas:○ ordem de atendimento;○ spooler de impressão;○ outros controles de acesso à recursos.

Fila

Fila

➢ F. cabeca é o índice do elemento inserido primeiro.➢ F. cauda é o índice do último elemento inserido na fila.➢ F.capacidade = n.

O QUE SÃOÁRVORES?

23

➢ São estruturas não lineares constituídas de nós, onde cada nó contém valor e chave, e pode ter uma ou mais ligações para outros nós.

➢ Especificamente, são estruturas hierárquicas nas quais cada nó acessa os nós imediatamente “abaixo” (filhos).

➢ Nó que não possui filhos é uma folha.➢ Um nó especial é a raiz (topo da hierarquia) - nível 0.➢ Um nó não pode ter dois pais e a raiz é o único nó que

não possui pai.

Árvores

➢ Inicialmente somente é possível acessar o nó raiz, qualquer busca por uma chave precisa ser feita percorrendo-se a árvore inteira (no pior caso) - tempo linear O(n).

➢ Atenção para não confundi todasas árvores com árvores binárias debusca.

Árvores

➢ São árvores em que qualquer nó possui no máximo dois filhos (esquerdo e direito).

➢ Definição: uma árvore binária é uma árvore vazia ou um nó que possui ligações para duas árvores binárias.

➢ Considera-se que todo nó possui os atributos chave, esq e dir.

➢ Para toda folha, temos esq = dir = null.➢

Árvores binárias

➢ Definição: Uma árvore binária de busca é uma árvore binária em que, para cada nó, todos os nós da subárvore esquerda possuem chaves menores e da subárvore direita possuem chaves maiores.

➢ Principais operações são busca, inserção e remoção.

Árvores binárias de busca

➢ Para a operação de busca (k):○ três eventos podem ocorrer:

■ k = chave do elemento e a busca termina;■ k < chave do elemento, problema na subárvore esquerda;■ k > chave da raiz, problema reduz na subárvore direita.

Árvores binárias de busca

➢ Para a operação de inserção (r, x):○ três eventos podem ocorrer:

■ r é vazia, x é a nova árvore;■ busca por x.chave, caso não encontre, x será filho do nó que

parou:● x.chave < r.chave, insere x à esquerda;● x.chave > r.chave, insere x à direita.

Árvores binárias de busca

➢ Para a operação de remoção (r, x):○ três eventos podem ocorrer:

■ x não tem filho esquerdo, então substitui x por x.dir;■ x tem filho esquerdo mas não tem filho direito, então

substitui x por x. esq;■ x tem os dois filhos, então substitui x por seu sucessor y e

removemos y de seu local atual (o que pode ser feito recursivamente).

Árvores binárias de busca

Árvores binárias de busca

➢ CORMEN, T. H.; STEIN, C.; LEISERSON, C.; RIVEST, R. L. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2002.

➢ Lintzmayer, C N; Mota, G O. Análise de Algoritmos e Estruturas de Dados. Disponível em: http://professor.ufabc.edu.br/~g.mota/livros/Livro%20-%20Analise%20de%20Algoritmos.pdf. Acesso em: 18 Abr 2020

Referências

➢ Pesquise e crie um vídeo explicativo sobre as estruturas de dados e algoritmos abaixo (definidos em aula):○ Tabelas Hash;○ Árvore vermelho-preta;○ Programação dinâmica;○ Algoritmos gulosos;○ Árvore B;○ Heaps binomiais e de Fibonacci;○ Estruturas de dados para conjuntos disjunto;○ Algoritmos em Grafos

■ Algoritmo de Dijkstra (caminhos mais curtos)■ Algoritmo de Prim e Kruskal (árvore geradora de custo mínimo)

Exercício

➢ O conteúdo do vídeo deve conter:○ conceitualização;○ exemplos de problemas e suas descrições;○ possíveis soluções de algoritmos e suas complexidades;○ estrutura de dados comumente utilizada;○ (extra) comparação com outras estruturas de dados.

Exercício