Se você quer se tornar um engenheiro de software, mas não sabe por onde começar, vamos salvar o suspense: são algoritmos e estruturas de dados.
Após você obter a essência desses pilares da programação, você começará a vê-los em todos os lugares. E quanto mais algoritmos e estruturas de dados você aprender, mais eles servirão como combustível para sua carreira como engenheiro de software.
Para começar, vamos primeiro mergulhar fundo na Search and Sort, duas classes de algoritmos sem os quais você não pode viver. Depois vamos fazer um rápido levantamento do resto da paisagem que inclui árvores, gráficos, programação dinâmica e toneladas a mais.
Em termos gerais, há duas categorias de algoritmos de busca que você precisará saber imediatamente: linear e binário. Depth First Search (DFS) e Breadth First Search (BFS) também são super importantes, mas vamos salvá-los para a seção de travessia do gráfico abaixo.
Linear search
Os algoritmos lineares e binários são nomeados como tal para descrever quanto tempo (complexidade de tempo) uma pesquisa vai levar com base no tamanho da entrada que está sendo pesquisada.
Por exemplo, com algoritmos de pesquisa linear, se você tiver 100 itens para pesquisar, então o pior cenário exigiria que você olhasse cada item no input antes de encontrar o valor desejado. É chamado linear porque o tempo que leva para pesquisar está exatamente correlacionado com a quantidade de itens na pesquisa (100 itens/entrada = 100 verificações/complexidade)
Em resumo, linear = simples (não há nada de inteligente no algoritmo). Por exemplo: imagine que você está tentando encontrar seu amigo Lin entre uma linha de pessoas sem uma ordem em particular. Você já sabe como Lin é, então você simplesmente tem que olhar para cada pessoa, uma a uma, em sequência, até que você reconheça ou não reconheça Lin. É isso mesmo. Ao fazer isso, você está seguindo o algoritmo de busca linear
Binary search
Binary search gets its name because the word binary means “of or relating to 2 things” and the algoritmo funciona dividindo a entrada em duas partes até encontrar o item que está sendo procurado. Uma metade contém o item pesquisado e a outra metade não. O processo continua até que o local onde o input é dividido se torne o item que está sendo pesquisado. A pesquisa binária é basicamente apenas uma abordagem altamente disciplinada do processo de eliminação. É mais rápida que a busca linear, mas só funciona com sequências ordenadas.
Um exemplo deve deixar isso mais claro. Suponha que você esteja tentando encontrar o seu amigo Bin (que tem 1,5 m) em uma linha de arquivo único de pessoas que foram ordenadas por altura da esquerda para a direita, do mais baixo para o mais alto. É uma fila muito longa, e você não tem tempo de passar um a um por todo o processo, comparando a altura de todos com a de Bin. O que pode fazer?