1 - Fundamentos da Análise de Algoritmos
1.1 Introdução .................................................................... 1
1.2 Conceito de algoritmo ......................................................... 1
1.3 Análise algorítmica ........................................................... 3
1.4 Casos a considerar na análise ................................................. 5
1.5 Complexidade assimptótica ..................................................... 6
1.6 Classes de complexidade ....................................................... 10
1.7 Tipos de problemas mais importantes ........................................... 12
1.8 Estratégias algorítmicas ...................................................... 15
1.8.1 Força bruta e pesquisa exaustiva .......................................... 15
1.8.2 Dividir para conquistar ................................................... 16
1.8.3 Decrementar para conquistar ............................................... 17
1.8.4 Transformar para conquistar ............................................... 18
1.8.5 Programação dinâmica ...................................................... 19
1.8.6 Algoritmos gananciosos .................................................... 19
1.8.7 Recursividade com retrocesso .............................................. 20
1.9 Fórmulas úteis para a análise de algoritmos ................................... 20
1.10 Exemplos ..................................................................... 22
Leituras Recomendadas ............................................................. 32
Exercícios ........................................................................ 33
2 - Pesquisa e Seleção
2.1 Introdução .................................................................... 37
2.2 Algoritmos de pesquisa ........................................................ 37
2.2.1 Pesquisa sequencial ....................................................... 38
2.2.2 Pesquisa binária .......................................................... 41
2.2.3 Pesquisa ternária ......................................................... 49
2.2.4 Análise experimental dos algoritmos de pesquisa ........................... 57
2.3 Algoritmos de seleção ......................................................... 58
2.3.1 Seleção do maior e do menor valores ....................................... 58
2.3.2 Seleção do K-ésimo menor valor ............................................ 61
Leituras Recomendadas ............................................................. 67
Exercícios ........................................................................ 68
3 - Ordenação
3.1 Introdução .................................................................... 71
3.2 Métodos de ordenação .......................................................... 72
3.3 Ordenação Sequencial .......................................................... 73
3.4 Ordenação Seleção ............................................................. 75
3.5 Ordenação Bubble .............................................................. 77
3.6 Ordenação Inserção ............................................................ 80
3.7 Ordenação de Shell ............................................................ 83
3.8 Ordenação Heap ................................................................ 87
3.8.1 Construção do amontoado binário ........................................... 88
3.8.2 Implementação do algoritmo ................................................ 91
3.9 Ordenação Merge ............................................................... 98
3.10 Ordenação Inserção Recursiva ................................................. 101
3.11 Ordenação Quick .............................................................. 106
3.12 Comparação dos algoritmos de ordenação ....................................... 114
3.13 Limite inferior da complexidade da ordenação ................................. 115
Leituras Recomendadas ............................................................. 117
Exercícios ........................................................................ 118
4 - Recursividade e Programação Dinâmica
4.1 Introdução .................................................................... 119
4.2 Exemplos simples .............................................................. 121
4.3 Conversão de decimal para binário ............................................. 126
4.4 Torres de Hanói ............................................................... 128
4.5 Cálculo das permutações ....................................................... 131
4.6 Teorema mestre ................................................................ 133
4.7 Números de Fibonacci .......................................................... 137
4.8 Função numérica com recursividade não linear .................................. 142
Leituras Recomendadas ............................................................. 149
Exercícios ........................................................................ 150
5 - Algoritmos Numéricos
5.1 Introdução .................................................................... 153
5.2 Cálculo da potência ........................................................... 153
5.3 Avaliação do polinómio ........................................................ 156
5.4 Multiplicação binária por partição ............................................ 157
5.5 Multiplicação de polinómios ................................................... 158
5.6 Cálculo do determinante ....................................................... 162
5.7 Multiplicação de matrizes ..................................................... 168
Leituras Recomendadas ............................................................. 175
Exercícios ........................................................................ 176
Glossário de Termos - Português Europeu/Português do Brasil
Índice Remissivo