ALGORITMO E COMPLEXIDADE

Prévia do material em texto

Algoritmo e
complexidade
Algoritmo: 
É a estrutura básica para
a resolução de problemas
computacionais. Como uma
receita de bolo: tem um
conjunto de instruções finitas,
que devem ser seguidas em
determinada ordem para se
resolver um problema. 
Complexidade
Quanto maior for a variedade de
problemas a serem resolvidos,
maior será a complexidade do
algoritmo.
 problemão 
 
 probleminhas
sub-rotinas
Sub-rotina
Também chamada de subprograma,
é um bloco de instrução que
realiza tarefas específicas. É
utilizada para diminuir a
complexidade de um problema,
subdividindo-o em pequenas
tarefas (mini problemas). 
Objetivos da Sub-rotina
Dividir e estruturar um
algoritmo em partes logicamente
coerentes;
Testar os trechos de código
separadamente com maior
facilidade;
Aumentar a legibilidade de um
programa;
Evitar a repetição de sequências
de comandos em vários locais do
código.
Vantagens da Sub-rotina
Clareza e legibilidade no
algoritmo;
Construção independente;
Testes individualizados;
Simplificação da manutenção;
Reaproveitamento de algoritmos.
Programação Estruturada
Paradigma da programação utilizado
para a decomposição de problemas
(subdividir problemões em
probleminhas). Nesta abordagem, o
método mais adequado para decompor
problemas é o TOP-DOWN. 
MÉTODO TOP-DOWN
Permite que o programa tenha uma
estrutura parecida com a de um
ORGANOGRAMA. O problema é dividido
em “refinamentos sucessivos” e as
partes que derivam dessa divisão
chamam-se “módulos” ou
“subalgoritmos”. 
Divida o problema em suas partes
principais;
1.
Analise a divisão para garantir
a coerência;
2.
Se alguma parte ainda estiver
complexa, volte para o passo 1.
3.
Analise o resultado para
garantir o entendimento e a
coerência. 
4.
Refinamentos Sucessivos
Declarando sub-rotinas
Uma sub-rotina é um bloco com início
e fim, sendo identificada por um
nome, pelo qual será referenciada em
qualquer momento e em qualquer parte
do programa, assim como uma FUNÇÃO
ou MÉTODO.
Sintaxe da sub-rotina:
 //sub-rotina (método) que calcula o dobro de um
