Análise de Algoritimo

Universidade do Estado de Minas Gerais 
Fundação Educacional de Ituiutaba 
Engenharia da Computação 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
APOSTILA DE 
 
ANÁLISE DE ALGORITMOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Walteno Martins Parreira Júnior 
www.waltenomartins.com.br 
waltenomartins@yahoo.com 
 
 
2012 
Análise de Algoritmos 
Prof. Walteno Martins Parreira Jr Pág. 1 
Sumário 
1 – Desenvolvimento de Algoritmos ............................................................................................................... 2 
1.1 – Introdução.......................................................................................................................................... 2 
1.2 – O que é um algoritmo......................................................................................................................... 2 
1.3 – Medidas de Complexidade ................................................................................................................. 2 
1.4 – Análise de Complexidade de um algoritmo......................................................................................... 6 
1.5 – Notação O.......................................................................................................................................... 6 
1.6 – Convenções para as expressões de O .................................................................................................. 8 
1.7 – Exemplo de análise da notação O ....................................................................................................... 8 
1.8 – Análise de complexidade da Busca Linear .......................................................................................... 9 
1.8.1 – Pior Caso................................................................................................................................... 10 
1.8.2 – Caso Médio ............................................................................................................................... 10 
1.8.3 – Melhor Caso.............................................................................................................................. 11 
1.8.4 – Um exemplo numérico............................................................................................................... 11 
1.9 – Exemplos ........................................................................................................................................ 12 
1.10 - Exercício Prático Algoritmo Busca a primeira ocorrência: ............................................................... 13 
2 – Estratégias Básicas.................................................................................................................................. 14 
2.1 – Refinamento Sucessivo .................................................................................................................... 14 
2.2 – Modularização ................................................................................................................................. 14 
2.3 – Confiabilidade X Complexidade....................................................................................................... 15 
3 – Divisão e Conquista................................................................................................................................ 16 
3.1 – Máximo e Mínimo de uma lista ........................................................................................................ 16 
3.2 – Exercício MaxMin ........................................................................................................................... 20 
3.3 – Ordenação por Intercalação .............................................................................................................. 21 
3.4 – Ordenação por Concatenação ........................................................................................................... 23 
3.5 – Busca Binária................................................................................................................................... 25 
3.6 – Exercício prático de Busca Binária ................................................................................................... 26 
3.7 - Lista de Exercícios da Unidade ......................................................................................................... 27 
4 - Métodos de Ordenação ............................................................................................................................ 29 
4.1 - Métodos de Ordenação Interna.......................................................................................................... 29 
4.2 - Método de ordenação por Seleção ..................................................................................................... 30 
4.2.1 - Algoritmo de Ordenação por seleção: ......................................................................................... 30 
4.2.2 - Análise de complexidade............................................................................................................ 30 
4.3 - Método de ordenação por Inserção .................................................................................................... 31 
4.3.1 - Algoritmo de Ordenação por Inserção ............................................................................................ 31 
4.3.2 - Análise de complexidade do algoritmo ........................................................................................... 32 
4.4 - Método de ordenação Quicksort ........................................................................................................ 33 
4.4.1 - Algoritmo Partição..................................................................................................................... 34 
4.4.2 - Versão recursiva do Quicksort .................................................................................................... 34 
4.4.3 - Outra versão recursiva do Quicksort ........................................................................................... 34 
4.4.4 - Versão iterativa do Quicksort ..................................................................................................... 35 
4.4.5 - Conclusão .................................................................................................................................. 39 
4.5 - Método de ordenação Shellsort ......................................................................................................... 40 
4.5.1 – Algoritmo Shellsort ................................................................................................................... 41 
4.5.2 - Análise do algoritmo .................................................................................................................. 41 
4.6 - Método de ordenação Heapsort ......................................................................................................... 42 
4.6.1 - Fila de prioridades...................................................................................................................... 42 
4.6.2 - Heaps......................................................................................................................................... 43 
4.6.3 - Heapsort .................................................................................................................................... 43 
4.6.4 - Análise de complexidade do Heapsort ........................................................................................ 45 
4.6.5 - Conclusão .................................................................................................................................. 46 
4.7 - Comparação entre os métodos de ordenação......................................................................................