← DCC205 · Estruturas de Dados
DCC205 · Estruturas de Dados · 2026/2

Análise de algoritmose função de custo

Aula 01, terceira parte. Como medir o custo de um algoritmo sem executá-lo: o modelo RAM, a função de complexidade \(f(n)\), e os três casos — melhor, pior e médio. No fim, o movimento que se repete em toda a disciplina: analisar um algoritmo dá um teto; analisar a classe inteira dá um piso; quando os dois coincidem, o algoritmo é ótimo e a busca acabou.

Aulas cobertas: A1 · parte 3 do slide Referência: CLRS, cap. 1 e seção 2.2 Atualizado: 25/08/2026
Parte 1Medir o custo sem executar
A1 · 01

As duas perguntas do projeto de algoritmos

Ao projetar um algoritmo — análise do problema, decisões de projeto, tipos abstratos de dados — duas perguntas dominam:

Definição
  1. O algoritmo funciona? (correção)
  2. O algoritmo é eficiente? (custo)

A eficiência pode ser medida em várias métricas — tempo de execução, espaço ocupado. O estudo dessas medidas é a Análise de Algoritmos, e é a ferramenta usada em todos os outros módulos do curso.

A1 · 02

Dois tipos de análise

A palavra “análise” cobre duas perguntas bem diferentes. Confundi-las é o erro que mais atrapalha na hora de ler um enunciado de prova.

De um algoritmo particular

Qual é o custo de usar um dado algoritmo?

  • quantas vezes cada parte executa;
  • quanta memória as estruturas usam.
De uma classe de algoritmos

Qual é o menor custo possível para resolver o problema?

  • investiga-se toda a família de algoritmos;
  • estabelece-se um limite inferior.

Esta aula faz as duas — e elas se encontram duas vezes: no tópico 09, com o \(\mathrm{Max}\), e no tópico 20, com o \(\mathrm{MaxMin3}\).

A1 · 03

Cronometrar ou modelar

Há duas maneiras de medir o custo:

  1. Medir pela execução: rodar o programa e cronometrar.
  2. Modelo matemático: contar operações num computador idealizado.
Por que cronometrar, em geral, não basta
  • os resultados dependem do compilador;
  • dependem do hardware;
  • com muita memória em uso, o tempo pode depender disso também.
Medir não é inútilCronometrar é a ferramenta certa em dois casos: comparar algoritmos de mesma ordem de custo, e observar o comportamento no ambiente real, onde há custos invisíveis ao modelo — alocação, indexação, carga de dados.
A1 · 04

O computador idealizado: modelo RAM

Definição · CLRS, seção 2.2

RAM — Random Access Machine:

  • um processador; instruções executadas uma após a outra, sem concorrência;
  • instruções encontradas em computadores reais, cada uma de custo constante: aritméticas (soma, produto, resto, piso, teto), movimentação de dados (load, store, cópia) e controle (desvios, chamada de sub-rotina);
  • não modela a hierarquia de memória — cache, memória virtual.
Por que o modelo precisa de disciplinaSe a RAM tivesse uma instrução ordenar, ordenaríamos em um passo — e o modelo não diria nada sobre o mundo. Ele só é útil porque espelha máquinas reais. Na prática, análises no modelo RAM preveem muito bem o desempenho real.
A1 · 05

O que contar, e o que é \(n\)

Mesmo dentro do modelo RAM, ninguém conta tudo. É usual ignorar o custo da maioria das operações e contar apenas as mais significativas.

Em ordenação, por exemplo, contam-se as comparações entre elementos e ignoram-se aritmética e manipulação de índices.

Tamanho da entrada · CLRS, seção 2.2

O que é \(n\) depende do problema:

ProblemaTamanho da entrada
ordenaçãonúmero de itens do vetor
multiplicação de inteirosnúmero de bits
grafosvértices e arestas — dois números
A1 · 06

A função de complexidade \(f(n)\)

Definição

O custo de execução de um algoritmo é dado por uma função de complexidade \(f\), onde \(f(n)\) é a medida do custo para um problema de tamanho \(n\).

  • Tempo: \(f(n)\) conta operações relevantes executadas.
  • Espaço: \(f(n)\) mede a memória necessária.
