Entendendo algoritmos | Douglas Scaini

Principais conceitos de computação demonstrados no livro Entendendo algoritmos:

Capítulo 1 - Introdução a algoritmos

A pesquisa binária é muito mais rápida do que a pesquisa simples.
O(log n) é mais rápido do que O(n) e O(log n) fica ainda mais rápido conforme os elementos da lista aumentam.
A rapidez de um algoritmo não é medida em segundos.
O tempo de execução de um algoritmo é medido por meio de seu crescimento.
O tempo de execução dos algoritmos é expresso na notação Big O.

A memória do seu computador é como um conjunto gigante de gavetas.
Quando se quer armazenar múltiplos elementos, usa-se um array ou uma lista.
No array, todos os elementos são armazenados um ao lado do outro.
Na lista, os elementos estão espalhados e um elemento armazena o endereço do próximo elemento.
Arrays permitem leituras rápidas.
Listas encadeadas permitem rápidas inserções e eliminações.
Todos os elementos de um array devem ser do mesmo tipo (todos ints, todos doubles, e assim por diante).

A estratégia DC (Dividir para Conquistar) funciona por meio da divisão do problema em problemas menores. Se você estiver utilizando DC em uma lista, o caso-base provavelmente será um array vazio ou um array com apenas um elemento.
Se você estiver implementando o quicksort, escolha um elemento aleatório como o pivô. O tempo de execução médio do quicksort é O(n log n)!
A constante, na notação Big O, pode ser relevante em alguns casos. Está é a ração pela qual o quicksort é mais rápido do que o merge sort.
A constante dificilmente será relevante na comparação entre pesquisa simples e pesquisa binária, pois O(log n) é muito mais rápido do que O(n) quando sua lista é grande.

Você pode fazer uma tabela hash ao combinar uma função hash com um array.
Colisões são problemas. É necessário haver uma função hash que minimize colisões.
As tabelas hash são extremamente rápidas para pesquisar, inserir e remover itens.
Tabelas hash são boas para modelar relações entre dois itens.
Se o seu fator de carga for maior que 0.7, será necessário redimensionar a sua tabela hash.
As tabelas hash são utilizadas como cache de dados (como em um servidor da web, por exemplo).
Tabelas hash são ótimas para localizar duplicatas.

A pesquisa em largura lhe diz se há um caminho de A para B.
Se esse caminho existir, a pesquisa em largura lhe dará o caminho mínimo.
Se você tem um problema do tipo “encontre o menor X”, tente modelar o seu problema utilizando grafos e use a pesquisa em largura para resolvê-lo.
Um dígrafo contem setas e as relações seguem a direção das setas (Rama → Adit significa “Rama deve dinheiro a Adit).
Grafos não direcionados não contêm setas, e a relação acontece nos dois sentidos (Ross - Rachel significa “Ross namorou Rachel e Rachel namorou Ross”).
Filas são FIFO (primeiro a entrar, primeiro a sair).
Pilhas são LIFO (último a entrar, primeiro a sair).
Você precisa verificar as pessoas na ordem em que elas foram adicionadas a lista de pesquisa. Portanto a lista de pesquisa deve ser uma fila; caso contrário, você não obterá o caminho mínimo.
Cada vez que você precisar verificar alguém, procure não verificá-lo novamente. Caso contrário, poderá acabar em um loop infinito.

A pesquisa em largura é usada para calcular o caminho mínimo para um grafo não ponderado.
O algoritmo de Dijkstra é usado para calcular o caminho mínimo para um grafo ponderado.
O algoritmo de Dijkstra funciona quando todos os pesos são positivos.
Se o seu grafo tiver pesos negativos, use o algoritmo de Bellman-Ford.

Algoritmos gulosos otimizam localmente na esperança de acabar em uma otimização global.
Problemas NP-completo não tem uma solução rápida.
Se você estiver tentando resolver um problema NP-completo, o melhor a se fazer é usar um algoritmo de aproximação.
Algoritmos gulosos são fáceis de escrever e têm tempo de execução baixo, portanto eles são bons algoritmos de aproximação.

A programação dinâmica é útil quando você está tentando otimizar algo em relação a um limite.
Você pode utilizar a programação dinâmica quando o problema puder ser dividido em subproblemas discretos.
Os valores nas células são, geralmente, o que você está tentando otimizar.
Cada célula é um subproblema, então pense sobre como é possível dividir este subproblema em outros subproblemas.
Não existe uma fórmula única para calcular uma solução em programação dinâmica.

O algoritmo dos k-vizinhos mais próximos é utilizado na classificação e também na regressão. Ele envolve observar os K-vizinhos mais próximos.
Classificação = classificar em grupos.
Regressão - adivinhas uma resposta (como um número).
Extrair características significa converter um item (como uma fruta ou um usuário) em uma lista de números que podem ser comparados.
Escolher boas características é uma parte importante para que um algoritmos dos k-vizinhos mais próximos opere corretamente.