Mudanças entre as edições de "Algoritmos e estrutura de dados"

De Wikoleculares
Ir para navegação Ir para pesquisar
Linha 30: Linha 30:
 
- Dica:
 
- Dica:
 
* Fazer uma busca binária em uma lista ligada é ineficiente
 
* 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 (<code>x</code>) ocorre em uma sequência (<code>seq</code>). O objetivo é implementar a lógica por trás de operações comuns em [[Python]], como o operador <code>in</code> (<code>x in seq</code>) ou o método <code>.index()</code>.
 +
 +
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 <code>0</code> até o final (<code>len(seq) - 1</code>), comparando cada item <code>seq[i]</code> com <code>x</code>.
 +
* '''Desvantagem:''' É ineficiente para listas grandes. No pior caso (quando <code>x</code> 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):'''
 +
# Considere o elemento <code>M</code> no '''meio''' da lista.
 +
# Se <code>x == M</code>, o elemento foi encontrado.
 +
# Se <code>x < M</code>, o elemento (se existir) só pode estar na primeira metade. A segunda metade é descartada.
 +
# Se <code>x > M</code>, o elemento (se existir) só pode estar na segunda metade. A primeira metade é descartada.
 +
# 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<sub>2</sub>(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>
  
 
=Referências Interessantes=
 
=Referências Interessantes=

Edição das 11h10min de 3 de novembro de 2025

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 log2(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>

Referências Interessantes

Disponível em "http://wiki.cecm.usp.br/wiki/index.php?title=Algoritmos_e_estrutura_de_dados&oldid=21490"