número
public static int calcularDobro(int numero) {
return numero * 2; 
}
public static void main(String[ ] args) {
//chamada da sub-rotina
int resultado = calcularDobro(5);
System.out.println(“O dobro de 5 é: ” + resultado); 
}
Várias sub-rotinas
Um programa pode ter mais de uma
sub-rotina. Depois de executar a
primeira sub-rotina, o controle
volta para o programa principal. Em
seguida, a segunda sub-rotina é
executada e, ao fim, o programa
principal retoma o controle. 
Fluxo de execução:
Parâmetros são os valores que uma
sub-rotina pode receber antes de
iniciar sua execução. Através dos
parâmetros, é possível tornar uma
sub-rotina mais genérica e,
portanto, mais reutilizável.
EX: em vez de um método que calcula
a tabuada de 8, um método que
calcula a tabuada de qualquer número
digitado pelo usuário. 
Parâmetros e sub-rotinas
Passagem por valor
Na passagem de parâmetros por valor,
o valor da variável na chamada é
copiado para a variável da função. 
As alterações feitas dentro da
função ou método NÃO são salvas na
variável original.
EXEMPLO:
public class ExemploPassagemPorValor {
 public static void main(String[] args) {
 int numero = 10;
 System.out.println("Antes de chamar o
método: " + numero);
 modificarValor(numero);
 System.out.println("Depois de chamar o
método: " + numero);
 }
 public static void modificarValor(int valor) {
 valor = 20;
 System.out.println("Dentro do método: " +
valor);
 }
}
Passagem por referência
Na passagem de parâmetros por
referência, os endereços de memória
das variáveis são acessados
diretamente.
As alterações feitas dentro da
função ou método também ocorrem na
variável original.
EXEMPLO:
class ExemploObjeto {
 int valor;
 ExemploObjeto(int valor) {
 this.valor = valor;
 }
}
public class ExemploPassagemPorReferencia {
 public static void main(String[] args) {
 ExemploObjeto obj = new ExemploObjeto(10);
 System.out.println("Antes de chamar o
método: " + obj.valor);
 modificarObjeto(obj);
 
continuação...
System.out.println("Depois de chamar o método: "
+ obj.valor);
 }
 public static void modificarObjeto(ExemploObjeto
objeto) {
 objeto.valor = 20;
 System.out.println("Dentro do método: " +
objeto.valor);
 }
}
OBRIGATÓRIOS NUMA FUNÇÃO:
Tipo de retorno
Nome da função
Corpo da função
NÃO OBRIGATÓRIOS:
Parâmetros
OBSERVAÇÕESOBSERVAÇÕES
Uma Função SEMPRE retorna um valor.
OBSERVAÇÕESOBSERVAÇÕES
Procedimento NÃO retorna valor.
Os tipos primitivos (int, char,
boolean, float...) não são
suficientes para representar todos
os tipos de informação, nem servem
para guardar mais de uma informação. 
Veremos agora que os tipos
primitivos podem ser usados para
construir estruturas mais complexas,
como vetores (arrays), matrizes e
registros. 
GUARDANDO + INFO
Conhecido também como: 
Variáveis indexadas
Variáveis compostas
Variáveis subscritas
Arranjos
Vetores
Tabelas em memória
Arrays
Arranjo Unidimensional
Homogêneo
Um vetor é um tipo de variável
homogênea que repete determinado
dado N vezes. Ou seja, é um arranjo
de elementos armazenados na memória
principal, com várias colunas e
APENAS uma linha (arranjo
unidimensional). 
VETOR
EXEMPLO:
Segue abaixo um exemplo de vetor com 10
elementos (ou seja, 10 variáveis), todas com
o mesmo nome, porém diferenciadas pela
posição no arranjo (indicada por um índice
que inicia em 0):
Variáveis em azul
(cada uma com um valor)
Índice abaixo das variáveis
(começa em 0)
EXEMPLO:
Representamos o vetor do exemplo anterior em
ALGORITMO da seguinte forma:
Após o igual, 
vem o valor da
variável
Posição da variável (índice) 
entre colchetes [ ]
DECLARANDO VETORES
Declaramos um vetor assim em Java:
tipo[ ] nomeDoVetor; 
Depois de declarar um vetor, é possível
inicializá-lo especificando o seu tamanho
(ou seja, quantos elementos ele terá): 
int[ ] numerosInteiros = new int[ 5 ]; 
Ou, então, se já souber os valores,
inicializando-o diretamente:
int[ ] numerosInteiros = {1, 2, 3, 4, 5}; 
Tipo de variável heterogênea que
trabalha com vários dados de tipos
diferentes (campos) em uma mesma
estrutura. Os elementos de um
registro são alocados em posições de
memória adjacentes. 
REGISTRO
DECLARANDO REGISTROS
Declaramos um registro assim em Pascal:
type 
Pessoa = record 
nome: string[50]; 
idade: integer; 
end;
Declarando uma variável do tipo registro:
 pessoa1: Pessoa;
Atribuindo valores aos campos do registro:
pessoa1.nome := 'João'; 
pessoa1.idade := 30;
Exibindo os valores:
writeln('Nome: ', pessoa1.nome); 
writeln('Idade: ', pessoa1.idade); 
end.
Tipo especial de variável que serve
para guardar o endereço de memória
de outra variável (já declarada
anteriormente no programa). Permite
acessar uma variável de forma
indireta. 
PONTEIRO
Vantagens do Ponteiro
Permite fazer a passagem de
parâmetros por referência;
Pode ser usado no lugar de uma
matriz;
Manipula os elementos de uma
matriz mais facilmente;
Permite criar estruturas de
dados mais complexas (listas
encadeadas e árvores binárias);
Aloca e desaloca memória
dinamicamente;
Passa para uma função o endereço
de outra função. 
DECLARANDO PONTEIROS
Declaramos um ponteiro assim em C:
int main() { 
int valor = 10; // Declara uma variável int
int *ponteiro; // Declara um ponteiro int 
Modificando o valor usando o ponteiro:
Exibindo os valores:
 *ponteiro = 20; 
printf("Novo valor da variável 'valor': %d\n",
valor); 
printf("Novo valor armazenado no ponteiro:
%d\n", *ponteiro); 
return 0;
 }
Especificá-lo através de suas
propriedades;
1.
Definir sua arquitetura por meio
da estrutura de dados;
2.
Indicar o seu nível de
complexidade, considerando o seu
tempo de execução e o espaço
ocupado na memória;3.
Implementá-lo em uma linguagem
de programação;
4.
Executar testes. 5.
Definindo um algoritmo
Desempenho;
Simplicidade;
Clareza;
Segurança;
Funcionalidade;
Modularidade;
Interface amigável. 
Características de um
(bom) algoritmo
É uma característica fundamental
para os algoritmos. Um algoritmo
correto é aquele que gera a saída
esperada para qualquer conjunto de
entradas válidas. Após gerar a saída
esperada, o algoritmo também deve
terminar sua execução. 
Corretude
A eficiência de um algoritmo pode se
associar à:
Quantidade de armazenamento que
utiliza;
Quantidade de tráfego que gera
em uma rede de computadores;
Quantidade de dados que precisa
mover do/para o disco.
Eficiência
Tempo de execução
Tamanho da entrada
 a ser processada
Eficiência =
Método de Cramer x Método de Gauss
Ambos os algoritmos calculam o tempo de
operação de um computador real, para avaliar
sua eficiência. 
Cramer(n!) x Gauss(n³)
+ simples + complexo
inviável para
entradas maiores 
Crescimento
estável
O desempenho de um algoritmo deve
ser desassociado do desempenho da
máquina que o executará. A análise
de um algoritmo se baseia em 2 tipos
de complexidade:
1) Espacial: quanto de memória usa.
II) Temporal: 
 -> Tempo de execução
 -> Número de instruções necessárias
para a execução.
Análise de algoritmos
Serve para prever quanto tempo um
algoritmo vai demorar para terminar
sua execução à medida que o problema
fica maior. Aqui, não nos
preocupamos com números exatos, mas
com a tendência: se o tempo de
execução vai dobrar, triplicar etc. 
Assim sendo, considerando-se um
algoritmo com tamanho de entrada n,
a eficiência de um algoritmo é
definida por uma função f(n) e a
análise assintótica descreve a
eficiência do algoritmo quando n
torna-se grande. 
 
Análise Assintótica
É a forma matemática de se prever o
pior caso de cada algoritmo, isto é,
a configuração de código que demanda
o maior número de operações para a
solução do problema. 
LEMBRE-SE: a análise da complexidade
de um algoritmo é SEMPRE feita na
visão do pessimista, ou seja, na
análise do pior caso apresentado ao
algoritmo.
A notação O
Melhor caso:
O(n): tempo de execução proporcional
ao tamanho da lista. 
EX: se n = 10, levará 10 unidades de
tempo para ser executado.
Pior caso:
O(n²): se n dobrar, o tempo de
execução vai multiplicar por 4. 
EX: se n = 10 levava 10 unidades de
tempo para ser executado, n = 20
pode demorar cerca de 40 unidades (4
vezes mais que o tempo de n = 10). 
Exemplos de notação O
Operações aritméticas;
Comparações;
Atribuições;
Resolver um ponteiro ou
referência;
Indexação em um arranjo;
Chamadas/retornos de funções e
métodos.
São as operações primitivas usadas
pela máquina para realizar certas
atividades. 
Passos Básicos
OPERAÇÕES BÁSICAS
É baseada na quantidade de passos
básicos executados para se encontrar
a solução de um problema.
Um algoritmo geralmente tem
componentes que são formados por
passos básicos, os quais dão sua
contribuição para a complexidade do
algoritmo. 
 
Complexidade do
algoritmo
Uma componente CONJUNTIVA de um
algoritmo é a parte do código que a
gente tem certeza que será executada
toda vez que executarmos o
algoritmo, sem exceção. 
Desempenho do algoritmo = 
SOMA das componentes conjuntivas.
Pior caso = SOMA do pior caso de
cada uma das conjuntivas.
Componente Conjuntiva
Uma componente DISJUNTIVA de um
algoritmo é a parte do código que
pode ou não ser executada, a
depender dos valores colocados no
algoritmo. 
Desempenho do algoritmo = 
considerar a MAIOR COTA superior
entre as duas componentes.
Pior caso = pior caso de execução
entre as duas disjuntivas.
Componente Disjuntiva
Quando analisamos a complexidade de
um algoritmo, os termos de ordem
mais alta “absorvem” os menores, ou
seja, os termos que crescem mais
devagar se tornam irrelevantes
quando o tamanho da entrada (n) é
muito grande. 
Princípio da absorção
EX: imagine um algoritmo com tempo de execução
descrito por f(n) = 3n² + 5n + 10.
Temos 3 termos: 3n² (quadrático), 5n (linear) e 10
(constante). 
Quando n aumenta bastante, o termo 3n² cresce
muito mais rápido que os outros, tornando 5n e 10
irrelevantes (ele os absorve). Assim, dizemos que a
complexidade do algoritmo é O(n²). 
Refere-se ao comportamento de um
algoritmo quando o tamanho da
entrada (n) cresce infinitamente. É
o limite superior de quanto tempo ou
recursos o algoritmo vai precisar à
medida que o número de dados cresce. 
Máximo Assintótico
EX: se temos dois algoritmos:
O(n) --> complexidade linear
O(n²) --> complexidade quadrática
Quando n aumenta muito, o algoritmo O(n²)
crescerá bem mais rapidamente que o O(n). Assim
sendo, O(n²) possui um máximo assintótico MAIOR
que O(n). 
Referem-se ao pior caso possível
para o tempo de execução ou o uso de
recursos de um algoritmo. Significa
que olharemos o cenário mais
desfavorável, em que o algoritmo
levaria o maior tempo para terminar
ou consumiria o máximo de memória. 
Complexidades
Pessimistas
ATRIBUIÇÃO: a complexidade num
algoritmo desse tipo indica quanto
tempo leva para realizar uma
atribuição de valor em um programa.
COMPLEXIDADE: O(n) tempo constante. 
Ou seja, atribuiu executou. 
Complexidades
Pessimistas
REPETIÇÃO: a complexidade num
algoritmo desse tipo indica quanto
tempo leva para executar estruturas
de repetição (loops).
COMPLEXIDADE: O(n) tempo constante. 
 
Complexidades
Pessimistas
REPETIÇÃO ANINHADA: a complexidade
num algoritmo desse tipo indica
quanto tempo leva para executar
estruturas de repetição (loops), uma
dentro da outra.
COMPLEXIDADE: O(n²) quadrática. 
 
Complexidades
Pessimistas
CONDIÇÃO: a complexidade num
algoritmo desse tipo indica quanto
tempo ele leva para executar, a
depender das condições que verifica.
COMPLEXIDADES: 
O(1)-> CONDIÇÃO SIMPLES (IF) 
O(n)-> CONDIÇÃO COMPOSTA (IF-ELSE) 
 
Complexidades
Pessimistas
CHAMADAS ÀS SUB-ROTINAS: a
complexidade num algoritmo desse
tipo indica quanto tempo ele leva
para chamar métodos e/ou funções.
COMPLEXIDADE: O(n) tempo constante. 
 
Complexidades
Pessimistas
Técnica em que uma função chama a si
mesma para resolver um problema.
Pode ser usada para definir uma
sequência de objetos, funções de
objetos e conjuntos. 
Recursividade
Método de resolução de problemas que
envolve quebrar um problema em
pequenas partes, até chegar num
tamanho em que possa ser resolvido
normalmente. Em geral, a recursão
abrange uma função que chama a si
mesma (função recursiva). 
Recursão
Função que quebra o problema em
pequenas partes e se chama para
resolvê-las (chamadas recursivas).
Depois que encontra uma solução
direta para o problema, ela encerra
sua execução (caso base). 
EX: fatorial de um número n 
Função recursiva
Caso base: Se n = 1, então n! = 1
Chamadas recursivas: 
se n > 1, então n! = n(n - 1)!
A função que calcula o fatorial de n continua
chamando a si mesma com n - 1, até que atinja o caso
base (n = 1). 
Também chamada de DEFINIÇÃO
INDUTIVA, é uma maneira de definir
um conceito simples ou estrutura,
passo a passo, começando com um caso
básico e, em seguida, estabelecendo
regras para lidar com casos mais
complexos, a partir dos casos mais
simples. 
Definição Recursiva
Este princípio é utilizado para
provar a correção de algoritmos
recursivos ou para demonstrar que
uma propriedade é válida para todas
as entradas de um determinado
problema. 
Indução matemática
Caso base da indução: provar que um
valor é verdadeiro para o menor valor
possível, em geral, n = 0 ou n = 1. 
Passo Indutivo: assumir que a afirmação
é válida para um valor qualquer n = x 
Lista de objetos enumerados em
determinada ordem. Uma sequência
recursiva explicita seu(s)
primeiro(s) valor(es) e define
outros valores na sequência, em
termos dos valores iniciais.
EX: sequência de potências de 2Sequência
a ^ 0 = 1
a ^ n = 2 ^ n, tal que n = {0, 1, 2, 3, 4...}
É a adição de uma sequência de
quaisquer tipos de números
(parcelas) usando-se uma notação. 
Imagine que você queira somar os
números de 1 a 5. Podemos
representar essa soma assim: 
Somatório
i = representação do número
i = 1 representa o valor inicial de i
O 5 (em cima do Sigma) é o valor final de i
O i (na frente do Sigma) é a fórmula ou valor 
da soma a cada passo. 
Estrutura que possui elementos
finitos e ordenados.
Conjuntos
Caso base dos conjuntos: especificar
uma coleção inicial de elementos. 
Passo recursivo dos conjuntos: criar
regras para formar novos elementos a
partir daqueles que já estão no conjunto. 
Algoritmo Recursivo
x
Algoritmo Iterativo
Recursivo Iterativo
Resolve um problema
dividindo-o em problemas
menores. O algoritmo
chama a si mesmo com
esses subproblemas até
que atinja um caso base,
onde o problema é
simples o suficiente
para ser resolvido sem
chamadas recursivas. 
Resolve um problema
usando estruturas de
repetição, como loops
(for, while). Ele executa
repetidamente um bloco de
código até que uma
condição de término seja
atendida. Em vez de
chamar a si mesmo, ele
controla o problema
através de variáveis. 
3 leis da Recursão
LEI I
Um algoritmo recursivo deve ter um CASO
BÁSICO (ou seja, um ponto onde a função será
encerrada, porque o problema já foi
resolvido).
***CASO BÁSICO DE FUNÇÃO FATORIAL --> n == 0 
3 leis da Recursão
LEI II
Um algoritmo recursivo deve mudar o seu
estado e se aproximar do caso básico. 
(os dados devem ser alterados tendo em vista
diminuir os problemas, para resolvê-los
melhor. 
3 leis da Recursão
LEI III
Um algoritmo recursivo deve chamar a si
mesmo, recursivamente. 
Na recursão linear, a função faz uma única
chamada recursiva a cada passo do algoritmo.
Por isso, a recursão linear é a mais
adequada para encontrar o elemento máximo em
uma lista.
Tipos de Recursividade
Recursão linear
Aqui, a chamada recursiva é a última
operação a ser realizada pela função. Isto
é, após a chamada recursiva, a função não
faz mais nada, apenas retorna o resultado.
FUNÇÃO RECURSIVA EM CAUDA --> 
RESULTADO FINAL DA CHAMADA RECURSIVA 
= 
RESULTADO FINAL DA FUNÇÃO 
Tipos de Recursividade
Recursão em cauda
Tipos de Recursividade
Recursão Indireta
É quando uma função invoca a si mesma
através de outra(s) função(ões). 
FUNÇÃO RECURSIVA INDIRETA --> P chama Q, que chama R,
que chama P. 
Tipos de Recursividade
Recursão Aninhada
É quando uma função recursiva pode receber
um argumento que inclui outra função
recursiva. 
Desvantagens
Vantagens
Função Recursiva
Torna o código mais simples e fácil de
entender;
Código menor e mais elegante;
Útil para problemas com subdivisões
repetidas.
Consome muita memória e corre o risco de
stack overflow (quando há excesso de
dados a serem armazenados);
Depuração mais complexa;
Processamento mais lento (por causa das
chamadas de função).
***A quantidade de chamadas recursivas deve ser finita,
pois funções recursivas utilizam bastante memória. 
Desvantagens
Vantagens
Função Iterativa
Uso da memória mais eficiente;
Processamento mais rápido;
Fácil de depurar e testar.
Solução mais difícil e menos intuitiva;
Torna o código maior e mais complexo;
Escrita menos elegante do código.
Método de organizar um conjunto de objetos
em uma ordem (ascendente ou descendente).
Colocar um conjunto de dados em determinada
ordem predefinida permite que o acesso a
eles ocorra de maneira mais eficiente. 
É feita usando-se como base uma CHAVE DE
ORDENAÇÃO (campo do item, que serve para
comparação). É por meio dessa chave que
podemos saber se um elemento está à frente
ou não de outros no conjunto de dados. 
Processo de Ordenação
Ordenação
Aquele que coloca os elementos de dada
sequência em uma ordem predefinida. 
Algoritmos de ordenação interna (in-place): o
conjunto de dados é pequeno e cabe todo na memória
principal. Os dados a se ordenar estão em um VETOR
ou em uma TABELA, e a ordenação é feita por um
campo chamado CHAVE, que identifica cada elemento
do vetor que forma a tabela.
Algoritmos de ordenação externa: o conjunto de
dados NÃO cabe na memória principal. Dados são
armazenados como registros, podendo ser acessados
sequencialmente ou em blocos. 
Processo de Ordenação
Algoritmo de ordenação
MÉTODO: ORDENAÇÃO POR INSERÇÃO
INSERTION SORT (inserção direta): pega um elemento
de cada vez, inserindo-o em seu devido lugar (no
array). É como uma mão de cartas no baralho, que a
gente vai ordenando de forma crescente, uma por
uma. 
SHELL SORT: divide o conjunto de dados em
sublistas, escolhendo um intervalo (GAP) que
determina a distância entre os elementos que serão
comparados. Para cada sublista, ocorre a inserção
direta, mas comparando e trocando elementos que
estão distantes (de acordo com o valor do GAP). O
valor do GAP reduz a cada iteração (até chegar a 1)
e o processo continua até tudo estar ordenado. 
Processo de Ordenação
Tipos de Algoritmo de ordenação
MÉTODO: ORDENAÇÃO POR TROCA
BUBBLE SORT (Bolha): em cada etapa, cada elemento é
comparado com o próximo, havendo a troca se o
elemento não estiver na ordem certa. A comparação é
realizada até que as trocas não sejam mais
necessárias. 
 
QUICK SORT (Troca e partição): o algoritmo de
ordenação interna MAIS RÁPIDO. Escolhe um pivô,
divide o array em torno desse pivô e ordena as
partições (sublistas) recursivamente. 
Processo de Ordenação
Tipos de Algoritmo de ordenação
MÉTODO: ORDENAÇÃO POR SELEÇÃO
SELECTION SORT (Seleção direta): a cada passo,
seleciona o melhor elemento (maior ou menor, a
depender da ordenação) para ocupar aquela posição
do array. 
HEAP SORT: extrai, repetidamente, o maior (ou
menor) elemento de uma estrutura, até que todos
elementos estejam ordenados. Também quebra o
problema maior em partes menores (um heap de
tamanho reduzido a cada iteração). 
Processo de Ordenação
Tipos de Algoritmo de ordenação
MÉTODO: ORDENAÇÃO POR INTERCALAÇÃO
MERGE SORT: o Merge Sort divide os dados em
conjuntos cada vez menores para, depois, ordená-los
e combiná-los por meio da intercalação.
Representado por uma ÁRVORE BINÁRIA (cada nó =
chamada recursiva, nó raiz = chamada principal e
folhas = casos bases ou vetores de 1 ou 2 números. 
 
Processo de Ordenação
Tipos de Algoritmo de ordenação
Processo de Ordenação
Funcionamento do Merge Sort
Vamos ordenar os números 72943861 usando Merge
Sort.
Partimos o vetor sempre na metade:
Processo de Ordenação
Funcionamento do Merge Sort
Depois, fazemos uma chamada recursiva para
partir a primeira partição do vetor: 
Processo de Ordenação
Funcionamento do Merge Sort
Uma nova chamada recursiva é realizada para
partir, mais uma vez, a partição: 
Processo de Ordenação
Funcionamento do Merge Sort
Mais duas chamadas recursivas para o caso base
encontrado (7 e 2):
Processo de Ordenação
Funcionamento do Merge Sort
Em seguida, ocorre a intercalação para ordenar
o caso base (7 e 2). 
Processo de Ordenação
Funcionamento do Merge Sort
O mesmo é feito para o outro caso base (9 e
4):
Processo de Ordenação
Funcionamento do Merge Sort
É feita uma intercação para ordenar a primeira
partição do valor:
Processo de Ordenação
Funcionamento do Merge Sort
O mesmo processo ocorre com a segunda
partição:
Processo de Ordenação
Funcionamento do Merge Sort
Por último, há uma intercalação para ordenar
as duas principais partições do vetor: 
Comparando algoritmos
Desvantagens
Vantagens
Bubble Sort
Usa pouca memória adicional;
É simples e fácil de entender e
implementar;
É estável (mantém a ordem relativa de
elementos iguais);
Melhor caso = O(n). 
Ruim com grande quantidade de dados ou
que demandem velocidade --> Complexidade
= O(n²);
É ineficiente: faz trocas desnecessárias
e é lento. 
Desvantagens
Vantagens
SelectionSort
Usa pouca memória adicional;
É simples e fácil de entender e
implementar;
Faz menos trocas que o Bubble Sort.
Ruim com grande quantidade de dados -->
Complexidade = O(n²);
É instável (não preserva a ordem entre
dois elementos iguais);
Desempenho consistente, mas ruim (sempre
percorre a lista toda, independentemente
do estado inicial dos dados. 
Desvantagens
Vantagens
Insertion Sort
Usa pouca memória adicional;
É simples e fácil de entender e
implementar;
É estável (mantém a ordem relativa de
elementos iguais);
Melhor caso = O(n). 
Ruim com grande quantidade de dados -->
Pior caso = O(n²);
Faz muitas comparações e movimentações;
Não indicado para listas com elementos
muito desordenados. 
Desvantagens
Vantagens
Shell Sort
É uma adaptação melhorada do Insertion;
Menos trocas e comparações (diminui o
número de incrementos para comparação
dos elementos do vetor);
É fácil e simples de implementar;
Mais eficiente que Bubble, Insertion e
Selection Sort;
Bom para quantidade moderada de
elementos. 
Pior caso = algo entre O(n²) e O(n3/2);
É instável;
Menos eficiente que Quick e Merge Sort. 
Desvantagens
Vantagens
Merge Sort
Mesma complexidade para todos os casos:
O(n log n);
É eficiente com grande quantidade de
dados;
É estável (mantém a ordem relativa de
elementos iguais).
Requer memória adicional;
Mais lento que o Quick Sort;
Mais complicado de implementar e
entender. 
Desvantagens
Vantagens
Quick Sort
Complexidade média de: O(n log n);
Usa pouca memória adicional;
É eficiente com grande quantidade de
dados e com elementos desordenados.
Pior caso = O(n²) --> quando se escolhe
mal o pivô, por exemplo;
É instável (não preserva a ordem dos
elementos iguais);
Pode exigir uma recursão profunda, o que
pode causar estouro de pilha (stack
overflow). 
Stack Overflow
A pilha de execução é uma área da memória
reservada para guardar informações sobre as
chamadas de funções, tais como variáveis
locais e endereços de retorno.
STACK OVERFLOW é um erro que acontece quando
a pilha de um programa se enche além da sua
capacidade, causando um erro de execução. 
Árvore Binária
Estrutura de dados hierárquica, na qual cada
NÓ possui, no máximo, 2 FILHOS (filho
esquerdo e filho direito). Representada em
memória por ALOCAÇÃO DINÂMICA. É composta
por:
NÓ: representa cada elemento da árvore.
Pode conter um valor, um ponteiro para o
filho direito e outro para o esquerdo;
RAIZ (root): o nó principal, de onde
todos os outros se derivam.
 
FILHOS: são os nós que vêm imediatamente
abaixo de outro nó. Cada nó pode ter até
2 filhos. 
FOLHA: é um nó sem filhos. 
Árvore Binária
SUBÁRVORE: é uma árvore formada por um
nó e todos os seus descendentes (seus
filhos e “netos”);
ALTURA: medida pelo número de arestas
(ou conexões) do caminho mais longo da
raiz até uma folha. 
Neste exemplo, o nó 8 é a raiz, 3 e 10 são seus
filhos, e 1, 6, 14 são descendentes de 3 e 10. Os
nós 1, 4, 7, 13 são folhas, pois não têm filhos.
Árvore Binária
AGREGADO HETEROGÊNEO: chamado também de
REGISTRO (Record) ou ESTRUTURA (Structure),
é capaz de armazenar objetos de dados de
tipos diferentes, acessando-os através do
mesmo identificador e distinguindo-os a
través de um seletor. 
Usado para representar o NÓ de uma árvore. 
A árvore é representada por uma referência para a sua
raiz, ponteiro para a raiz, que, recursivamente, aponta
para as raízes das subárvores esquerda e direita. 
Ponteiro para a raiz da árvore: 
Árvore Binária
ÁRVORE VAZIA: representada quando o ponteiro
raiz aponta para o endereço 0 (zero). Assim,
para inicializar uma árvore vazia, basta
colocar o ponteiro raiz como NULO. 
Na figura abaixo, o nó raiz da árvore é armazenado no
endereço $100, que contém um agregado heterogêneo com a 
chave 10 e dois ponteiros $150 e $70, respectivamente,
para o endereço das subárvores esquerda e direita da
raiz. 
Árvore Binária
PERCURSO: processo de visitar todos os nós
da árvore seguindo determinada ordem.
Visitar é o mesmo que realizar uma operação
(NÃO é acessar o conteúdo armazenado em um
elemento).
TIPOS DE PERCURSO:
Pré-ordem: raiz -> esquerda -> direita
Em ordem: esquerda -> raiz -> direita
Pós-ordem: esquerda -> direita -> raiz
***OBS: a visita mais simples que podemos
definir é a IMPRESSÃO do rótulo da chave
armazenado no nó visitado. 
Árvore Binária de Busca
É uma estrutura de dados em que cada nó tem,
NO MÁXIMO, 2 filhos. 
REGRAS: 
valor de cada nó à esquerda valor do nó
raiz/referência. 
 
Repare que, se pegarmos o nó 80, perceberemos que o nó
à sua esquerda vale 60 (menor que 80) e o nó à sua
direita vale 90 (maior que 80). O mesmo é válido para
qualquer nó que tomarmos como referência.
ALGORITMO DE BUSCA: É usado nas operações de
inserção e remoção de nós em árvores
binárias de busca. 
Sendo X a chave que queremos encontrar, o
algoritmo compara X com a raiz, para ver se
ele está lá. Caso X não esteja na raiz, o
algoritmo parará de executar. 
Se X o algoritmo é executado na
subárvore esquerda. 
Se X > RAIZ -> o algoritmo é executado na
subárvore direita. 
Árvore Binária de Busca
EXEMPLO 1:
Árvore Binária de Busca
Se buscarmos a chave 80 na árvore acima, o algoritmo
irá retornar:
1) A referência para o nó com a chave 80;
II) A referência para o nó de chave 40, que é o pai do
nó que contém a chave 80;
III) O Boolean TRUE, indicando que a chave que buscamos
foi encontrada. 
 
EXEMPLO 1I:
Árvore Binária de Busca
Se buscarmos a chave 25 na árvore acima, o algoritmo
irá retornar:
1) A referência para o nó com a chave 30;
II) A referência para o nó de chave 20, que é o pai do
nó que contém a chave 30;
III) O Boolean FALSE, indicando que a chave que
buscamos NÃO foi encontrada. 
 
