Introdução a algoritmos e estruturas de dados
Tags: algorithms, datastructures
Published: 2022-04-08 18:35:28

Se você é novo na área de TI, mas já sabe alguma linguagem de programação (mesmo que só o básico de lógica de programação) e está começando agora a estudar algoritmos e estruturas de dados, talvez a série de posts que se inicia com este possa te ajudar.

Particularmente eu tive bastante dificuldade quando comecei a estudar alguns algoritmos mais mirabolantes e algumas estruturas de dados (se você é alguém que não curte livros tão maçantes sobre as coisas, assim como eu, talvez se identifique). Pretendo botar nesse e nos próximos posts explicações que funcionaram muito bem para mim no meu tempo na universidade e espero que possam te servir também! 😃

Antes de começarmos por alguns conceitinhos básicos, já quero deixar claro que irei usar a linguagem Python nos meus exemplos, então é bom que você saiba ao menos um pouco sobre a sintaxe da linguagem. Beleza, com tudo isso em mente, vamos lá!


## O que é um algoritmo computacional?
Um algoritmo computacional (ou apenas algoritmo, para os mais íntimos) é qualquer procedimento computacional **bem definido** que aceita um valor ou um conjunto de valores como **entrada** e produz um valor ou um conjunto de valores como **saída**. Para quem já estudou funções (as da matemática mesmo), deve achar essa definição bem familiar, não é?


![Máquina de algoritmo representada por um paralelepípedo com uma cavidade de entrada e uma de saída. As cavidades representam a entrada e saída de dados do algoritmo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zab7txwweoof3jm0rdbn.png)

E não é por acaso, não! As funções da matemática são algoritmos também e vice-versa, mas não se preocupe se nunca tiver estudado isso na escola, não vai ser nada complicado.😉

A gente geralmente usa os algoritmos para resolver algum problema de computação. Um exemplo disso é o algoritmo de soma (sim, é um exemplo básico, mas não deixa de ser um algoritmo):

```python
def soma(a, b):
    resultado = a + b
    return resultado
```
O que o algoritmo acima faz é solucionar um problema de computação, que é somar dois números (somar é uma computação). Este algoritmo é descrito numa linguagem que o computador consegue entender (Python) e sem ambiguidades, com isso tendo a chamada **precisão**. Considere que executemos o algoritmo com as entradas 1 e 9:

```python
teste = soma(1, 9)
print(teste)
```

O código acima irá imprimir 10 na tela, o que é de se esperar. Quando o nosso algoritmo produz os resultados esperados, dizemos que ele tem a propriedade de **correção**.

Um bom algoritmo sempre atende aos critérios de **precisão** e **correção**. Também é bom quando o nosso algoritmo faz um **uso eficiente dos recursos do computador** em que ele vai rodar, já que o tempo e os recursos são finitos.

## Corretude dos algoritmos
Como acabamos de ver, um algoritmo atende ao critério de correção quando o que ele retorna é considerado correto de acordo com a(s) entrada(s) considerada(s). Bem, nem sempre é fácil ou possível saber se a saída do algoritmo está certa de acordo com a(s) entrada(s).

Um exemplo comum é quando consideramos o problema de achar o melhor caminho entre dois lugares, um problema que vamos falar em um futuro post. Considere a imagem abaixo, queremos achar uma rota entre os pontos **A** e **B** e que precisamos desenvolver um algoritmo que ache uma rota entre esses dois pontos.


![Mapa do google maps mostrando uma possível rota entre o museu do Ipiranga até o MASP, ambos na cidade de São Paulo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/di22lz49eb85in0subf5.png)

Se o nosso problema é fazer o algoritmo retornar uma rota qualquer entre A e B (ou seja, nosso critério para considerar correta a saída do algoritmo é ele retornar uma caminho qualquer entre A e B), é fácil.

Agora, quando o problema considerado é encontrar a **melhor rota** entre A e B, a coisa complica um pouco, já que é bem difícil determinar se a resposta está certa ou não. Neste caso, precisamos arranjar uma forma de medir o quão "ótima" é a resposta que o algoritmo nos dá.

## Eficiência de algoritmos
Uma forma de sabermos se o nosso algoritmo está fazendo um uso eficiente dos recursos (computacionais e de tempo) é analisar o tempo de execução e a memória exigida para que ele rode na nossa máquina.

Diferentes algoritmos que resolvem o exato mesmo problema podem ter desempenhos bem diferentes. Mais para frente iremos falar sobre a **análise da complexidade** de algoritmos, que é uma forma de estimar o tempo de execução e a memória utilizada durante a execução do algoritmo, técnica bastante utilizada durante o desenvolvimento. Vale ressaltar que, depois de termos desenvolvido o algoritmo, podemos usar ferramentas que nos indicam de forma quantitativa esses parâmetros, como é o caso do *benchmarking*.

A análise dos algoritmos independe da tecnologia utilizada (linguagem de programação, etc). A análise é importante pois nos dá um norte de qual algoritmo, dentre os possíveis vários que resolvem o mesmo problema, devemos escolher, tendo em vista os recursos computacionais e o tempo limitados.


## Estrutura de dados
Uma estrutura de dados é uma forma de **organizar**, **armazenar**, **acessar** e **modificar** dados que estão na memória do computador. Um exemplo clássico é o *array* (ou vetor), presente em todas as principais linguagens de programação.


![Sequência de retângulos com nomes de pessoas dentro, representando a estrutura de um vetor de strings de uma linguagem de programação](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cn713lhbhnh9n1iww5k1.png)

No nosso vetor acima, temos os nomes "Maria", "Lucas", "José" e "Frida" armazenados nesta ordem. Na maioria das linguagens de programação, temos métodos para buscar, remover e inserir dados no nosso array (operações de **manipulação de dados**).

Tá, mas o que estrutura de dados tem a ver com algoritmos? A resposta é simples: tem tudo a ver! A estrutura de dados costuma interferir na eficiência dos algoritmos, uma vez que em uma estrutura de dados **A** qualquer podemos ter um tempo de acesso a um elemento diferente do tempo de acesso em uma estrutura de dados **B**.

Não há estrutura de dados perfeita, cada uma tem seus pontos fortes e fracos. Temos que analisar, durante a construção de um algoritmo, qual/quais seria(m) a(s) estrutura(s) de dados mais adequada(s) a ser(em) utilizada(s) no caso.

Um exemplo é quando consideramos um comércio e o processamento de pedidos deste em sua loja virtual. Seria um enorme desperdício de memória guardar todos os pedidos em um vetor/array, além de que os pedidos só podem ser removidos ou adicionados em ordem. Uma melhor estrutura de dados para armazenar os pedidos seria uma **lista ligada**, em que temos alocação e desalocação dinâmica de memória (vamos falar melhor disso mais para frente).

## É isso!
Enfim, é basicamente isso! Isso é apenas um introdução aos conceitos mais importantes de algoritmos e estruturas de dados, nada muito aprofundado. Como já disse várias vezes, pretendo fazer mais posts entrando em detalhes, em algoritmos mais específicos, etc. Espero que tenha gostado da leitura. Qualquer coisa, me chama no twitter!