Algoritmos e estrutura de dados

Um algoritmo é uma receita, ou seja, uma sequência finita de passos lógicos e bem definidos, criada para resolver um problema específico ou executar uma tarefa.

• Análise (Eficiência): A "qualidade" de um algoritmo é medida por sua complexidade:

Complexidade de Tempo: Quão rápido o algoritmo executa (quantos passos ele leva) à medida que a quantidade de dados aumenta.

Complexidade de Espaço: Quanta memória o algoritmo consome para rodar.

Estruturas de dados são formas sistemáticas de organizar, armazenar e gerenciar dados no computador, para que possam ser acessados e modificados de forma eficiente. Alguns exemplos:

Tipos Principais (Lineares):

• Array (Vetor/Lista): Uma coleção de itens armazenados em locais de memória contíguos. Ótimo para acesso rápido pelo índice (ex: lista[5]).

• Lista Ligada (Linked List): Uma coleção de itens onde cada um "aponta" para o próximo. Ótimo para inserir e remover itens no meio da lista.

• Pilha (Stack): Segue a regra "Último a Entrar, Primeiro a Sair" (LIFO - Last In, First Out). Pense em uma pilha de pratos.

• Fila (Queue): Segue a regra "Primeiro a Entrar, Primeiro a Sair" (FIFO - First In, First Out). Pense em uma fila de banco.

Tipos Principais (Não-Lineares):

• Árvores (Trees): Estrutura hierárquica. Ótima para buscas rápidas (ex: Árvore Binária de Busca) ou para representar hierarquias (ex: pastas de arquivos).

• Grafos (Graphs): Estrutura que representa conexões (redes). Usado para mapas (GPS), redes sociais, etc.

- Dica:

• Fazer uma busca binária em uma lista ligada é ineficiente

Algoritmos de Busca

Os Algoritmos de Busca são métodos usados para verificar se uma dada informação (x) ocorre em uma sequência (seq). O objetivo é implementar a lógica por trás de operações comuns em Python, como o operador in (x in seq) ou o método .index().

Existem duas estratégias principais: a busca sequencial e a busca binária.

Busca Sequencial

• Definição: Também conhecida como busca linear, é o método de busca mais simples.
• Estratégia: Percorre a lista elemento por elemento, do índice 0 até o final (len(seq) - 1), comparando cada item seq[i] com x.
• Desvantagem: É ineficiente para listas grandes. No pior caso (quando x não está na lista), o algoritmo precisa varrer toda a sequência.

Código Exemplo (Busca Sequencial)

<syntaxhighlight lang="python"> def busca_sequencial(x, seq):

   (float, list) -> bool
   Retorna True se x ocorre na lista, ou False caso contrário.
   
   for i in range(len(seq)):
       if seq[i] == x:
           return True
   return False

</syntaxhighlight>

Busca Binária

• Definição: Um algoritmo de busca muito mais eficiente, que "corta" o problema pela metade a cada passo.
• Pré-requisito: A sequência OBRIGATORIAMENTE precisa estar ordenada (ex: do menor para o maior).
• Estratégia (Método do Dicionário):

1. Considere o elemento M no meio da lista.
2. Se x == M, o elemento foi encontrado.
3. Se x < M, o elemento (se existir) só pode estar na primeira metade. A segunda metade é descartada.
4. Se x > M, o elemento (se existir) só pode estar na segunda metade. A primeira metade é descartada.
5. O processo é repetido na metade restante, cortando a área de busca repetidamente.

• Vantagem (Eficiência): É extremamente rápido. Em uma lista com 1024 elementos, a busca sequencial faria 1024 testes no pior caso. A busca binária faria no máximo 10 testes (pois log₂(1024) = 10).

Código Exemplo (Busca Binária)

<syntaxhighlight lang="python"> def busca_binaria(x, seq):

    (float, list) -> int ou None
       Retorna a posição (índice) em que x ocorre na lista ORDENADA,
       ou None caso contrário.
   
   inicio = 0
   fim = len(seq) - 1
   
   while inicio <= fim:
       meio = (inicio + fim) // 2 # Divisão inteira para achar o índice do meio
       
       if seq[meio] == x:
           return meio # ACHOU! Retorna a posição.
       elif seq[meio] > x:
           # x é menor, joga fora a metade da direita
           fim = meio - 1
       else: # seq[meio] < x
           # x é maior, joga fora a metade da esquerda
           inicio = meio + 1
           
   return None # O loop terminou (inicio > fim) e não achou.

</syntaxhighlight>