Analise de algoritmosConceitos basicos
Prof. Flavio Rogerio Uber(UEM/DIN)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN)
Conteudo
Ordenacao por insercaoProva de corretudeAnalise do tempo de execucao
Ordenacao por intercalacaoProva de corretudeAnalise do tempo de execucao
Exercıcios
Referencias
Problema de ordenacao
EntradaUma sequencia de n numeros 〈a1, a2, . . . , an〉
SaıdaUma permutacao (reordenacao) 〈a′1, a′2, . . . , a′n〉 da sequencia deentrada tal que a′1 ≤ a′2 ≤ · · · ≤ a′n.
Como resolver o problema de ordenacao?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 3 / 24
Problema de ordenacao
EntradaUma sequencia de n numeros 〈a1, a2, . . . , an〉
SaıdaUma permutacao (reordenacao) 〈a′1, a′2, . . . , a′n〉 da sequencia deentrada tal que a′1 ≤ a′2 ≤ · · · ≤ a′n.
Como resolver o problema de ordenacao?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 3 / 24
Ordenacao por insercao
I Semelhante a maneira como muitas pessoas ordenam ascartas de um baralho
I Abordagem incremental: a cada iteracao a porcao do vetorordenada e incrementada
I Eficiente para ordenar um numero pequeno de elementos
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 4 / 24
Ordenacao por insercao
insertion-sort(A)1 for j = 2 to A.length2 chave = A[j]3 # insere A[j] na sequencia ordenada A[1..j-1]4 i = j - 15 while i > 0 and A[i] > chave6 A[i + 1] = A[i]7 i = i - 18 A[i + 1] = chave
Como saber se a ordenacao por insercao funcionacorretamente?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 5 / 24
Ordenacao por insercao
insertion-sort(A)1 for j = 2 to A.length2 chave = A[j]3 # insere A[j] na sequencia ordenada A[1..j-1]4 i = j - 15 while i > 0 and A[i] > chave6 A[i + 1] = A[i]7 i = i - 18 A[i + 1] = chave
Como saber se a ordenacao por insercao funcionacorretamente?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 5 / 24
Prova de corretude
I Usamos invariantes de laco para entender por que umalgoritmo e correto.
Inicializacao Ela e verdadeira antes da primeira iteracao do laco.Manutencao Se for verdadeira antes de uma iteracao do laco, ela
permanecera verdadeira antes da proxima iteracao.Termino Quando o laco termina, a invariante nos fornece uma
propriedade util para mostrar que o algoritmo e correto.
Invariante do laco principal do insertion-sort
No comeco de cada iteracao do laco for das linhas 1 a 8, osubarranjo A[1..j − 1] consiste nos elementos contidosoriginalmente em A[1..j − 1], mas em sequencia ordenadaVeja os detalhes nas paginas 13 e 14.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 6 / 24
Prova de corretude
I Usamos invariantes de laco para entender por que umalgoritmo e correto.
Inicializacao Ela e verdadeira antes da primeira iteracao do laco.
Manutencao Se for verdadeira antes de uma iteracao do laco, elapermanecera verdadeira antes da proxima iteracao.
Termino Quando o laco termina, a invariante nos fornece umapropriedade util para mostrar que o algoritmo e correto.
Invariante do laco principal do insertion-sort
No comeco de cada iteracao do laco for das linhas 1 a 8, osubarranjo A[1..j − 1] consiste nos elementos contidosoriginalmente em A[1..j − 1], mas em sequencia ordenadaVeja os detalhes nas paginas 13 e 14.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 6 / 24
Prova de corretude
I Usamos invariantes de laco para entender por que umalgoritmo e correto.
Inicializacao Ela e verdadeira antes da primeira iteracao do laco.Manutencao Se for verdadeira antes de uma iteracao do laco, ela
permanecera verdadeira antes da proxima iteracao.
Termino Quando o laco termina, a invariante nos fornece umapropriedade util para mostrar que o algoritmo e correto.
Invariante do laco principal do insertion-sort
No comeco de cada iteracao do laco for das linhas 1 a 8, osubarranjo A[1..j − 1] consiste nos elementos contidosoriginalmente em A[1..j − 1], mas em sequencia ordenadaVeja os detalhes nas paginas 13 e 14.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 6 / 24
Prova de corretude
I Usamos invariantes de laco para entender por que umalgoritmo e correto.
Inicializacao Ela e verdadeira antes da primeira iteracao do laco.Manutencao Se for verdadeira antes de uma iteracao do laco, ela
permanecera verdadeira antes da proxima iteracao.Termino Quando o laco termina, a invariante nos fornece uma
propriedade util para mostrar que o algoritmo e correto.
Invariante do laco principal do insertion-sort
No comeco de cada iteracao do laco for das linhas 1 a 8, osubarranjo A[1..j − 1] consiste nos elementos contidosoriginalmente em A[1..j − 1], mas em sequencia ordenadaVeja os detalhes nas paginas 13 e 14.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 6 / 24
Prova de corretude
I Usamos invariantes de laco para entender por que umalgoritmo e correto.
Inicializacao Ela e verdadeira antes da primeira iteracao do laco.Manutencao Se for verdadeira antes de uma iteracao do laco, ela
permanecera verdadeira antes da proxima iteracao.Termino Quando o laco termina, a invariante nos fornece uma
propriedade util para mostrar que o algoritmo e correto.
Invariante do laco principal do insertion-sort
No comeco de cada iteracao do laco for das linhas 1 a 8, osubarranjo A[1..j − 1] consiste nos elementos contidosoriginalmente em A[1..j − 1], mas em sequencia ordenadaVeja os detalhes nas paginas 13 e 14.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 6 / 24
Ordenacao por insercao
insertion-sort(A)1 for j = 2 to A.length2 chave = A[j]3 # insere A[j] na sequencia ordenada A[1..j-1]4 i = j - 15 while i > 0 and A[i] > chave6 A[i + 1] = A[i]7 i = i - 18 A[i + 1] = chave
Como saber se a ordenacao por insercao e eficiente?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 7 / 24
Ordenacao por insercao
insertion-sort(A)1 for j = 2 to A.length2 chave = A[j]3 # insere A[j] na sequencia ordenada A[1..j-1]4 i = j - 15 while i > 0 and A[i] > chave6 A[i + 1] = A[i]7 i = i - 18 A[i + 1] = chave
Como saber se a ordenacao por insercao e eficiente?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 7 / 24
Analise do tempo de execucao
Analisar um algoritmoSignifica prever os recursos que ele necessitara durante a suaexecucao.
I E preciso um modelo da tecnologia de implementacao quesera utilizada
I Maquina de Turing? Muito diferente dos computadores reaisI RAM (random-acess machine - maquina de acesso aleatorio)
I Caracterısticas da RAMI As instrucoes sao executadas uma apos a outraI Instrucoes aritmeticas, de movimentacao de dados e de
controleI Cada uma das instrucoes demora um tempo constanteI Nao considera a hierarquia de memoria
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 8 / 24
Analise do tempo de execucao
Analisar um algoritmoSignifica prever os recursos que ele necessitara durante a suaexecucao.
I E preciso um modelo da tecnologia de implementacao quesera utilizada
I Maquina de Turing? Muito diferente dos computadores reaisI RAM (random-acess machine - maquina de acesso aleatorio)
I Caracterısticas da RAMI As instrucoes sao executadas uma apos a outraI Instrucoes aritmeticas, de movimentacao de dados e de
controleI Cada uma das instrucoes demora um tempo constanteI Nao considera a hierarquia de memoria
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 8 / 24
Analise do tempo de execucao
Analisar um algoritmoSignifica prever os recursos que ele necessitara durante a suaexecucao.
I E preciso um modelo da tecnologia de implementacao quesera utilizada
I Maquina de Turing?
Muito diferente dos computadores reaisI RAM (random-acess machine - maquina de acesso aleatorio)
I Caracterısticas da RAMI As instrucoes sao executadas uma apos a outraI Instrucoes aritmeticas, de movimentacao de dados e de
controleI Cada uma das instrucoes demora um tempo constanteI Nao considera a hierarquia de memoria
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 8 / 24
Analise do tempo de execucao
Analisar um algoritmoSignifica prever os recursos que ele necessitara durante a suaexecucao.
I E preciso um modelo da tecnologia de implementacao quesera utilizada
I Maquina de Turing? Muito diferente dos computadores reais
I RAM (random-acess machine - maquina de acesso aleatorio)I Caracterısticas da RAM
I As instrucoes sao executadas uma apos a outraI Instrucoes aritmeticas, de movimentacao de dados e de
controleI Cada uma das instrucoes demora um tempo constanteI Nao considera a hierarquia de memoria
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 8 / 24
Analise do tempo de execucao
Analisar um algoritmoSignifica prever os recursos que ele necessitara durante a suaexecucao.
I E preciso um modelo da tecnologia de implementacao quesera utilizada
I Maquina de Turing? Muito diferente dos computadores reaisI RAM (random-acess machine - maquina de acesso aleatorio)
I Caracterısticas da RAMI As instrucoes sao executadas uma apos a outraI Instrucoes aritmeticas, de movimentacao de dados e de
controleI Cada uma das instrucoes demora um tempo constanteI Nao considera a hierarquia de memoria
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 8 / 24
Analise do tempo de execucao
Analisar um algoritmoSignifica prever os recursos que ele necessitara durante a suaexecucao.
I E preciso um modelo da tecnologia de implementacao quesera utilizada
I Maquina de Turing? Muito diferente dos computadores reaisI RAM (random-acess machine - maquina de acesso aleatorio)
I Caracterısticas da RAMI As instrucoes sao executadas uma apos a outraI Instrucoes aritmeticas, de movimentacao de dados e de
controleI Cada uma das instrucoes demora um tempo constanteI Nao considera a hierarquia de memoria
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 8 / 24
Analise do tempo de execucao
I O recurso que queremos prever para o insertion-sort e otempo
I O tempo de execucao de um algoritmo em uma determinadaentrada e o numero de operacoes primitivas executadas
I O tempo de execucao depende da quantidade de itens naentrada (tamanho da entrada)
I Vamos assumir que cada linha executada consome um perıodoconstante de tempo
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 9 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1
n
2 chave = A[j] c2
n − 1
3 # insere A[j] ... 0
n − 1
4 i = j - 1 c4
n − 1
5 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6
∑nj=2(tj − 1)
7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor jI Para calcular T (n), o tempo de execucao de insertion-sort, somamos os
produtos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2
n − 1
3 # insere A[j] ... 0
n − 1
4 i = j - 1 c4
n − 1
5 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6
∑nj=2(tj − 1)
7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor jI Para calcular T (n), o tempo de execucao de insertion-sort, somamos os
produtos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0
n − 1
4 i = j - 1 c4
n − 1
5 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6
∑nj=2(tj − 1)
7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor jI Para calcular T (n), o tempo de execucao de insertion-sort, somamos os
produtos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4
n − 1
5 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6
∑nj=2(tj − 1)
7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor jI Para calcular T (n), o tempo de execucao de insertion-sort, somamos os
produtos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4 n − 15 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6
∑nj=2(tj − 1)
7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor jI Para calcular T (n), o tempo de execucao de insertion-sort, somamos os
produtos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4 n − 15 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6
∑nj=2(tj − 1)
7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1
I tj e o numero de vezes que o teste do laco while da linha e executado para ovalor j
I Para calcular T (n), o tempo de execucao de insertion-sort, somamos osprodutos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4 n − 15 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6∑n
j=2(tj − 1)7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1
I tj e o numero de vezes que o teste do laco while da linha e executado para ovalor j
I Para calcular T (n), o tempo de execucao de insertion-sort, somamos osprodutos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4 n − 15 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6∑n
j=2(tj − 1)7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8
n − 1
I tj e o numero de vezes que o teste do laco while da linha e executado para ovalor j
I Para calcular T (n), o tempo de execucao de insertion-sort, somamos osprodutos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4 n − 15 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6∑n
j=2(tj − 1)7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8 n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor j
I Para calcular T (n), o tempo de execucao de insertion-sort, somamos osprodutos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucaoinsertion-sort(A) custo vezes1 for j = 2 to A.length c1 n2 chave = A[j] c2 n − 13 # insere A[j] ... 0 n − 14 i = j - 1 c4 n − 15 while i > 0 and A[i] > chave c5
∑nj=2 tj
6 A[i + 1] = A[i] c6∑n
j=2(tj − 1)7 i = i - 1 c7
∑nj=2(tj − 1)
8 A[i + 1] = chave c8 n − 1I tj e o numero de vezes que o teste do laco while da linha e executado para o
valor jI Para calcular T (n), o tempo de execucao de insertion-sort, somamos os
produtos das colunas custo e vezes, obtendo
T (n) =c1n + c2(n − 1) + c4(n − 1) + c5
n∑j=2
tj
+ c6
n∑j=2
(tj − 1) + c7
n∑j=2
(tj − 1) + c8(n − 1)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 10 / 24
Analise do tempo de execucao
I Mesmo para entradas do mesmo tamanho, o tempo deexecucao pode ser diferente (depende de tj)
I Como deve ser a entrada para o algoritmo executar com omenor numero de operacoes?
I Como deve ser a entrada para o algoritmo executar com omaior numero de operacoes?
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 11 / 24
Analise do tempo de execucao
I Melhor caso
I Ocorre quando o arranjo ja esta ordenadoI O teste A[i] > chave na linha 5 falha na primeira
comparacao quando i = j − 1I Portanto, tj = 1, para j = 2, 3, . . . , n, e o tempo de execucao
no melhor caso e
T (n) = c1n + c2(n − 1) + c4(n − 1) + c5(n − 1) + c8(n − 1)
= (c1 + c2 + c4 + c5 + c8)n − (c2 + c4 + c5 + c8)
I Esse tempo pode ser expresso como T (n) = an + b, paraconstantes a e b
I E uma funcao linear de n.I T (n) = Θ(n)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 12 / 24
Analise do tempo de execucao
I Melhor casoI Ocorre quando o arranjo ja esta ordenadoI O teste A[i] > chave na linha 5 falha na primeira
comparacao quando i = j − 1I Portanto, tj = 1, para j = 2, 3, . . . , n, e o tempo de execucao
no melhor caso e
T (n) = c1n + c2(n − 1) + c4(n − 1) + c5(n − 1) + c8(n − 1)
= (c1 + c2 + c4 + c5 + c8)n − (c2 + c4 + c5 + c8)
I Esse tempo pode ser expresso como T (n) = an + b, paraconstantes a e b
I E uma funcao linear de n.I T (n) = Θ(n)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 12 / 24
Analise do tempo de execucao
I Melhor casoI Ocorre quando o arranjo ja esta ordenadoI O teste A[i] > chave na linha 5 falha na primeira
comparacao quando i = j − 1I Portanto, tj = 1, para j = 2, 3, . . . , n, e o tempo de execucao
no melhor caso e
T (n) = c1n + c2(n − 1) + c4(n − 1) + c5(n − 1) + c8(n − 1)
= (c1 + c2 + c4 + c5 + c8)n − (c2 + c4 + c5 + c8)
I Esse tempo pode ser expresso como T (n) = an + b, paraconstantes a e b
I E uma funcao linear de n.I T (n) = Θ(n)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 12 / 24
Analise do tempo de execucao
I Pior caso
I Ocorre quando o arranjo esta em ordem inversaI Cada elemento A[j] deve sem comparado com os elementos do
subarranjo ordenado A[1..j − 1]I Portanto, tj = j , para j = 2, 3, . . . , n. Como
n∑j=2
j =n(n + 1)
2 − 1
en∑
j=2(j − 1) =
n(n − 1)
2
o tempo de execucao no pior caso e
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 13 / 24
Analise do tempo de execucao
I Pior casoI Ocorre quando o arranjo esta em ordem inversaI Cada elemento A[j] deve sem comparado com os elementos do
subarranjo ordenado A[1..j − 1]I Portanto, tj = j , para j = 2, 3, . . . , n. Como
n∑j=2
j =n(n + 1)
2 − 1
en∑
j=2(j − 1) =
n(n − 1)
2
o tempo de execucao no pior caso e
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 13 / 24
Analise do tempo de execucao
T (n) = c1n + c2(n − 1) + c4(n − 1) + c5
n(n + 1)
2 − 1
+ c6
n(n − 1)
2
+ c7
n(n − 1)
2
+ c8(n − 1)
T (n) =c5
2 +c62 +
c72
n2 +c1 + c2 + c4 +
c52 +
c62 +
c72 + c8
n
− (c1 + c4 + c5 + c8)
I Esse tempo pode ser expresso como T (n) = an2 + bn + c, paraconstantes a, b e c
I E uma funcao quadratica de n.I T (n) = Θ(n2)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 14 / 24
Analise do tempo de execucao
T (n) = c1n + c2(n − 1) + c4(n − 1) + c5
n(n + 1)
2 − 1
+ c6
n(n − 1)
2
+ c7
n(n − 1)
2
+ c8(n − 1)
T (n) =c5
2 +c62 +
c72
n2 +c1 + c2 + c4 +
c52 +
c62 +
c72 + c8
n
− (c1 + c4 + c5 + c8)
I Esse tempo pode ser expresso como T (n) = an2 + bn + c, paraconstantes a, b e c
I E uma funcao quadratica de n.I T (n) = Θ(n2)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 14 / 24
Analise do tempo de execucao
I Porque preferimos o pior caso?I E o limite superior sobre o tempo de execucao para qualquer
entradaI Para alguns algoritmos, ocorre com bastante frequenciaI Muitas vezes, o caso medio e quase tao ruim quanto o pior
caso
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 15 / 24
Ordenacao por intercalacao
I Utiliza a abordagem de divisao e conquistaI Divisao do problema em determinado numero de subproblemas
(instancias menores)I Conquista os subproblemas, resolvendo-os recursivamenteI Combinacao das solucoes dadas aos subproblemas
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 16 / 24
Merge(A, p, q, r)1 n1 = q - p + 12 n2 = r - q3 sejam L[1..n1+1] e R[1..n2+1] novos arranjos4 for i = 1 to n15 L[i] = A[p+i-1]6 for j = 1 to n27 R[j] = A[q+j]8 L[n1+1] = ∞9 R[n2+1] = ∞10 i = 111 j = 112 for k=p to r13 if L[i] ≤ R[j]14 then A[k] = L[i]15 i = i + 116 else A[k] = R[j]17 j = j + 1
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 17 / 24
Prova de corretude
I Invariante de lacoInicializacao Antes da primeira iteracao, k = p, de modo que o arranjo
A[p..k-1] esta vazio.Manutencao E preciso primeiro supor que L[i] ≤ R[j]. Nesse caso, L[i] e o
menor elemento nao copiado de volta em A (executa linhas 14e 15). Em seguida vamos supor que L[i] > L[j]. Entao L[j] e omenor elemento, o que muda as linhas que serao executadas(16 e 17).
Termino No termino, k = r + 1. Pelo invariante de laco, o subarranjoA[p..k-1] que e A[p..r], contem os k - p = r - p + 1 menoreselementos de L e R em sequencia ordenada. Todos oselementos, exceto os dois maiores (as sentinelas) foramcopiados de volta em A.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 17 / 24
Merge-sort(A, p, r)1 if p < r2 then q = b (p + r)/2 c3 Merge-sort (A, p, q)4 Merge-sort (A, q + 1, r)5 Merge (A, p, q, r)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 18 / 24
Analise do tempo de execucao
I Na chamada recursiva o tempo de execucao pode ser descritopor uma equacao de recorrencia ou recorrencia, quedescreve o tempod e execucao global de um problema detamanho n.
I Consideracoes:I T(n) e o tempo de execucao para um problema de tamanho n.I Se o tamanho e pequeno, digamos n ≤ c para alguma
constante c, a solucao leva tempo constante, representada porΘ(1).
I Temos ”a” subproblemas de tamanho ”b”. Cada subproblemaleva T(n/b) e portanto todos os subproblemas leva aT(n/b)
I D(n) e o tempo para dividir o problema em subproblemasI C(n) e o tempo para combinar as solucoes dadas
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 18 / 24
Analise do tempo de execucaoRecorrencia
T (n) =
{Θ(1) se n ≤ c,
aT (n/b) + D(n) + C(n) caso contrario .
DivisaoSimplesmente calcula o ponto medio do subarranjo, o que demoratempo constante: D(n) = Θ(1)
ConquistaResolvemos recursivamente dois subproblemas, cada um detamanho n/2, o que resulta em 2T(n/2)
CombinacaoO procedimento Merge para um subarranjo de n elementos leva otempo Θ(n). Portanto C(n) = Θ(n)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 19 / 24
Analise do tempo de execucao
Recorrencia Resultante:
T (n) =
{Θ(1) se n = 1,
2T (n/2) + Θ(n) se n > 1.
Ou ainda:
T (n) =
{c se n = 1,
2T (n/2) + cn se n > 1.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 20 / 24
Analise do tempo de execucao
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 21 / 24
Analise do tempo de execucao
I A arvore tem lg n + 1 nıveisI Portanto temos o custo cn x lg nI Isto resulta em um custo Θ(nlgn)
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 22 / 24
Exercıcios
I Leitura do capıtulo 2 e do apendice AI Exercıcios 2.1-1 a 2.1-4I Exercıcios 2.2-1 a 2.2-4I Exercıcios 2.3-1 a 2.3-7
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 23 / 24
Referencias
I Thomas H. Cormen et al. Introducao a Algoritmos. 2a edicaoem portugues. Capıtulo 2.
Autor: Prof. Marco Aurelio Lopes Barbosa (UEM/DIN) 24 / 24