O erro de leitura mais comum\(f(n)\) não mede segundos. Mede quantas vezes a operação relevante executa. Por isso “\(f(n)=n-1\)” é uma resposta completa, sem unidade nenhuma.
Parte 2Primeiro algoritmo: o maior elemento
A1 · 07

Max — contando as comparações

Problema: encontrar o maior elemento de um vetor de inteiros A[n], \(n \ge 1\).

Maxuma varredura
  1. int Max(int *A, int n) {
  2. int i, temp;
  3. temp = A[0];
  4. for (i = 1; i < n; i++)
  5. if (temp < A[i])
  6. temp = A[i];
  7. return temp;
  8. }
Exemplo · a contagem

Seja \(f(n)\) o número de comparações entre elementos de A.

  • O laço executa para \(i = 1, 2, \dots, n-1\): são \(n-1\) iterações.
  • Cada iteração faz 1 comparação (temp < A[i]).
$$f(n) = n - 1$$

para o melhor caso, o pior caso e o caso médio — a organização da entrada não muda a contagem.

A1 · 08

Dá para fazer melhor? O limite inferior

Teorema

Qualquer algoritmo para encontrar o maior elemento de um conjunto com \(n\) elementos, \(n \ge 1\), faz pelo menos \(n-1\) comparações.

Prova

O que determina que um elemento é o maior? O fato de todos os outros serem menores do que ele.

Cada um dos outros \(n-1\) elementos precisa ser testado — por comparação — contra algum elemento. Logo, \(n-1\) comparações são necessárias. \(\blacksquare\)

Leia o quantificadorO teorema fala de qualquer algoritmo — é uma análise da classe, não de um algoritmo particular. Nenhuma linha de código foi examinada para chegar nele.
A1 · 09

Algoritmo ótimo

Definição

Quando o custo de um algoritmo é igual ao menor custo possível da classe, o algoritmo é ótimo para essa medida de custo.

Aplicando ao Max
  • \(\mathrm{Max}\) faz \(n-1\) comparações.
  • O teorema diz: ninguém faz menos que \(n-1\).

Logo \(\mathrm{Max}\) é ótimo em número de comparações.

Guarde o método: analisar o algoritmo dá um teto; analisar a classe dá um piso; quando os dois coincidem, acabou a busca. A Parte 5 repete isso com um problema mais rico.

Parte 3Quando a entrada muda o custo
A1 · 10

Melhor, pior e caso médio

Para alguns algoritmos, o custo depende não só do tamanho, mas da organização da entrada. Definimos então:

Definição
  • Melhor caso: menor custo sobre todas as entradas de tamanho \(n\).
  • Pior caso: maior custo sobre todas as entradas de tamanho \(n\). Se \(f\) é do pior caso, o custo real nunca passa de \(f(n)\) — é uma garantia.
  • Caso médio: média dos custos sobre todas as entradas de tamanho \(n\), ponderada por uma distribuição de probabilidades — em geral o mais difícil de calcular.
A1 · 11

Pesquisa sequencial

Problema: dado um arquivo de registros com chaves únicas, localizar o registro com uma dada chave.

Pesquisaretorna a posição, ou n se ausente
  1. int Pesquisa(TipoRegistro *A, int n, int chave) {
  2. int i = 0;
  3. while (i < n) {
  4. if (A[i].chave == chave)
  5. break;
  6. i++;
  7. }
  8. return i;
  9. }
Melhor e pior caso

Contando comparações de chaves:

  • Melhor caso — a chave está no primeiro registro consultado: \(f(n) = 1\).
  • Pior caso — a chave está no último registro, ou não está no arquivo: \(f(n) = n\).
A1 · 12

O caso médio, passo a passo

Hipótese: toda pesquisa recupera um registro — pesquisa com sucesso.

Passo 1 · a soma ponderada

Seja \(p_i\) a probabilidade de o \(i\)-ésimo registro ser o procurado. Recuperá-lo custa \(i\) comparações, logo:

$$f(n) = 1\cdot p_1 + 2\cdot p_2 + \dots + n\cdot p_n = \sum_{i=1}^{n} i\,p_i$$
Passo 2 · a distribuição uniforme

Se toda chave é igualmente provável, \(p_i = \tfrac{1}{n}\), e a soma ponderada vira uma média simples:

$$f(n) = \frac{1}{n}\sum_{i=1}^{n} i$$
Passo 3 · fechar o somatório

Como \(\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}\):

$$f(n) = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}$$

Em média, percorre-se metade do arquivo — bate com a intuição.

A hipótese faz parte da respostaO \((n+1)/2\) só vale sob distribuição uniforme e sob pesquisa com sucesso. Mudou a distribuição, muda o caso médio — enquanto melhor e pior caso continuam \(1\) e \(n\). Numa prova, enunciar a hipótese vale ponto.
A1 · 13

Por que a prática privilegia o pior caso

Caso\(f(n)\)Quando ocorre
Melhor\(1\)chave no primeiro registro
Médio\((n+1)/2\)chaves equiprováveis (uniforme)
Pior\(n\)chave no último registro, ou ausente
Três razões · CLRS, seção 2.2
  • É uma garantia: o custo nunca passa dali.
  • O pior caso ocorre com frequência: buscar informação ausente é comum — e é justamente o pior caso da pesquisa.
  • O caso médio é, muitas vezes, tão ruim quanto o pior — mesma ordem de crescimento. Aqui, \((n+1)/2\) e \(n\) crescem igual.
Parte 4Maior e menor: três algoritmos
A1 · 14

MaxMin1 — a versão direta

Problema: encontrar o maior e o menor elemento de A[n], \(n \ge 1\).

MaxMin1dois testes por iteração
  1. void MaxMin1(int *A, int n, int *Max, int *Min) {
  2. int i;
  3. *Max = A[0]; *Min = A[0];
  4. for (i = 1; i < n; i++) {
  5. if (A[i] > *Max) *Max = A[i];
  6. if (A[i] < *Min) *Min = A[i];
  7. }
  8. }
Contagem

Duas comparações por iteração, \(n-1\) iterações:

$$f(n) = 2(n-1)$$

em todos os casos — melhor, médio e pior.

A1 · 15

MaxMin2 — o else que economiza

Observação: se A[i] > *Max, então A[i] não pode ser o novo mínimo. O segundo teste só é necessário quando o primeiro falha.

MaxMin2o segundo teste vira else
  1. void MaxMin2(int *A, int n, int *Max, int *Min) {
  2. int i;
  3. *Max = A[0]; *Min = A[0];
  4. for (i = 1; i < n; i++) {
  5. if (A[i] > *Max) *Max = A[i];
  6. else if (A[i] < *Min) *Min = A[i];
  7. }
  8. }
Os três casos
  • Melhor caso — vetor crescente: o 1º teste sempre passa, o 2º nunca executa. \(f(n) = n-1\)
  • Pior caso — maior elemento na 1ª posição, por exemplo vetor decrescente: o 1º teste sempre falha e o 2º sempre executa. \(f(n) = 2(n-1)\)
  • Caso médio — A[i] > *Max metade das vezes:
$$f(n) = \frac{3n}{2} - \frac{3}{2}$$
A1 · 16

MaxMin3 — comparar aos pares

A ideia muda: em vez de comparar cada elemento contra o máximo e o mínimo correntes, comparam-se os elementos entre si, aos pares. Cada par já separa um candidato a máximo de um candidato a mínimo.

10 30 5 68 12 67 par 1 par 2 par 3 30 · 68 · 67 10 · 5 · 12 Max = 68 Min = 5
O máximo só pode estar entre os vencedores dos pares; o mínimo, só entre os perdedores. Cada busca varre metade do vetor.
A contagem, em três parcelas
  • Comparar aos pares: \(\lceil n/2 \rceil\) comparações separam maiores de menores.
  • Máximo só entre os maiores: \(\lceil n/2 \rceil - 1\) comparações.
  • Mínimo só entre os menores: \(\lceil n/2 \rceil - 1\) comparações.
