Algoritmos 2Revisão em C

Caderno de estudo

Algoritmos 2

Uma revisão para entender o código, acompanhar sua execução e resolver problemas novos, inclusive os difíceis.

Começamos pela organização dos dados (struct) e pela memória (ponteiros). Em seguida, vem recursão, a ferramenta para pensar em problemas menores. Por fim, comparamos três ordenações e vemos o que cada uma ensina sobre invariantes, inversões e custo.

Ideia-chave

Caixas azuis trazem o que você precisa levar para a prova.

Armadilhas

Caixas laranja mostram os erros que mais derrubam código em C.

Exercícios em níveis

Básico, intermediário e avançado, com dica e resposta.

$ hacker

Perto do fim de cada aula há um desafio difícil e opcional, com solução comentada.

Encontrou uma palavra nova, como invariante, inversão, aliasing ou memoização? Todas estão explicadas no glossário, em uma ou duas frases.

Percurso da revisão

  1. Struct o laboratório com dois professores

    Registros, cópia, passagem para funções e regras de comparação.

    Abrir aula

  2. Ponteiros o swap mágico

    Endereços, aritmética de ponteiros, vetores e aliasing.

    Abrir aula

  3. Funções recursivas o cofre das somas

    Caso base, pilha de chamadas, pastas, busca binária e, como aprofundamento, memoização e backtracking.

    Abrir aula

  4. Bubble sort o juiz que conta trocas

    Trocas entre vizinhos, inversões e parada antecipada.

    Abrir aula

  5. Insertion sort o sensor quase ordenado

    Prefixo ordenado, deslocamentos e vetores quase ordenados.

    Abrir aula

  6. Selection sort o robô do armazém

    Seleção do menor, mínimo de trocas e estabilidade.

    Abrir aula

Método para resolver problemas de algoritmos

Programadores experientes raramente “veem” a solução de imediato. Eles seguem um roteiro. Use este em todos os exercícios e desafios:

  1. Entenda a entrada e a saída. Quais são os tipos, tamanhos e limites? Reescreva o enunciado com suas palavras e resolva um exemplo pequeno à mão.
  2. Comece pela força bruta. Qual é a solução mais simples que funciona, mesmo que lenta? Ela serve de referência para testar a solução final.
  3. Estime o custo e compare com o limite. Faça a conta: com n = 10⁵, n² = 10¹⁰ operações; 10¹⁰ ÷ 10⁸ por segundo ≈ 100 segundos. Já n log₂ n = 10⁵ × 17 ≈ 1,7 × 10⁶; ÷ 10⁸ ≈ 0,02 segundo. Como regra de bolso, um computador comum faz da ordem de 10⁸ operações simples por segundo. Com n = 10⁵, um algoritmo que cresce como n² faz da ordem de 10¹⁰ operações e não passa. Um que cresce como n log₂ n faz cerca de 1,7 × 10⁶ e passa com folga. É uma estimativa: memória, entrada e saída e o custo real de cada operação mudam o resultado.
  4. Procure estrutura. Há um invariante (algo que continua verdadeiro a cada passo)? O problema se divide em subproblemas menores? A entrada já vem quase ordenada? Existe uma medida, como inversões (pares fora de ordem) ou ciclos, que conta o trabalho?
  5. Escreva e argumente. Para laços, use invariantes. Para recursão, use caso base mais indução. Explicar por que funciona ajuda a encontrar os casos que ainda precisam ser testados.
  6. Teste as bordas. Vetor vazio, um elemento, todos iguais, já ordenado, ordem inversa, valores negativos e limites do tipo: um int de 32 bits vai só até cerca de 2,1 bilhões, então somas e contagens maiores pedem long long. Compare com a força bruta em entradas aleatórias.
Três perguntas que destravam quase tudo
  • O que fica garantido depois de cada iteração? (invariante)
  • Se eu soubesse a resposta para um problema menor, conseguiria montar a do maior? (recursão)
  • Estou recalculando alguma coisa? (memoização: guardar resultados já calculados para não refazer)

Complexidade em uma página

A notação O descreve como o custo cresce com n, ignorando constantes. Na prática, ela responde: se n ficar 1000 vezes maior, um algoritmo O(n) fica cerca de 1000 vezes mais lento, e um O(n²), cerca de 1 milhão de vezes.

O símbolo log₂ n é quantas vezes dá para dividir n ao meio até chegar a 1. Para 1 000 000, são uns 20 cortes, por isso log₂ n cresce muito devagar.

Ordens de crescimento comuns e uma estimativa grosseira do n que cabe em cerca de 1 segundo
OrdemNomeExemplo nesta revisãon viável (estimativa)
O(1)constanteacessar v[i], p->notao custo não depende de n
O(log n)logarítmicabusca bináriamuito grande: o limite vem da memória, não do tempo
O(n)linearmédia de notas, contar ciclos (desafio do selection sort)até ~10⁸
O(n log n)linearítmicamerge sort, contar inversões (desafio do bubble sort)10⁶ (10⁷ já passa do orçamento)
O(n²)quadráticabubble, insertion, selectionaté ~10⁴
O(2ⁿ)exponencialgerar todos os subconjuntos≈ 25 (imprimir cada subconjunto custa ainda mais)
≈ O(1,6ⁿ)exponencial, um pouco mais lentaFibonacci ingênuo≈ 35 a 40
Regras práticas
  • Laços aninhados que percorrem tudo multiplicam os custos. Laços em sequência somam, e vale o maior.
  • Se cada etapa descarta metade das possibilidades e faz trabalho constante, como na busca binária, são cerca de log₂ n etapas. Se resolve as duas metades e ainda percorre tudo para juntar, como o merge sort, o total cresce como n log n.
  • Os números da tabela são estimativas para ter ordem de grandeza, não garantias: dependem da máquina, do compilador e dos dados.
  • Melhor caso, pior caso e caso médio são perguntas diferentes. Diga sempre de qual está falando.

Como estudar

Em cada aula, leia o problema inicial e proponha uma solução antes da teoria. Nos exemplos, preveja a saída antes de executar. Nos exercícios, tente primeiro e abra a dica só quando travar. Abra a resposta só depois de ter uma resposta sua.

Os desafios hacker são opcionais e vão além da aula. Para cada um:

  1. Tente por 30 minutos antes de abrir qualquer dica.
  2. Abra uma dica por vez e tente de novo antes de passar à seguinte.
  3. Depois de ler a solução, reescreva-a do zero, sem consultar, e teste contra uma força bruta.

Partes marcadas com Aprofundamento também são opcionais: estude primeiro o núcleo da aula.