• Pesquisa Binária

    1. A pesquisa binária é muito mais rápida do que a pesquisa simples.
    2. 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.
    3. A rapidez de um Algoritmo não é medida em segundos.
    4. O tempo de execução de um algoritmo é medido por meio de seu crescimento.
    5. O tempo de execução dos algoritmos é expresso na notação Big O.

    Pensamentos

    Todo algoritmo, por mais simples que seja, possui um tempo de execução, e esse tempo é medido pela notação Big O. Imagine quanto tempo levaria para procurar um elemento em uma lista de apenas 10 elementos; provavelmente seria muito rápido, talvez até menos de 1 milissegundo. No entanto, imagine agora que a lista tenha 4 bilhões de elementos; nesse caso, a busca pode levar consideravelmente mais tempo.
    No método convencional, leríamos a lista procurando nosso elemento um por um. Isso não é um problema quando a lista é pequena, mas quando ela se torna gigantesca, a abordagem se torna impraticável. É aí que a pesquisa binária entra em cena, pois, em vez de percorrer a lista elemento por elemento, você inicia a busca no meio da lista, com base em critérios específicos relacionados à ordenação, e, a partir daí, reduz as possibilidades pela metade. A pesquisa binária é especialmente eficiente para listas ordenadas, pois utiliza uma estratégia de divisão e conquista, dividindo repetidamente o espaço de busca pela metade até encontrar o elemento desejado.

    Exemplo de Código


    Copiar

    Ordenação por Seleção

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

    Pensamentos

    Antes de aprender sobre a Ordenação por Seleção, é importante compreender as diferenças entre Listas Encadeadas e Arrays pois ambos estão diretamente relacionados à memória da máquina. Como funcionam? Bem, listas e arrays possuem índices, e esses índices ocupam um espaço na memória, cada um de uma forma específica. Em listas encadeadas, os índices podem estar dispersos na memória, como este exemplo:

    vazio Café da Manhã vazio vazio vazio
    vazio ocupado vazio Jogar Bocha vazio
    ocupado ocupado Chá vazio ocupado

    Cada célula desta tabela representa um espaço na memória. Observe que os elementos na lista não estão contíguos. Em uma lista encadeada, cada item armazena o endereço do próximo item, mantendo assim a conexão entre os elementos. Portanto, adicionar novos elementos é uma tarefa simples, pois requer apenas um espaço livre na memória. O mesmo se aplica à remoção de elementos.
    No entanto, em um array, as coisas funcionam de maneira um pouco diferente:

    Café da Manhã Jogar Bocha Chá ocupado vazio
    vazio ocupado vazio vazio
    ocupado ocupado vazio ocupado

    Em um array, todos os elementos devem estar contíguos na memória. Portanto, ao criar um array, você primeiro precisa encontrar um espaço na memória que seja grande o suficiente para acomodar o array. Se você deseja adicionar um novo elemento e o próximo espaço de memória estiver ocupado, será necessário mover todo o array para um novo local na memória. A remoção de elementos também é mais complicada, pois a eliminação de um elemento, como “Jogar Bocha”, requer que todo o restante do array seja movido para manter a continuidade, tornando-o lento para inserções e exclusões, mas eficiente para leituras.

    Arrays Listas
    Leitura O(1) O(n)
    Inserção O(n) O(1)
    Eliminação O(n) O(1)

    Agora que compreendemos essas diferenças, podemos prosseguir para o nosso algoritmo de ordenação mais simples, a Ordenação por Seleção. Este algoritmo envolve a busca do menor/maior valor em uma lista desordenada e colocando-o como o primeiro elemento em uma nova lista. Repetimos esse processo em um loop até esvaziarmos a lista desordenada, resultando em uma lista ordenada.

    Exemplo de Código


    Copiar

    Recursão

    1. Recursão é quando uma função chama a si mesma.
    2. Toda função recursiva tem dois casos: o caso-base e o caso recursivo.
    3. Uma pilha tem duas operações: push e pop.
    4. Todas as chamadas de função vão para a pilha de chamada(call stack).
    5. A pilha de chamada pode ficar muito grande e ocupar muita memória.

    Pensamentos

    A recursão é um conceito fundamental na programação em que uma função chama a si mesma. Em geral, chamamos funções de fora do seu “escopo” quando achamos que é hora de executar o seu trabalho. No entanto, ao chamar uma função dentro dela mesma, criamos um processo recursivo. Isso pode resultar em um loop infinito, a menos que estabeleçamos uma condição de parada, o que é uma prática comum.
    As recursões têm uma função semelhante aos loops “for” e “while”. Todos eles são mecanismos de repetição que desempenham um papel importante em diferentes situações. As recursões são conhecidas por terem um tempo de execução geralmente mais eficiente do que os loops convencionais. No entanto, cada chamada recursiva gera uma estrutura de dados chamada “Pilha de Chamadas”, que é empilhada uma sobre a outra na memória. Portanto, é importante gerenciar o tamanho dessas pilhas para evitar o estouro de memória.
    Aqui está um exemplo de código que utiliza recursão para calcular o fatorial de um número. A cada chamada recursiva, a pilha armazena o valor de ‘X’ e o multiplica pelo próximo número menor, até que a condição base seja atingida, quando ‘X’ é menor ou igual a 1. Nesse momento, a recursão termina e o valor do fatorial é retornado.

    Exemplo de Código


    Copiar

    Quicksort

    1. A estratégia DC(Dividir para Conquistar) funciona por meio da divisão do problema em problemas menores.
    2. Se você estiver utilizando DC em uma lista, o caso-base provavelmente será um array vazio ou com apenas um elemento.
    3. Se você estiver implementando o quicksort, escolha um elemento aleatório como o pivô.
    4. O tempo de execução médio do quicksort é O(n log n)!
    5. A constante, na notação Big O, pode ser relevante em alguns casos. Está é a razão pela qual o quicksort é mais rápido do que o mergesort.
    6. 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.

    Pensamentos

    O algoritmo Quicksort, conhecido por sua estratégia “Dividir para Conquistar”, é um método de ordenação para listas que geralmente é mais rápido e eficiente em comparação com outros métodos. Para entender como funciona, primeiro precisamos estabelecer um “caso-base” para evitar problemas. No Quicksort, o caso-base ocorre quando a lista tem apenas um elemento, nesse caso, “um único elemento não precisa ser ordenado”.
    A essência do Quicksort é a escolha de um elemento especial chamado de “pivô”. Embora seja possível escolher o pivô aleatoriamente, geralmente escolhemos um valor que faça sentido para o nosso contexto. Em seguida, dividimos a lista em duas partes: uma para elementos menores que o pivô e outra para elementos maiores. Isso é feito usando um loop que percorre a lista e direciona cada elemento para a lista de menores ou maiores, dependendo de sua relação com o pivô.
    Este código divide a lista em partes menores e maiores em relação ao pivô e, em seguida, chama a função Quicksort recursivamente para ordenar essas partes. O pivô é inserido entre as partes ordenadas, criando uma lista ordenada completa.

    Exemplo de Código:


    Copiar

    Tabelas Hash

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

    Pensamentos

    As tabelas hash são estruturas de dados que se assemelham a listas e arrays, mas possuem propriedades distintas que as tornam especialmente úteis em diversas aplicações. Elas têm a capacidade de mapear chaves para valores, permitindo a recuperação eficiente de um valor com base em sua chave correspondente. No entanto, é importante destacar que colisões podem ocorrer em tabelas hash, diferentemente de listas e arrays convencionais. Isso acontece quando duas chaves diferentes são mapeadas para a mesma posição na tabela.
    A prevenção e tratamento de colisões em tabelas hash são aspectos cruciais de seu uso. Para evitar colisões, é essencial empregar uma função de hash eficaz, que distribua as chaves uniformemente ao longo da tabela. No caso de colisões, existem várias técnicas de resolução disponíveis, como encadeamento separado (onde cada posição da tabela contém uma lista ligada de valores) e resolução linear (tentativa de acomodar o valor em uma posição livre adjacente).
    As tabelas hash têm uma ampla gama de aplicações. Elas podem ser utilizadas como bancos de dados, caches de memória, ferramentas de verificação de integridade de dados e componentes essenciais em algoritmos de criptografia. Para que elas desempenhem seu papel com eficiência, é necessário escolher um tamanho adequado para a tabela, visando evitar colisões frequentes e garantir um funcionamento otimizado.

    Exemplo de Código


    Copiar

    Pesquisa em Largura

    1. A pesquisa em largura lhe diz se há um caminho de A para B.
    2. Se esse caminho existir, a pesquisa em largura lhe dará o caminho mínimo.
    3. 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 resolve-lo.
    4. Um dígrafo contém setas e as relações seguem a direção das setas(Rama -> Adit significa “Rama deve dinheiro a Adit”).
    5. 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”).
    6. Filas são FIFO (primeiro a entrar, primeiro a sair).
    7. Pilhas LIFO (ultimo a entrar, primeiro a sair).
    8. Você precisa verificar as pessoas na ordem em que elas foram adicionadas à lista de pesquisa. Portanto a lista de pesquisa deve ser uma fila; caso contrário, você não obterá o caminho mínimo.
    9. Cada vez que você precisar verificar alguém, procure não verifica-lo novamente. Caso contrário, poderá acabar em um loop infinito.

    Pensamentos

    A pesquisa em largura é uma técnica relativamente simples, mas poderosa, amplamente utilizada para encontrar o caminho mais curto entre dois pontos em um grafo. Se esse caminho existir, a pesquisa em largura retornará o percurso que leva menos “tempo” ou etapas para ser concluído. Essa abordagem é frequentemente empregada em problemas modelados como grafos, como ilustrado no exemplo a seguir.

    Grafo "em forma de tabela"

    Pessoa Amigos
    voce alice, bob, claire
    bob anuj, peggy
    alice peggy
    claire thom, jhonny
    anuj
    peggy
    thom
    jhonny

    Neste exemplo, suponhamos que desejamos encontrar o vendedor de manga mais próximo a partir de “você”. Para fazer isso, podemos adotar uma abordagem de pesquisa em largura. Começamos a análise a partir de “você” e, em seguida, exploramos sistematicamente cada elemento, indo do mais próximo ao mais distante.
    Primeiro, examinamos os amigos diretos de “você” (Alice, Bob e Claire). Em seguida, investigamos os amigos dos amigos (Anuj e Peggy) e continuamos expandindo nossa busca até identificarmos o vendedor de manga.
    Essa técnica é eficaz na descoberta de rotas curtas em uma ampla variedade de contextos, desde redes sociais até sistemas de mapeamento de rotas. Ela oferece uma abordagem sistemática para explorar conexões e encontrar soluções de maneira eficiente.

    Exemplo de Código


    Copiar

    Dijkstra

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

    Pensamentos

    Algoritmo de Dijkstra é uma técnica usada para encontrar o caminho mais curto entre um ponto de partida e todos os outros pontos em um grafo ponderado. Ele é amplamente utilizado em problemas de roteamento, otimização e sistemas de navegação.
    A principal ideia por trás do algoritmo é a busca por caminhos mais curtos, começando pelo ponto de partida e gradualmente explorando os nós vizinhos. O algoritmo mantém um conjunto de nodos não processados e seus custos associados. Inicialmente, todos os custos são definidos como infinito, exceto o custo do nó de partida, que é definido como zero.
    Em cada iteração, o algoritmo seleciona o nó com o custo mais baixo entre os nodos não processados e o marca como processado. Em seguida, atualiza os custos dos nodos vizinhos se um caminho mais curto for encontrado através do nó atual. Este processo é repetido até que todos os nodos tenham sido processados ou até que o destino desejado seja alcançado.

    Exemplo de Código

    dijkstra
    Copiar