The Algorithm Design Manual
Podemos nos deparar em alguns momentos com situações onde o algoritmo com a solução correta, não é implementavel na prática, por motivos do poder computacional necessário ou outro, nesses casos recorremos a heuristica. Heuristica irá nos ajudar nesses cenários com atalhos que nos levam a soluções que respondam o problema satisfatoriamente.
Heuristica é utilizado em problema de otimização complexos onde algoritmos exatos demoram muito tempo para serem calculados
Podemos expressar algoritmos nas seguintes formas:
- Linguagem natural (Português)
- Pseudocode
- Linaguage de Programação
Analise de algoritmos
- modelo RAM
- analise assintótica
Case complexity
- worst case
- average case
- best case
The Big OH Notation
Estrutura de Dados
Mudanças na estrutura de dados não mudam um algoritmo correto mas influencia na sua performance.
Tres abstrações de dados fundamentais:
- containers
- dicionarios
- filas de prioridade (priority queue)
Contiguous vs Linked Data Structures
- Contiguous means that it is composable of a single slab of memory
- Linked distincts chucks of memory bound together by pointers
Arrays
- constant-time access given the index
- space effiency no metadata needed so no space is wasted
- memory locality
Linked List
pagina 69 —-