EXEMPLO 1II:
Árvore Binária de Busca
Se buscarmos uma chave que está na raiz, o algoritmo
irá retornar:
1) A referência para o nó raiz;
II) NULO na referência para o pai (que o nó raiz não
tem);
III) O Boolean TRUE, indicando que a chave que buscamos 
foi encontrada. 
 
EXEMPLO 1V:
Árvore Binária de Busca
Se buscarmos uma chave em uma árvore vazia, o algoritmo
irá retornar:
1) NULO para o nó que contém a chave;
II) NULO na referência para o pai do nó que contém a
chave;
III) O Boolean FALSE, indicando que a chave que
buscamos NÃO foi encontrada. 
 
ATENÇÃO: a função “Busca” é recursiva, então, na
primeira ativação, temos: raiz = endereço; pai =
NULO; encontrado = FALSE. 
Para determinarmos a complexidade de busca
de uma árvore binária de busca, devemos
determinar qual a árvore de busca de maior
altura. 
 
Complexidade de uma árvore binária de busca
= O(n) -> no pior caso (sendo n o número de
nós). 
Análise de complexidade
A inserção de uma nova chave em uma árvore
binária de busca ocorre SEMPRE em um novo nó
posicionado como uma nova folha da árvore.
Como NÃO é permitido CHAVE DUPLICADA, a
busca pela chave que desejamos inserir na
árvore deverá, obrigatoriamente, falhar e
retornar como resultado o nó que será pai do
novo nó inserido na árvore. 
***Inserção de nó em árvore vazia -> novo(a)
nó/chave = nó raiz. 
Inserção de nós
Considere a árvore binária de busca abaixo:
Inserção de nós
Vamos inserir um nó com chave “45” nela, seguindo os
passos a seguir:
I - Começando pela raiz (50), como 45 é menor que 50,
iremos para o nó da esquerda (30). 
II - No nó da esquerda (30), como 45 é maior que 30,
iremos para o nó da direita (40). 
III - No nó da direita (40), como 45 é maior que 40, o
nó 45 será inserido à direita de 40. 
A remoção pode ocorrer de 3 maneiras:
Remoção de uma folha na árvore binária
de busca;
Remoção de um nó interno com 1 filho;
Remoção de um nó interno com 2 filhos.
 