MaxMin3anel de dois em dois
  1. void MaxMin3(int n, Vetor A, int *Max, int *Min) {
  2. int i, FimDoAnel;
  3. if ((n % 2) > 0) { /* n impar */
  4. A[n] = A[n - 1]; /* duplica ultimo */
  5. FimDoAnel = n;
  6. } else FimDoAnel = n - 1;
  7. if (A[0] > A[1]) { *Max = A[0]; *Min = A[1]; }
  8. else { *Max = A[1]; *Min = A[0]; }
  9. i = 3;
  10. while (i <= FimDoAnel) {
  11. if (A[i - 1] > A[i]) {
  12. if (A[i - 1] > *Max) *Max = A[i - 1];
  13. if (A[i] < *Min) *Min = A[i];
  14. } else {
  15. if (A[i - 1] < *Min) *Min = A[i - 1];
  16. if (A[i] > *Max) *Max = A[i];
  17. }
  18. i += 2;
  19. }
  20. }
Custo total

Com \(n\) par, uma comparação por par mais duas atualizações por par processado:

$$f(n) = \frac{n}{2} + 2\left(\frac{n}{2} - 1\right) = \frac{3n}{2} - 2$$

para melhor, pior e caso médio — a estrutura do anel não depende da organização da entrada.

Por que duplicar o último elementoCom \(n\) ímpar sobraria um elemento sem par. Copiar A[n-1] em A[n] cria um par artificial e evita um tratamento de exceção dentro do laço — o elemento duplicado não altera nem o máximo nem o mínimo.
A1 · 17

O quadro comparativo

Número de comparações dos três algoritmos:

MelhorMédioPior
MaxMin1\(2(n-1)\)\(2(n-1)\)\(2(n-1)\)
MaxMin2\(n-1\)\(\tfrac{3n}{2}-\tfrac{3}{2}\)\(2(n-1)\)
MaxMin3\(\tfrac{3n}{2}-2\)\(\tfrac{3n}{2}-2\)\(\tfrac{3n}{2}-2\)

MaxMin3 vence no pior caso e empata praticamente no médio. Fica a pergunta inevitável: existe algoritmo ainda melhor? Qual é o limite inferior desta classe?

Parte 5O oráculo e o limite inferior
A1 · 18

A ideia do oráculo

Definição · oráculo, ou adversário

Dado um modelo de computação, o oráculo responde cada comparação do algoritmo da pior forma possível — escolhendo o resultado que force o maior trabalho restante.

Se mesmo contra o oráculo um custo \(C\) é inevitável, então nenhum algoritmo da classe faz menos que \(C\).

Teorema

Qualquer algoritmo para encontrar o maior e o menor elemento de um conjunto não ordenado com \(n\) elementos, \(n > 1\), faz pelo menos \(\tfrac{3n}{2}-2\) comparações.

A1 · 19

A prova: estados como 4-tuplas

O truque da prova é descrever o conhecimento do algoritmo — não o seu código — por uma 4-tupla \((a,b,c,d)\).

O que cada componente conta
ComponenteElementos que…Papel
\(a\)nunca foram comparadosainda indefinidos
\(b\)só venceram comparaçõescandidatos a máximo
\(c\)só perderam comparaçõescandidatos a mínimo
\(d\)já venceram e perderamintermediários, fora da disputa

Estado inicial: \((n,0,0,0)\) — ninguém foi comparado.
Estado final: \((0,1,1,n-2)\) — um máximo, um mínimo, o resto fora.

O que uma única comparação pode fazer
Quem se comparaNovo estadoProgresso
2 elementos de \(a\)\((a-2,\,b+1,\,c+1,\,d)\)2 saem de \(a\)
1 de \(a\) com 1 de \(b\) ou \(c\)\((a-1,\,b+1,\,c,\,d)\), \((a-1,\,b,\,c+1,\,d)\) ou \((a-1,\,b,\,c,\,d+1)\)1 sai de \(a\)
2 elementos de \(b\)\((a,\,b-1,\,c,\,d+1)\)1 sai de \(b\)
2 elementos de \(c\)\((a,\,b,\,c-1,\,d+1)\)1 sai de \(c\)
Onde está o oráculoNas linhas com mais de um estado possível, quem escolhe é o oráculo — sempre o resultado que mais atrasa o algoritmo. Só a primeira linha esvazia \(a\) em ritmo de 2 por comparação; é por isso que ela é a jogada mais eficiente disponível.
A1 · 20

O caminho mais barato — e por que MaxMin3 é ótimo

O melhor que o algoritmo consegue é o caminho mais barato de \((n,0,0,0)\) até \((0,1,1,n-2)\):

