Sumário

Prefácio ..............................................................................13

Introdução ..........................................................................15

Pseudocódigo .........................................................................................16
Análise de casos ....................................................................................18
Análise do melhor caso ........................................................................... 18
Análise do caso médio ............................................................................ 18
Análise do pior caso ................................................................................ 19
Métodos de análise de complexidade .................................................19

Modelo RAM de Computação ............................................. 21
Bubble Sort μ ........................................................................................21
Análise detalhada .................................................................................... 22
Análise resumida ..................................................................................... 26
Exemplos ................................................................................................... 27
Código ....................................................................................................... 30

Selection Sort μ .....................................................................................33
Análise detalhada .................................................................................... 33
Análise resumida ..................................................................................... 37
Exemplos ................................................................................................... 38
Código ....................................................................................................... 41

Insertion Sort μμ ................................................................................44
Análise detalhada .................................................................................... 45
Análise resumida ..................................................................................... 48
Exemplos ................................................................................................... 50
Código ....................................................................................................... 53

Transposição de Matriz μμ ...............................................................56
Análise detalhada .................................................................................... 57
Análise resumida ..................................................................................... 60
Exemplos ................................................................................................... 62
Código ....................................................................................................... 68

Rotação de Matriz μμμ .................................................................... 71
Análise detalhada .................................................................................... 72
Análise resumida ..................................................................................... 76
Exemplos ................................................................................................... 77
Código ....................................................................................................... 80

Stupid Sort μμμμ ............................................................................82
Caracterização do melhor e pior caso................................................... 82
Análise detalhada .................................................................................... 85
Exemplos ................................................................................................. 101
Código ......................................................................................................104

Análise Comparativa de Complexidade ............................... 108
Problema 1 ............................................................................................ 108
Problema 2 ............................................................................................ 110
Problema 3 ............................................................................................ 113

Análise Assintótica de Complexidade ...................................117
Problema 4 .............................................................................................117
Solução incorreta ................................................................................. 118
Por que a solução é incorreta ................................................................119
Solução correta pelo método gráfi co ................................................ 121
Solução correta pelo método analítico ............................................. 124
Método analítico aplicado à solução incorreta ................................ 126

Análise Assintótica Aplicada ............................................... 129
Problema 5 ............................................................................................ 129
Problema 6 ............................................................................................ 131
Problema 7 ............................................................................................ 134
Problema 8 ............................................................................................ 136

Conclusão ......................................................................... 140

Leituras Recomendadas ...................................................... 142

Book Trailer