Remoção de nós
Considere a árvore binária de busca abaixo:
Remoçãode nós
Vamos remover o nó folha com chave “20” seguindo os
passos a seguir:
I - Localize o nó a ser removido (20). Começando pela
raiz (50), como 20 é menor que 50, iremos para o nó da
esquerda (30). No nó da esquerda (30), como 20 é menor
que 30, vá para a esquerda novamente (20). 
II - Confirme que o nó é uma folha (não tem filhos). 
III - Como o nó 20 não tem filhos (é uma folha), ele
pode ser removido diretamente da árvore. O ponteiro do
pai de 20 (nó 30), que apontava para ele, é
simplesmente ajustado para NULL, removendo o nó 20 da
árvore. 
Remoção de nós
Vamos remover o nó com 1 filho de chave “30” seguindo
os passos a seguir:
I - Localize o nó a ser removido (30). Começando pela
raiz (50), como 30 é menor que 50, iremos para o nó da
esquerda (30). 
II - Confirme que o nó 30 tem só 1 filho (que é o nó 40
à direita). 
III - Substitua o nó (30) pelo seu único filho (40).
Ajuste o ponteiro do pai de 30 (nó 50) apontando-o para
o nó 40. O nó 30 será removido e o nó 40 o substituirá. 
Remoção de nós
Vamos remover o nó com 2 filhos de chave “50” seguindo
os passos a seguir:
I - Localize o nó a ser removido (50 - o nó raiz). 
II - Encontrar o sucessor ou antecessor. Para
substituir o nó 50, pegaremos o seu sucessor, neste
caso, o menor valor da subárvore direita. O menor valor
na subárvore direita é o nó 60, à esquerda de 70. 
III - Substitua o nó (50) pelo valor do seu sucessor
(60). Não se esqueça de remover o nó original 60. 
Árvore Binária Completa
É uma estrutura de dados na qual:
Todos os nós têm 2 filhos (EXCETO no
último nível);
No último nível, os nós podem NÃO estar
completos, mas estão o mais à esquerda
possível. 
 