( n, 0, 0, 0 ) n/2 · pares em a ( 0, n/2, n/2, 0 ) n/2 − 1 · máximo em b ( 0, 1, n/2, n/2 − 1 ) n/2 − 1 · mínimo em c ( 0, 1, 1, n − 2 )
Três trechos: esvaziar a aos pares, achar o máximo dentro de b, achar o mínimo dentro de c.
Somando os três trechos $$f(n) = \frac{n}{2} + \left(\frac{n}{2} - 1\right) + \left(\frac{n}{2} - 1\right) = \frac{3n}{2} - 2$$
Conclusão
  • O limite \(\tfrac{3n}{2}-2\) foi obtido sem analisar algoritmo algum — é uma propriedade do problema.
  • MaxMin3 atinge exatamente \(\tfrac{3n}{2}-2\) comparações.
  • Logo MaxMin3 é ótimo: não adianta procurar algoritmo melhor nesta medida de custo.

É o padrão da aula pela segunda vez: análise do algoritmo dá o teto, análise da classe dá o piso, e teto \(=\) piso encerra a busca.

FechoCobertura e checklist
A1 · Cobertura

Até onde vai este resumo

O slide da Aula 01 tem três partes. Este resumo cobre apenas a terceira — a que a prova cobra.

Parte do slideSituação
Parte 1 — A disciplina (definições de algoritmo e estrutura de dados, abstração, ementa, avaliação, bibliografia)fora deste resumo
Parte 2 — Programação na era da IA (LLMs, vibe coding, estudos Anthropic / DORA / GitClear / METR, o guia de 4 fases)fora deste resumo
Parte 3 — Análise de complexidade (modelo RAM, \(f(n)\), três casos, Max, pesquisa sequencial, MaxMin1–3, oráculo)coberta, do início ao fim

As duas primeiras partes são de enquadramento: regras da disciplina e discussão sobre uso de IA. Nada ali entra em prova como conteúdo técnico. O único item das partes 1–2 que sobrevive como conteúdo é o duelo do CLRS — mergesort numa máquina 1000× mais lenta ganha da ordenação por inserção — e ele já reaparece na A2, quando a ordem de crescimento é formalizada.

Revisão

Checklist da A1

Se você consegue responder tudo abaixo sem consultar, a aula está fechada.

PerguntaOnde está
Distinguir análise de um algoritmo particular de análise de uma classeDois tipos de análise
Dar três razões pelas quais cronometrar não substitui o modeloCronometrar ou modelar
Dizer o que a máquina RAM assume e o que ela deliberadamente ignoraO modelo RAM
Escolher a operação relevante e dizer o que é \(n\) num problema dadoO que contar
Explicar por que \(f(n)\) não tem unidade de tempoA função de complexidade
Contar as comparações do Max e concluir \(f(n)=n-1\)Max
Provar que nenhum algoritmo acha o máximo com menos de \(n-1\) comparaçõesO limite inferior
Definir algoritmo ótimo e justificar que o Max é ótimoAlgoritmo ótimo
Definir melhor, pior e caso médio, e dizer qual deles é uma garantiaMelhor, pior e caso médio
Exibir a entrada de melhor e a de pior caso da pesquisa sequencialPesquisa sequencial
Deduzir \((n+1)/2\) a partir de \(\sum i\,p_i\), enunciando a hipótese usadaO caso médio
Dar as três razões para privilegiar o pior casoPor que a prática usa o pior caso
Contar as comparações de MaxMin1 e dizer por que os três casos coincidemMaxMin1
Exibir a entrada de melhor e a de pior caso do MaxMin2, com a contagemMaxMin2
Descrever a estratégia dos pares e as três parcelas de \(\tfrac{3n}{2}-2\)MaxMin3
Explicar por que MaxMin3 duplica o último elemento quando \(n\) é ímparMaxMin3
Explicar o que o oráculo faz e por que ele produz um limite inferiorA ideia do oráculo
Dizer o que \(a\), \(b\), \(c\) e \(d\) contam, e os estados inicial e finalA prova por 4-tuplas
Somar os três trechos do caminho mais barato e chegar a \(\tfrac{3n}{2}-2\)O caminho mais barato
Concluir que MaxMin3 é ótimo, dizendo qual é o teto e qual é o pisoO caminho mais barato