Algoritmos, lógica de programação e estruturas de dados

Do zero

Um algoritmo é uma receita: uma sequência finita de passos claros que leva de uma entrada a um resultado. Toda receita usa só três movimentos, que são a base da lógica de programação:

• Sequência: faça um passo depois do outro.
• Decisão: se a massa estiver mole, acrescente farinha (o if).
• Repetição: mexa até engrossar (o while e o for).

E estrutura de dados é o jeito de arrumar as coisas para achá-las depressa. Cada arrumação serve para um uso:

• Vetor (array): uma fileira de gavetas numeradas. Vai direto à gaveta 7, mas abrir espaço no meio obriga a empurrar todas as outras.
• Lista encadeada: uma caça ao tesouro. Cada item diz onde está o próximo. Inserir no meio é fácil; chegar ao décimo item exige passar pelos nove anteriores.
• Pilha: uma pilha de pratos. O último que entra é o primeiro que sai (LIFO). É o “desfazer” do editor.
• Fila: a fila do banco. O primeiro que entra é o primeiro que sai (FIFO). É a fila de processos do protocolo.
• Árvore: um organograma, com uma raiz e ramos. As pastas do computador são uma árvore.
• Grafo: um mapa de cidades e estradas, em que qualquer ponto pode se ligar a qualquer outro.
• Tabela hash: um armário em que uma regra transforma o nome (a chave) no número da gaveta. Achar o CPF 123 não exige olhar os outros.

Frase para guardar: pilha é o último que entra, fila é o primeiro que chega; vetor acessa pelo índice, lista encadeada pelo caminho; hash vai direto pela chave.

Em 1 minuto

• Complexidade (notação O): como o tempo cresce quando a entrada cresce. Do melhor para o pior: O(1) constante, O(log n) logarítmico, O(n) linear, O(n log n), O(n²) quadrático.
• Busca linear olha um a um: O(n). Busca binária exige a lista ordenada e corta o problema pela metade a cada passo: O(log n). Em um milhão de itens, cerca de 20 passos.
• Ordenação: bubble, insertion e selection sort são O(n²); merge sort é O(n log n) sempre (e usa memória extra); quicksort é O(n log n) em média, mas O(n²) no pior caso; heap sort é O(n log n).
• Recursão: uma função que chama a si mesma, com um caso base que a faz parar. Sem caso base, ela não termina (estouro de pilha).
• Árvore binária de busca: à esquerda, menores; à direita, maiores. O percurso em ordem devolve os valores ordenados.

Exemplo concreto: a busca binária e a árvore dos processos

A busca binária é como procurar uma palavra no dicionário: abre no meio, vê se a palavra está antes ou depois e descarta metade.

def busca_binaria(lista, alvo):
    inicio, fim = 0, len(lista) - 1
    while inicio <= fim:
        meio = (inicio + fim) // 2
        if lista[meio] == alvo:
            return meio
        if lista[meio] < alvo:
            inicio = meio + 1      # descarta a metade da esquerda
        else:
            fim = meio - 1         # descarta a metade da direita
    return -1                      # não encontrou

Com 1.024 processos ordenados, a busca linear pode precisar de 1.024 comparações; a binária, de no máximo 11 (1.024 → 512 → 256 → … → 1). Por isso o crescimento é logarítmico: dobrar a lista acrescenta só um passo.

Agora, uma árvore binária de busca montada com a chegada dos processos de números 8, 3, 10, 1, 6 e 14, nessa ordem. Cada número vai para a esquerda se for menor que o nó e para a direita se for maior:

          8
        /   \
       3     10
      / \      \
     1   6      14

Os três percursos clássicos mudam só o momento de visitar a raiz:

Comparação: as estruturas e os algoritmos

Uma pilha passo a passo: empilha 5, empilha 8, desempilha (sai o 8), empilha 3, empilha 9, desempilha (sai o 9), desempilha (sai o 3). Sobra o 5. Com uma fila e as mesmas operações, sairiam 5, 8 e 3, e sobraria o 9.

Como a FCC cobra

• Busca binária: requisito de ordenação e número de comparações.
• Quicksort × merge sort no pior caso.
• Qual estrutura escolher para um problema.
• Trechos de pseudocódigo com laços e condições: qual o valor final de uma variável.
• Recursão e caso base.

Pegadinhas

Explique com suas palavras

Explique a um colega por que a busca binária precisa de no máximo uns 20 passos num milhão de itens, e por que ela não funciona se a lista estiver fora de ordem.

1. Escreva sem olhar a lição, com frases curtas e um exemplo seu.
2. Onde travar ou precisar de jargão, há uma lacuna: releia só essa parte.
3. Compare com a explicação-modelo e reescreva o que faltou.

Sua explicação

Fica salva neste navegador.

Comparar com uma explicação-modelo

A busca binária olha o item do meio e pergunta: o que procuro está antes ou depois? Como a lista está em ordem, a resposta permite jogar fora metade dos itens de uma vez. Um milhão vira meio milhão, depois 250 mil, e assim por diante. Dividindo um milhão pela metade umas 20 vezes, sobra um item só, por isso bastam cerca de 20 passos.

Se a lista estiver bagunçada, olhar o meio não diz nada sobre onde está o resto: o item procurado pode estar em qualquer das metades. Aí não dá para descartar nada, e o jeito é olhar um por um, a busca linear.

Teste-se

Mais duas questões deste tópico estão em Questões.

Flashcards gerados

Ligação com o estudo de caso

Num caso sobre desempenho de um sistema, justifique a escolha da estrutura pela operação mais frequente: busca por chave pede hash ou índice; atendimento por ordem de chegada pede fila; dados que precisam sair ordenados pedem árvore ou ordenação O(n log n). Mostrar a complexidade (de O(n²) para O(n log n), por exemplo) é o argumento técnico que a banca espera.

Fontes da lição

• Edital nº 01/2026, Anexo II, Desenvolvimento de Sistemas (fontes/edital-01-2026.txt).
• Thomas Cormen e outros, Algoritmos: teoria e prática (complexidade, ordenação, árvores e tabelas hash).
• Nivio Ziviani, Projeto de algoritmos (estruturas de dados e pesquisa em memória).