No exemplo acima: 
Nível 1 -> Nó raiz (nó 1)
Nível II -> Nós 2 e 3 (filhos do nó raiz)
Nível III -> Nós 4, 5 e 6 (filhos dos nós 2 e 3) 
***OBS: NÃO existe árvore binária com n nós cuja
altura seja inferior a 1 + [log n]. 
Árvore Balanceada
É uma árvore binária em que a altura das
subárvores (direita e esquerda), a partir de
qualquer nó, apresenta como valor da
diferença, no máximo, 1. Seu objetivo é
otimizar as operações de busca, inserção e
remoção de nós, mantendo-as eficientes
(próximas de O log n, no pior caso).
EXEMPLOS: 
Árvore AVL;
Árvore Rubro-Negra(Red-Black Tree). 
***OBS: TODA árvore binária de busca
balanceada tem altura proporcional a log n.
Assim, a complexidade, sendo proporcional à
altura, será de O(log n). 
 
Para saber se uma árvore é balanceada ou
não, é preciso:
1) Calcular a altura da subárvore esquerda e
da subárvore direita de cada nó;
II) Verificar a diferença de altura entre as
subárvores. Se a diferença for = 1, a árvore
é balanceada. 
EXEMPLO: 
 
É balanceada ou não?
Identificar o Nó raiz -> Nó 1
Altura da subárvore esquerda (começa a
partir do Nó 2) -> do Nó 2 até os nós 4
OU 5 = Altura I; 
Altura da subárvore direita (começa a
partir do Nó 3) -> do Nó 3 até os nós 6
E 7 = Altura = 2;
Altura da subárvore esquerda - Altura da
subárvore direita = I (árvore
balanceada) 
 
 
É balanceada ou não?
Árvore Zig-Zag
É uma árvore binária de busca em que os nós
alternam entre ter um único filho à esquerda
e um único filho à direita. Tem o PIOR
desempenho possível, uma vez que a
complexidade da busca, além da inserção e
remoção, é de O(n), não sendo possível
construir uma árvore binária de busca maior
do que n. É um exemplo de árvore
DESBALANCEADA. 
 
