Análise e Projeto de Algoritmos

Prévia do material em texto

Ana´lise e Projeto de Algoritmos
Prof. Dr. Jesmmer Alves∗
Instituto Federal Goiano Campus Morrinhos
Curso Bacharelado em Cieˆncia da Computac¸a˜o
∗
jesmmer.alves@ifgoiano.edu.br
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 1 / 47
Agenda
1 Introduc¸a˜o
2 Primeiros Passos
3 Ana´lise de um Algoritmo
Busca Sequencial e Busca Bina´ria
Insertion Sort
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 2 / 47
Introduc¸a˜o - Disciplina
Ana´lise e Projeto de Algoritmos - 73.33h
Medidas de Complexidade, Ana´lise Assinto´tica de Limites de Complex-
idade, Te´cnicas de Prova de Cotas Inferiores. Notac¸a˜o Big O, Little o,
Omega e Theta. Medidas Emp´ıricas de Performance. O Uso de Relac¸o˜es
de Recorreˆncia para Ana´lise de Algoritmos Recursivos. Ana´lise de Al-
goritmos Iterativos e Recursivos. Classes de Problemas P, NP, NP-
Completo e NP-Dif´ıcil.
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 3 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Algoritmos 1
Um algoritmo e´ qualquer procedimento computacional bem definido
que recebe um valor, ou conjunto de valores, como entrada e produz
um valor, ou conjunto de valores, como sa´ıda.
Algoritmos 2
Um algoritmo e´ uma sequeˆncia computacional de passos que
transforma uma entrada em uma sa´ıda.
Algoritmos 3
Um algoritmo e´ uma ferramenta para resolver problemas
computacionais bem definidos.
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 4 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Problemas
Tipos de Problemas
Bem definidos
Mal definidos
Me´todos para resolver problemas
Tentativa e erro
Algoritmo (determin´ıstico)
Heur´ıstica (na˜o determin´ıstico)
Tomada de decisa˜o (viabilidade, representatividade)
Tendeˆncias (confianc¸a, crenc¸a, efeito de enquadramento)
Problemas Dif´ıceis
NP, NP-Completo, NP-Dif´ıcil
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 5 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Algoritmos
Dados de entrada e sa´ıda
Entrada: xa1, a2, ¨ ¨ ¨ , any.
Sa´ıda: xa11, a12, ¨ ¨ ¨ , a1ny tal que: a11 ď a12 ď ¨ ¨ ¨ ,ď a1n.
Instaˆncia de um problema
x31, 41, 59, 26, 41, 58y
Algoritmo correto
O algoritmo pa´ra e apresenta a soluc¸a˜o correta
Algoritmo incorreto?
Finitude
Corretude
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 6 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Eficieˆncia de um Algoritmo
Um olhar no porvir
O qua˜o eficiente esta´ meu algoritmo?
espac¸o, tempo
Como podemos analisar um algoritmo para prever o montante de
tempo necessa´rio?
Como podemos relacionar ac¸o˜es/escolhas com eficieˆncia?
Por que devemos preocupar com isto?
Precisamos vender :)
Computadores esta˜o mais ra´pidos, mas os problemas esta˜o
maiores
Em 2014, Google disponibilizou 30,000,000,000,000 pa´ginas na
web, aproximadamente 100,000,000 GB
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 7 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
1 Medir com um timer
2 Contar o nu´mero de operac¸o˜es
3 Noc¸a˜o abstrata da ordem de crescimento
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 8 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
1 Medir com um timer
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 9 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
1 Medir com um timer
o tempo varia entre algoritmos
o tempo varia entre implementac¸o˜es
o tempo varia entre computadores
dif´ıcil determinar para pequenas entradas
2 Contar o nu´mero de operac¸o˜es
3 Noc¸a˜o abstrata da ordem de crescimento
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 10 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
2 Contar o nu´mero de operac¸o˜es
Assuma passos com tempo constante
operac¸o˜es matema´ticas; comparac¸o˜es; atribuic¸o˜es; acessar valor de
uma varia´vel, etc.
Identifique o nu´mero de operac¸o˜es com relac¸a˜o ao tamanho da
entrada n
void impares( int n ){
 int i = 1;
 while (i <= n){
 if (i % 2 != 0)
 cout << i << " ";
 i++;
 }
 cout << "Fim";
}
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 11 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
2 Contar o nu´mero de operac¸o˜es
Assuma passos com tempo constante
operac¸o˜es matema´ticas; comparac¸o˜es; atribuic¸o˜es; acessar valor de
uma varia´vel, etc.
Identifique o nu´mero de operac¸o˜es com relac¸a˜o ao tamanho da
entrada n
void impares( int n ){
 int i = 1; 1 op.
 while (i <= n){ n +1 op.
 if (i % 2 != 0) 2 op.
 cout << i << " "; 1 op.
 i++; 1 op.
 }
 cout << "Fim"; 1 op. 
} n + 7 op.
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 12 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
1 Medir com um timer
2 Contar o nu´mero de operac¸o˜es
contagem depende do algoritmo
contagem depende da implementac¸a˜o
contagem na˜o depende do computadores
quais operac¸o˜es contar
contagem varia para diferentes entradas e podemos calcular a
relac¸a˜o contagem ˆ entrada
3 Noc¸a˜o abstrata da ordem de crescimento
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 13 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
3 Noc¸a˜o abstrata da ordem de crescimento
considere entradas muito grandes
operac¸o˜es ba´sicas na˜o sa˜o importantes
relacione o tempo com o tamanho da entrada
expressar eficieˆncia em termos do tamanho da entrada
void impares( int n ){
 int i = 1;
 while (i <= n){
 if (i % 2 != 0)
 cout << i << " ";
 i++;
 }
 cout << "Fim";
}
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 14 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
3 Noc¸a˜o abstrata da ordem de crescimento
considere entradas muito grandes
operac¸o˜es ba´sicas na˜o sa˜o importantes
relacione o tempo com o tamanho da entrada
expressar eficieˆncia em termos do tamanho da entrada
void impares( int n ){
 int i = 1; 1 op.
 while (i <= n){ n +1 op.
 if (i % 2 != 0) 2 op.
 cout << i << " "; 1 op.
 i++; 1 op.
 }
 cout << "Fim"; 1 op . 
} n + 7 op. (custo n)
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 15 / 47
Introduc¸a˜o - Definic¸o˜es Ba´sicas
Como avaliar a eficieˆncia de um Algoritmo?
3 Noc¸a˜o abstrata da ordem de crescimento
considere entradas muito grandes
operac¸o˜es ba´sicas na˜o sa˜o importantes
relacione o tempo com o tamanho da entrada
expressar eficieˆncia em termos do tamanho da entrada
void poli ( int n ){
 int i = 1; -
 while (i <= n){ n op.
 for (j = 1; j <= n; j++){ n op. 
 cout << i + j; -
 }
 i++;
 } - 
} n2 op. (custo n2 )
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 16 / 47
Agenda
1 Introduc¸a˜o
2 Primeiros Passos
3 Ana´lise de um Algoritmo
Busca Sequencial e Busca Bina´ria
Insertion Sort
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 17 / 47
Primeiros Passos
Invariantes de Lac¸o
Demostrar que uma afirmativa e´ verdadeira no in´ıcio, cada vez que
acontecer uma iterac¸a˜o de lac¸o e quando o lac¸o terminar.
Passos em uma invariante de lac¸o
Inicializac¸a˜o: e´ verdadeira antes da primeira iterac¸a˜o do lac¸o;
Manutenc¸a˜o: se e´ verdadeira antes da iterac¸a˜o do lac¸o,
permanecera´ verdadeira antes da pro´xima iterac¸a˜o;
Terminac¸a˜o: o lac¸o termina e, quando termina, a invariante do
lac¸o, juntamente com a raza˜o do te´rmino do lac¸o, nos da´ uma
propriedade u´til.
Prof.Dr. Jesmmer Alves APA Julho 23, 2019 18 / 47
Primeiros Passos
Sugesto˜es para definir e mostrar o Invariante de Lac¸o
Na˜o existe uma resposta simples
Entenda exatamente o que esta´ sendo feito
Escreva os passos dentro do corpo do lac¸o
Certifique que o invariante de lac¸o e´ u´til
O lac¸o resolve algum problema?
O invariante de lac¸o deve concluir que o problema a ser resolvido
no lac¸o foi resolvido
Mantenha o invariante de lac¸o o mais simples poss´ıvel (isto e´ uma
arte!)
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 19 / 47
Primeiros Passos
Invariantes de Lac¸o - Exemplo Trivial
Invariante: o lac¸o escreve todos os elementos de um arranjo
Inicializac¸a˜o: o lac¸o na˜o acessou nenhum elemento do arranjo A
e na˜o escreveu nenhum elemento, portanto o invariante e´
verdadeiro.
Entrada: inteiro na˜o-negativo n; arranjo A
Sa´ıda: escrever os elementos do arranho A
i “ 1;
enquanto i ď n fac¸a
Escreva Aris;
i “ i` 1;
fim
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 20 / 47
Primeiros Passos
Invariantes de Lac¸o - Exemplo Trivial
Invariante: o lac¸o escreve todos os elementos de um arranjo
Manutenc¸a˜o: a cada iterac¸a˜o no lac¸o, e´ escrito um elemento do
arranjo A de acordo com a varia´vel i. Desce que i comec¸a na
primeira posic¸a˜o do arranjo e e´ incrementado em 1 a cada nova
iterac¸a˜o, o invariante e´ verdadeiro.
Entrada: inteiro na˜o-negativo n; arranjo A
Sa´ıda: escrever os elementos do arranho A
i “ 1;
enquanto i ď n fac¸a
Escreva Aris;
i “ i` 1;
fim
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 21 / 47
Primeiros Passos
Invariantes de Lac¸o - Exemplo Trivial
Invariante: o lac¸o escreve todos os elementos de um arranjo
Terminac¸a˜o: apo´s terminar o lac¸o, i “ n, e todos os n elementos
do arranjo A foram escritos.
Entrada: inteiro na˜o-negativo n; arranjo A
Sa´ıda: escrever os elementos do arranho A
i “ 1;
enquanto i ď n fac¸a
Escreva Aris;
i “ i` 1;
fim
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 22 / 47
Primeiros Passos
Invariantes de Lac¸o - Soma de Elementos
Invariante: Soma “ 1` 2` ¨ ¨ ¨ ` pi´ 1q
Inicializac¸a˜o: o invariante de lac¸o e´ verdadeiro desde que
Soma “ 0 e i “ 1 neste ponto.
Entrada: inteiro na˜o-negativo n
Sa´ıda: a soma 1` 2` ¨ ¨ ¨ ` n
Soma “ 0;
i “ 1;
enquanto i ď n fac¸a
Soma “ Soma` i;
i “ i` 1;
fim
Retorne Soma;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 23 / 47
Primeiros Passos
Invariantes de Lac¸o - Soma de Elementos
Invariante: Soma “ 1` 2` ¨ ¨ ¨ ` pi´ 1q
Manutenc¸a˜o: assumindo que o invariante e´ verdadeiro antes da
i-e´sima interac¸a˜o, sera´ verdadeiro tambe´m depois desta interac¸a˜o
desde que o lac¸o adiciona i a Soma e incremente i em um.
Entrada: inteiro na˜o-negativo n
Sa´ıda: a soma 1` 2` ¨ ¨ ¨ ` n
Soma “ 0;
i “ 1;
enquanto i ď n fac¸a
//Invariante: Soma “ 1` 2` ¨ ¨ ¨ ` pi´ 1q;
Soma “ Soma` i;
i “ i` 1;
fim
Retorne Soma;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 24 / 47
Primeiros Passos
Invariantes de Lac¸o - Soma de Elementos
Invariante: Soma “ 1` 2` ¨ ¨ ¨ ` pi´ 1q
Terminac¸a˜o: quando o lac¸o terminar, o invariante define que
Soma “ 1` 2` ¨ ¨ ¨ ` n, exatamente o que e´ necessa´rio para que o
algoritmo esteja correto.
Entrada: inteiro na˜o-negativo n
Sa´ıda: a soma 1` 2` ¨ ¨ ¨ ` n
Soma “ 0;
i “ 1;
enquanto i ď n fac¸a
//Invariante: Soma “ 1` 2` ¨ ¨ ¨ ` pi´ 1q;
Soma “ Soma` i;
i “ i` 1;
fim
Retorne Soma;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 25 / 47
Primeiros Passos
Atividades
1 O seguinte problema esta´ bem definido? Porque?
Em func¸a˜o da crise financeira mundial tem crescido os investimentos na
poupanc¸a programada, pois e´ um investimento renta´vel e com baix´ıssimo
risco. Um professor de administrac¸a˜o financeira do IF Goiano deseja sim-
ular investimentos na poupanc¸a programada para ensinar seus alunos a
driblarem a crise. Fac¸a um programa que atenda a solicitac¸a˜o desse profes-
sor, considerando que a poupanc¸a rende 5% ao meˆs, sendo tempo e capital
programados pelo investidor com isenc¸a˜o total do imposto de renda.
2 Apresente um um algoritmo determin´ıstico e uma heur´ıstica.
3 Qual o propo´sito do invariante de lac¸o? Escreva um algoritmo para
mostrar o maior valor de um arranjo. Defina o invariante de lac¸o
para este algoritmo. Mostre que o invariante de lac¸o e´ verdadeiro
antes, apo´s cada iterac¸a˜o e no te´rmino do lac¸o.
4 Determine os custos e os invariantes de lac¸o para a busca sequencial
e para a busca bina´ria.
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 26 / 47
Agenda
1 Introduc¸a˜o
2 Primeiros Passos
3 Ana´lise de um Algoritmo
Busca Sequencial e Busca Bina´ria
Insertion Sort
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 27 / 47
Informac¸o˜es Ba´sicas
Ana´lise de um Algoritmo
Corretude:
invariante de lac¸o, induc¸a˜o, prova direta, contradic¸a˜o, etc.
Performance
Identificar recursos necessa´rios (memo´ria, hardware, tempo de
computac¸a˜o, etc.)
Identificar um algoritmo mais eficiente
Instruc¸o˜es executadas em sequeˆncia
Na˜o usamos caches ou memo´ria virtual
O tempo necessa´rio depende da entrada
Tamanho da entrada?
itens em um arranjo, bits, ve´rtices, . . .
Noc¸a˜o abstrata da ordem de crescimento
Tempo de execuc¸a˜o da i-e´sima linha ci.
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 28 / 47
Busca Sequencial e Busca Bina´ria
Invariante de Lac¸o - Busca Sequencial
Invariante de Lac¸o: antes de cada iterac¸a˜o do lac¸o, o subarranjo
Ar0 . . . i´ 1s consiste dos elementos que sa˜o diferentes de x.
Inicializac¸a˜o: inicialmente o subarranjo esta´ vazio, portanto o in-
variante e´ va´lido.
Entrada: arranjo A; nu´mero de elementos n; inteiro x.
Sa´ıda: ı´ndice do elemento x em A, ou ´1.
para pi “ 0; i ă n; i``q fac¸a
se pAris ““ xq enta˜o
retorne i;
fim
fim
retorne ´1;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 29 / 47
Busca Sequencial e Busca Bina´ria
Invariante de Lac¸o - Busca Sequencial
Invariante de Lac¸o: antes de cada iterac¸a˜o do lac¸o, o subarranjo
Ar0 . . . i´ 1s consiste dos elementos que sa˜o diferentes de x.
Manutenc¸a˜o: em cada iterac¸a˜o, se pAris ““ xq o lac¸o termina e o
resultado esta´ correto. Sena˜o segue para a pro´xima iterac¸a˜o. Neste
caso, sabe-se que Ar1 . . . i´1s na˜o conte´m x e verifica-se novamente
se Aris e´ diferente de x, portanto o invariante e´ va´lido.
Entrada: arranjo A; nu´mero de elementos n; inteiro x.
Sa´ıda: ı´ndice do elemento x em A, ou ´1.
para pi “ 0; i ă n; i``q fac¸a
se pAris ““ xq enta˜o
retorne i;
fim
fim
retorne ´1;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 30 / 47
Busca Sequencial e Busca Bina´ria
Invariante de Lac¸o - Busca Sequencial
Invariante de Lac¸o: antes de cada iterac¸a˜o do lac¸o, o subarranjo
Ar0 . . . i´ 1s consiste dos elementos que sa˜o diferentes de x.
Terminac¸a˜o: o lac¸o termina quando i “ n. Desde que i comec¸a em
0, e´ incrementado em 1 a cada iterac¸a˜o e i ě n, todos os elementos
em A foram verificados e x na˜o esta´ entre eles, retornando ´1.
Portanto o invariante e´ va´lido.
Entrada: arranjo A; nu´mero de elementos n; inteiro x.
Sa´ıda: ı´ndice do elemento x em A, ou ´1.
para pi “ 0; i ă n; i``q fac¸a
se pAris ““ xq enta˜o
retorne i;
fim
fim
retorne ´1;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 31 / 47
Busca Sequencial e Busca Bina´ria
Performance (Aproximado)- Busca Sequencial
Considere n grande
Desconsidere tempo/custo constante
Simplifique!
Entrada: A; n; x.
Sa´ıda: ı´ndice de x em A, ou ´1.
para pi “ 0; i ă n; i``q fac¸a
se pAris ““ xq enta˜o
retorne i;
fim
fim
retorne ´1;
n
´
´
´
´
´
n
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 32 / 47
Busca Sequencial e Busca Bina´ria
Invariante de Lac¸o - Busca Bina´ria
Invariante de Lac¸o: o arranjo esta´ ordenado; Se x esta´ contidono arranjo original, enta˜o x esta´ em Arms ou em Aresq . . .m ´ 1s
ou em Arm` 1 . . . dirs.
Inicializac¸a˜o: inicialmente o arranjo esta´ vazio, portanto o invari-
ante e´ va´lido.
Entrada: arranjo A; inteiro n; ı´ndices esq, dir; inteiro x.
Sa´ıda: ı´ndice do elemento x em A, ou ´1.
enquanto pesq ď dirq fac¸a
m “ esq ` pdir ´ esqq{2;
se pArms ““ xq enta˜o retorne m ;
se pArms ă xq enta˜o esq “ m` 1;
sena˜o dir “ m´ 1 ;
fim
retorne ´1;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 33 / 47
Busca Sequencial e Busca Bina´ria
Invariante de Lac¸o - Busca Bina´ria
Invariante de Lac¸o: o arranjo esta´ ordenado; Se x esta´ contido
no arranjo original, enta˜o x esta´ em Arms ou em Aresq . . .m ´ 1s
ou em Arm` 1 . . . dirs.
Manutenc¸a˜o: o lac¸o na˜o modifica a posic¸a˜o dos elementos, por-
tanto permanece ordenado; se Arms “ x, o algoritmo retorna o
ı´ndice de x corretamente; caso contra´rio, o algoritmo passa a con-
siderar o Aresq . . .m´ 1s ou Arm` 1 . . . dirs, ate´ encontrar x.
Entrada: arranjo A; inteiro n; ı´ndices esq, dir; inteiro x.
Sa´ıda: ı´ndice do elemento x em A, ou ´1.
enquanto pesq ď dirq fac¸a
m “ esq ` pdir ´ esqq{2;
se pArms ““ xq enta˜o retorne m ;
se pArms ă xq enta˜o esq “ m` 1;
sena˜o dir “ m´ 1 ;
fim
retorne ´1;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 34 / 47
Busca Sequencial e Busca Bina´ria
Invariante de Lac¸o - Busca Bina´ria
Invariante de Lac¸o: o arranjo esta´ ordenado; Se x esta´ contido
no arranjo original, enta˜o x esta´ em Arms ou em Aresq . . .m ´ 1s
ou em Arm` 1 . . . dirs.
Terminac¸a˜o: na u´ltima iterac¸a˜o do lac¸o esq “ direita “ m e
o arranjo permanece ordenado; se Arms “ x, enta˜o o algoritmo
retorna o ı´ndice de x corretamente; caso contra´rio, o arranjo original
na˜o conte´m x e o algoritmo retorna ´1.
Entrada: arranjo A; inteiro n; ı´ndices esq, dir; inteiro x.
Sa´ıda: ı´ndice do elemento x em A, ou ´1.
enquanto pesq ď dirq fac¸a
m “ esq ` pdir ´ esqq{2;
se pArms ““ xq enta˜o retorne m ;
se pArms ă xq enta˜o esq “ m` 1;
sena˜o dir “ m´ 1 ;
fim
retorne ´1;
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 35 / 47
Busca Sequencial e Busca Bina´ria
Performance (Aproximado)- Busca Bina´ria
Considere n grande
Desconsidere tempo/custo constante
Simplifique!
Entrada: A; n; esq, dir; x.
Sa´ıda: ı´ndice de x em A, ou ´1.
enquanto pesq ď dirq fac¸a
m “ esq ` pdir ´ esqq{2;
se pArms ““ xq enta˜o retorne m ;
se pArms ă xq enta˜o esq “ m` 1;
sena˜o dir “ m´ 1 ;
fim
retorne ´1;
tempo ă n
´
´
´
´
´
´
tempo ă n
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 36 / 47
Insertion Sort
Invariantes de Lac¸o - Insertion Sort
Invariante de Lac¸o: o subarranjo Ar1 . . . j ´ 1s esta´ ordenado.
Inicializac¸a˜o: j = 2 e o subarranjo Ar1 . . . j ´ 1s consiste de um
elemento, trivialmente Ar1 . . . j ´ 1s esta´ ordenado.
para j “ 2 ate´ comp(A) fac¸a
chave = Arjs;
i “ j ´ 1;
enquanto i ą 0 e Aris ą chave fac¸a
Ari` 1s “ Aris;
i “ i´ 1;
fim
Ari` 1s “ chave;
fim
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 37 / 47
Insertion Sort
Invariantes de Lac¸o - Insertion Sort
Invariante de Lac¸o: o subarranjo Ar1 . . . j ´ 1s esta´ ordenado.
Manutenc¸a˜o: no corpo do lac¸o for, o algoritmo move uma posic¸a˜o
dentro da sec¸a˜o ordenada (Arj´1s, Arj´2s, ¨ ¨ ¨Ar1s) ate´ encontrar a
posic¸a˜o correta para Arjs, e aumenta o tamanho da sec¸a˜o ordenada
em 1. Portanto, a cada nova iterac¸a˜o, Ar1 . . . j ´ 1s esta´ ordenado.
para j “ 2 ate´ comp(A) fac¸a
chave = Arjs;
i “ j ´ 1;
enquanto i ą 0 e Aris ą chave fac¸a
Ari` 1s “ Aris;
i “ i´ 1;
fim
Ari` 1s “ chave;
fim
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 38 / 47
Insertion Sort
Invariantes de Lac¸o - Insertion Sort
Terminac¸a˜o: o algoritmo pa´ra quando j ą comppAq, ou j “ n `
1. Neste momento, o subarranjo Ar1 . . . j ´ 1s conte´m todos os n
elementos do arranjo original ordenados.
para j “ 2 ate´ comp(A) fac¸a
chave = Arjs;
i “ j ´ 1;
enquanto i ą 0 e Aris ą chave fac¸a
Ari` 1s “ Aris;
i “ i´ 1;
fim
Ari` 1s “ chave;
fim
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 39 / 47
Insertion Sort
Performance (Aproximado)- Insertion Sort
Considere n grande
Desconsidere tempo/custo constante
Simplifique!
para j “ 2 ate´ comp(A) fac¸a
chave = Arjs;
i “ j ´ 1;
enquanto i ą 0 e Aris ą chave fac¸a
Ari` 1s “ Aris;
i “ i´ 1;
fim
Ari` 1s “ chave;
fim
n´ 1
´
´
n´ 1
´
´
´
´
´
tempo « n2
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 40 / 47
Insertion Sort
Ana´lise Detalhada - Abstrac¸o˜es e Ordem de Crescimento
1 Utilize a constante ci para representar custos de cada linha i
2 Expresse T pnq como anx ` bn` c, para constantes a, b, c e inteiro
x “ 0 . . . k, de acordo com o custo de cada linha i
3 T pnq e´ definida pelo termo com maior grau no polinoˆmio (ex.: an2)
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 41 / 47
Insertion Sort
Ana´lise Detalhada - Exemplo Busca Sequencial
1 Utilize a constante ci para representar custos de cada linha i
2 Expresse T pnq como anx ` bn` c, para constantes a, b, c e inteiro
x “ 0 . . . k, de acordo com o custo de cada linha i
3 T pnq e´ definida pelo termo com maior grau no polinoˆmio (ex.: an2)
Entrada: A; n; x.
Sa´ıda: ı´ndice de x em A, ou ´1.
para pi “ 0; i ă n; i``q fac¸a
se pAris ““ xq enta˜o
retorne i;
fim
fim
retorne ´1;
custo qtd
c1 n+1
c2 n
c3 n
c4 -
c5 -
c6 1
T pnq “ an` b
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 42 / 47
Insertion Sort
Ana´lise Detalhada - Insertion Sort (Melhor Caso)
1 Aris ď chave para todo j “ 2, 3, . . . , n (ordem crescente)
2 T pnq “ an´ b, para a, b constantes. Uma func¸a˜o linear em n
para j “ 2 ate´ comp(A) fac¸a
chave = Arjs;
i “ j ´ 1;
enquanto i ą 0 e Aris ą chave fac¸a
Ari` 1s “ Aris;
i “ i´ 1;
fim
Ari` 1s “ chave;
fim
custo qtd
c1 n
c2 n-1
c3 n-1
c4 n-1
c5 -
c6 -
c7 -
c8 n-1
c9 -
T pnq “ an´ b
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 43 / 47
Insertion Sort
Ana´lise Detalhada - Insertion Sort (Pior Caso)
1 Aris ą chave para todo j “ 2, 3, . . . , n (ordem decrescente)
2 T pnq “ an2 ` bn´ c. Uma func¸a˜o quadra´tica em n
para j “ 2 ate´ comp(A) fac¸a
chave = Arjs;
i “ j ´ 1;
enquanto i ą 0 e Aris ą chave fac¸a
Ari` 1s “ Aris;
i “ i´ 1;
fim
Ari` 1s “ chave;
fim
custo qtd
c1 n
c2 n-1
c3 n-1
c4
řn
j“2 tj
c5
řn
j“2ptj´1q
c6
řn
j“2ptj´1q
c7 -
c8 n-1
c9 -
T pnq “ c1n`c2pn´1q`c3pn´1q`c4
nÿ
j“2
tj`c5
nÿ
j“2
ptj´1q`c6
nÿ
j“2
ptj´1q`c8pn´1q
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 44 / 47
Insertion Sort
Ana´lise Detalhada - Insertion Sort (Pior Caso)
1 Aris ą chave para todo j “ 2, 3, . . . , n (ordem decrescente)
2 T pnq “ an2 ` bn´ c. Uma func¸a˜o quadra´tica em n
T pnq “ c1n`c2pn´1q`c3pn´1q`c4
nÿ
j“2
tj`c5
nÿ
j“2
ptj´1q`c6
nÿ
j“2
ptj´1q`c8pn´1q
“ c1n`c2pn´1q`c3pn´1q`c4ˆ npn`1q
2
´ 1˙ `c5ˆ npn´1q
2
˙
`c6ˆ npn´1q
2
˙
`c8pn´1q
“
´c4
2
` c5
2
` c6
2
¯
n2`
´
c1 ` c2 ` c3 ` c4
2
´ c5
2
´ c6
2
` c8
¯
n´pc2`c3`c4`c8q
T pnq “ an2 ` bn´ c
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 45 / 47
Insertion Sort
Atividades
1 Fac¸a a ana´lise detalhada dos algoritmos Soma de Elementos, Busca
Sequencial e Busca Bina´ria considerando o melhor caso e o pior
caso.
2 Considere o Binary Insertion Sort: ordenac¸a˜o por inserc¸a˜o que e´
implementado com lista lincada e utiliza a busca bina´ria para de-
terminar a posic¸a˜o correta para inserir um elemento. Apresente o
invariante de lac¸o e T pnq considerando o melhor caso e o pior caso.
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 46 / 47
Bibliografia
VINU V. DAS: Princ´ıpios de Estruturas de Dados Usando C e C++, MIT Press,
(2006)
THOMAS H. et. al., Algoritmos - Teoria e Pra´tica,(1989)
TENENBAUM, A.M. et al, Estruturas de Dados usando C., Pearson, (2010)
GOODRICH, M. T. e TAMASSIA, R., Estruturas de Dados e Algoritmos em Java.,
Bookman, (2013)
Prof. Dr. Jesmmer Alves APA Julho 23, 2019 47 / 47
	Introdução
	Primeiros Passos
	Análise de um Algoritmo
	Busca Sequencial e Busca Binária
	Insertion Sort