O algoritmo DSW (Day-Stout-Warren) é uma
técnica utilizada para balancear árvores
binárias de busca. Pode ser dividido em 2
fases:
I - Transformar a árvore em uma “espinha”
(lista encadeada);
II - Reconstruir a árvore balanceada a
partir da espinha. 
Vamos tomar como exemplo a árvore
desbalanceada abaixo:
Algoritmo DSW
Algoritmo DSW
FASE 1: transformar a árvore em uma
“espinha” (lista encadeada), fazendo
rotações para a direita.
Algoritmo DSW
FASE 1I: fazer rotações para a esquerda para
reconstruir a árvore balanceada.
Árvore AVL
É um tipo de árvore binária de busca
balanceada em que a diferença de altura
(fator de balanceamento) entre as subárvores
esquerda e direita (a partir de qualquer nó)
é de NO MÁXIMO 1 (ou seja, pode ser menor ou
igual a 1). 
O balanceamento automático é feito através
de rotações, após inserir ou remover nós,
garantindo que a árvore mantenha a altura
mínima possível (próxima de O log n, em que
n = número de nós). 
 
FB = Altura esquerda - Altura direita 
FB = -1, 0 ou 1 -> árvore balanceada
***OBS: AVL = Adelson-Velsky e Landis, os
autores desse tipo de árvore.
Inserção em Árvores AVL
Ocorre da seguinte maneira:
Inserir um nó como se faz em uma árvore
binária de busca, comparando o valor do
nó a ser inserido com o nó atual, e indo
para a esquerda ou para a direita;
Após a inserção, o fator de
balanceamento de cada nó ancestral em
relação ao nó inserido é atualizado.
Se o fator de balanceamento de algum nó
for maior que 1 ou menor que -1, a
árvore está desbalanceada, o que vai
demandar uma rotação (ou sequência de
rotações) para corrigir isso. 
Remoção em Árvores AVL
Ocorre da seguinte maneira:
Remover um nó como se faz em uma árvore
binária de busca;
Após a remoção, o fator de balanceamento
de cada nó ancestral em relação ao nó
inserido é atualizado.
Se o fator de balanceamento de algum nó
for maior que 1 ou menor que -1, a
árvore está desbalanceada, o que vai
demandar uma rotação (ou sequência de
rotações) para corrigir isso. 
***OBS: quando é necessário aplicar uma
rotação para preservar a propriedade AVL,
esta rotação deve ser aplicada no nó de
menor nível que se encontre desregulado. 
Grafos são estruturas matemáticas usadas
para modelar relações entre objetos. São
compostos por:
Vértices (ou Nós): representam os
objetos.
Arestas: conectam os vértices e indicam
a relação entre eles. 
Um grafo é representado por um par ordenado
de conjuntos disjuntos (V,E), sendo V ->
conjunto arbitrário de vértices e E -> o
conjunto não ordenado de arestas. 
GRAFOS
GRAFO DIRECIONADO (DÍGRAFO): as arestas têm
uma direção, ou seja, a relação é
unidirecional. 
GRAFO NÃO DIRECIONADO: as arestas não
possuem uma direção, isto é, a relação é
bidirecional. 
GRAFO PONDERADO: aqui, as arestas têm um
peso ou custo associado (peso/custo = um
tipo de valor, como distância, tempo etc.). 
GRAFO NÃO PONDERADO: as arestas não têm
peso. 
GRAFOS
Vamos criar um grafo = G(V,E) para
interligar os estados da região sudeste do
Brasil: 
V = {ES, MG, SP, RJ} -> vértices são os
estados do sudeste
E = {(MG, SP), (RJ, SP), (MG, ES), (RJ, MG), 
(RJ, ES)} -> arestas representam a ligação
entre os estados (se os estados têm uma
fronteira geográfica entre si) 
Exemplo de Grafo
EXTREMIDADE: representa os vértices conectados
por uma aresta. 
VÉRTICES ADJACENTES: dois vértices são
adjacentes quando estão conectados por uma
aresta. São vértices “vizinhos”.
 
LAÇO: é uma aresta que conecta um vértice a
ele mesmo.
ARESTAS PARALELAS: são arestas que conectam o
mesmo par de vértices (sejam eles direcionados
ou não). 
Conceitos em Grafos
GRAFO SIMPLES: grafo em que cada par de
vértices se conecta por apenas uma aresta (NÃO
há laços nem arestas paralelas). 
GRAFO CONEXO: é quando há um caminho entre
qualquer par de vértices. 
GRAU DO VÉRTICE: é representado pelo número de
arestas que estão conectadas a determinado
vértice. 
Conceitos em Grafos
Na figura ao lado, o nó A
possui grau do vértice = 2,
pois tem ligação com os nós C
e B.
Soma dos graus do vértice = 2 .(nº de arestas) 
Representação de Grafo
 No grafo acima, por exemplo, temos 5 arestas. Assim:
 Soma dos graus do vértice = 2 . 5 = 10
Ao se remover um vértice, também retiramos
todas as arestas que têm o vértice como
extremidade. No exemplo abaixo, removeremos o
vértice (nó) E: 
Remoção de Vértices
Também é possível removeruma ARESTA (a e5):
GRAFO COMPLETO: este grafo contém arestas que
ligam todos os nós. 
GRAFO COMPLEMENTAR: considerando-se o grafo G,
um grafo complementar de G possui os mesmos
vértices de G, mas suas arestas possuem
conexões que opostas às de G (ou seja, se dois
vértices se conectam em G, em G’ eles não
estarão conectados).
 
GRAFO NULO/VAZIO: é um grafos que possui
APENAS vértices (NÃO tem arestas).
GRAFO CONEXO REGULAR: grafo em que todos os
vértices têm o mesmo grau e estão conectados
de alguma forma. 
Tipos de Grafos
GRAFO DIRECIONADO: também chamado de DÍGRAFO,
é um grafo em que as arestas têm uma direção
(as conexões entre os vértices são
unidirecionais). 
GRAFO SUBJACENTE: um grafo subjacente de um
grafo direcionado pode ser obtido
transformando-se um grafo direcionado em um
grafo não direcionado (ou seja, mantendo os
vértices e conexões, mas ignorando as direções
das arestas).
Tipos de Grafos
MATRIZ: modelo matemático que serve para
representar grafos, utilizando tabelas com linhas
e colunas. 
**MATRIZ DE ADJACÊNCIA: é uma forma de representar
um grafo, na qual as linhas e colunas da matriz
correspondem aos vértices do grafo.
 
Complexidade = O(n²) 
Matriz de um Grafo
**MATRIZ DE INCIDÊNCIA: é uma forma de representar
um grafo, na qual:
LINHAS -> Vértices;
COLUNAS -> Arestas
 
Complexidade = O(nm)
Matriz de um Grafo
Há 2 técnicas de BUSCA EM GRAFOS:
 
1)BUSCA EM PROFUNDIDADE (DFS - DEPTH FIRST
SEARCH): é um algoritmo que explora o grafo indo o
mais fundo possível em cada ramificação, antes de
retroceder e explorar outros caminhos.
PASSO A PASSO:
-> Começa com um vértice inicial e segue um
caminho até o vértice mais profundo possível,
visitando os vértices de forma recursiva ou
utilizando uma PILHA.
-> Se atinge um vértice sem mais vizinhos não
visitados, retrocede até o vértice anterior e
continua a busca por outro caminho não explorado.
-> O processo continua até que todos os vértices
conectados ao vértice inicial sejam visitados. 
Algoritmos de Busca
EXEMPLO BUSCA EM PROFUNDIDADE
Ordem de busca:
Algoritmos de Busca
Há 2 técnicas de BUSCA EM GRAFOS:
 
1I)BUSCA EM LARGURA (BFS - BREADTH FIRST SEARCH):
é um algoritmo que explora o grafo visitando
primeiro os vizinhos mais próximos do vértice
inicial e, depois, os mais distantes.
PASSO A PASSO:
-> Começa com um vértice inicial e visita todos os
seus vizinhos diretos, antes de ir para os
vizinhos dos vizinhos, e assim por diante.
-> Utiliza uma FILA para controlar a ordem de
visita dos vértices (quando um vértice é visitado,
seus vizinhos são postos na fila para serem
processados posteriormente).
-> O processo continua até que todos os vértices
conectados ao vértice inicial sejam visitados. 
Algoritmos de Busca
EXEMPLO BUSCA EM LARGURA
Ordem de busca:
Algoritmos de Busca
COMPARANDO...
Algoritmos de Busca
CAMINHO -> é uma sequência de vértices em que cada
par de vértices consecutivos está conectado por
uma aresta. 
Pode ser:
SIMPLES: NÃO repete vértices;
FECHADO: O ponto inicial e o ponto final são o
mesmo vértice, formando um ciclo. 
**CAMINHO MÍNIMO: consiste no menor caminho entre
dois nós. Pode ser medido pelo número de arestas
ou pelo peso delas. 
Caminho
Utilizado para encontrar o CAMINHO MÍNIMO em
grafos ponderados (ou seja, nos quais as arestas
têm pesos positivos). 
Algoritmo de Dijkstra 
O problema a seguir visa determinar qual o menor
caminho de uma viagem, partindo de e voltando a um
mesmo ponto: 
Problema do Caixeiro
Veremos alguns algoritmos para resolução do
problema acima.
Lista todos os circuitos possíveis;1.
Calcula o custo total de cada circuito;2.
Escolhe um circuito com custo total mínimo.3.
O menor caminho (com custo total de R$676,00) para
o problema anterior seria:
A -> E -> C -> B -> D -> A
Algoritmo da Força Bruta
Seleciona um ponto de partida;1.
Das arestas adjacentes, escolhe a de menor
peso, partindo para o vértice correspondente;
2.
Continua a construir o circuito, indo sempre
para o vizinho mais próximo;
3.
Regressando ao último vértice, volta para
casa. 
4.
O menor caminho (com custo total de R$773,00) para
o problema anterior seria:
A -> C -> E -> D -> B -> A
Algoritmo do Vizinho