Aplicações Informáticas B · 12.º Ano · Algoritmia e Estruturas de Dados · 1o Periodo

Introdução à Complexidade Algorítmica

Os alunos aprendem a analisar a eficiência de algoritmos em termos de tempo e espaço, usando a notação Big O.

• Aprendizagens Essenciais
• DGE: Secundário - Algoritmia e Programação
• DGE: Secundário - Pensamento Computacional

Sobre este tópico

A complexidade algorítmica foca na análise da eficiência de algoritmos quanto ao tempo e espaço de execução, com recurso à notação Big O. Os alunos do 12.º ano classificam algoritmos como O(1), O(n), O(n log n) ou O(n²), entendendo como o tamanho da entrada influencia o desempenho. Esta abordagem permite prever o comportamento em conjuntos de dados grandes, essencial para programação prática.

No Currículo Nacional, este tema pertence à unidade de Algoritmia e Estruturas de Dados, alinhando-se aos standards de Algoritmia e Programação e Pensamento Computacional. Os alunos avaliam a relevância da Big O para escalabilidade, analisam o contributo de operações básicas na complexidade total e preveem efeitos de algoritmos ineficientes em aplicações reais, como motores de busca ou redes sociais.

A aprendizagem ativa beneficia este tema porque os alunos podem implementar e cronometrar algoritmos em pares, gerar gráficos de desempenho e debater otimizações em grupo. Estas atividades tornam conceitos abstractos mensuráveis, promovem a experimentação iterativa e desenvolvem competências de análise crítica através de comparações directas.

Questões-Chave

1. Avalie a importância da notação Big O para prever o comportamento de algoritmos em larga escala.
2. Analise como diferentes operações básicas contribuem para a complexidade de um algoritmo.
3. Preveja o impacto de um algoritmo ineficiente no desempenho de uma aplicação real.

Objetivos de Aprendizagem

• Classificar algoritmos com base na sua complexidade temporal usando a notação Big O (O(1), O(n), O(n log n), O(n²)).
• Calcular a complexidade temporal de algoritmos simples, identificando as operações dominantes.
• Comparar a eficiência de diferentes algoritmos para resolver o mesmo problema, justificando a escolha com base na notação Big O.
• Explicar o impacto do aumento do tamanho da entrada no tempo de execução de algoritmos com diferentes ordens de complexidade.
• Avaliar a escalabilidade de um algoritmo, prevendo o seu desempenho em cenários com grandes volumes de dados.

Antes de Começar

Conceitos Fundamentais de Algoritmos

Porquê: Os alunos precisam de compreender o que é um algoritmo e como expressar uma sequência de passos para resolver um problema antes de analisar a sua eficiência.

Estruturas de Controlo (Ciclos e Condicionais)

Porquê: A análise da complexidade temporal depende da compreensão de como os ciclos (como `for` e `while`) e as instruções condicionais afetam o número de operações executadas.

Noções Básicas de Análise Matemática

Porquê: Uma compreensão básica de funções e taxas de crescimento é útil para entender como a notação Big O descreve o comportamento de algoritmos em relação ao tamanho da entrada.

Vocabulário-Chave

Notação Big O	Uma notação matemática usada para descrever o limite superior do tempo de execução ou do espaço de memória de um algoritmo em função do tamanho da entrada. Indica como o desempenho escala.
Complexidade Temporal	A medida do tempo que um algoritmo leva para ser executado, geralmente expresso em função do número de operações realizadas em relação ao tamanho da entrada.
Complexidade Espacial	A medida da quantidade de memória que um algoritmo utiliza durante a sua execução, também expressa em função do tamanho da entrada.
Ordem de Complexidade	A classificação da taxa de crescimento do tempo de execução ou do espaço de memória de um algoritmo, como O(1) para tempo constante, O(n) para tempo linear, O(n²) para tempo quadrático, etc.
Operação Dominante	A operação dentro de um algoritmo que mais contribui para o tempo total de execução à medida que o tamanho da entrada aumenta. É crucial para determinar a complexidade Big O.

Atenção a estes erros comuns

Erro comum

A notação Big O mede o tempo exato de execução de um algoritmo.

O que ensinar em alternativa

Big O descreve o crescimento assintótico no pior caso, ignorando constantes e hardware específico. Actividades de cronometragem em grupos revelam variações reais, ajudando os alunos a distinguir teoria de prática através de comparações empíricas.

Erro comum

Complexidade de tempo e espaço são sempre iguais num algoritmo.

O que ensinar em alternativa

Tempo foca em operações, espaço em memória alocada; um algoritmo pode ser rápido mas guloso em memória. Experiências com recursão em pares mostram trade-offs, fomentando discussões que clarificam estas distinções.

Erro comum

Algoritmos mais simples têm sempre menor complexidade.

O que ensinar em alternativa

Simplicidade sintáctica não implica eficiência assintótica. Simulações colectivas de loops aninhados versus estruturas eficientes ajudam os alunos a analisar contribuições operacionais, corrigindo esta visão superficial.

Ideias de aprendizagem ativa

Comparação Prática: Bubble Sort vs Insertion Sort

Divida a turma em grupos pequenos. Cada grupo implementa os dois algoritmos em Python para ordenar listas de tamanhos crescentes (10 a 1000 elementos). Cronometre a execução e registe os tempos. Discuta os resultados num gráfico partilhado.

45 min·Pequenos grupos

Gráficos de Big O: Simulação Individual

Os alunos criam funções para O(n) e O(n²) com loops aninhados. Executam com entradas variadas, medem tempos e plotam curvas em Excel ou Google Sheets. Partilham os gráficos na aula.

30 min·Individual

Análise em Pares: Otimização de Pesquisa

Em pares, implementem busca linear e binária. Testem com listas ordenadas de 100 a 10 000 elementos, registem complexidades e expliquem diferenças na notação Big O.

35 min·Pares

Debate Coletivo: Impacto Real

Apresente cenários de aplicações reais. A turma discute em roda o impacto de O(n²) vs O(n log n) em big data, votando em soluções otimizadas.

40 min·Turma inteira

Ligações ao Mundo Real

• Engenheiros de software em empresas como a Google utilizam a análise de complexidade algorítmica para otimizar motores de busca e sistemas de recomendação, garantindo respostas rápidas mesmo com biliões de pesquisas diárias.
• Cientistas de dados analisam a complexidade de algoritmos de machine learning para prever o tempo e os recursos computacionais necessários para treinar modelos em grandes conjuntos de dados, como os usados em aplicações de reconhecimento facial.
• Desenvolvedores de jogos avaliam a complexidade de algoritmos de inteligência artificial para personagens não jogáveis, assegurando que o desempenho do jogo permaneça suave e responsivo em consolas e PCs.

Ideias de Avaliação

Verificação Rápida

Apresente aos alunos um pequeno trecho de código (ex: um ciclo for aninhado). Peça-lhes para identificar a operação dominante e determinar a complexidade Big O do algoritmo, escrevendo a resposta numa folha. Verifique as respostas para identificar dificuldades comuns.

Questão para Discussão

Coloque a seguinte questão para discussão em pequenos grupos: 'Se um algoritmo tem complexidade O(n log n) e outro tem O(n²), qual deles será mais eficiente para um conjunto de dados com 1 milhão de elementos? Justifiquem a vossa resposta com base no comportamento esperado destas ordens de complexidade.'

Bilhete de Saída

Distribua um cartão a cada aluno com um algoritmo descrito (sem código explícito, apenas a lógica). Peça-lhes para escreverem a ordem de complexidade Big O esperada para o tempo de execução e uma frase explicando porquê. Recolha os cartões à saída da sala.

Perguntas frequentes

Como analisar complexidade com notação Big O?

Identifique a operação dominante no pior caso e conte como função do tamanho n da entrada. Por exemplo, dois loops aninhados dão O(n²). Pratique com pseudocódigo, depois implemente e teste para validar previsões teóricas em cenários reais.

Qual a importância da Big O em programação real?

Permite prever escalabilidade: um O(n²) falha em milhões de dados, enquanto O(n log n) suporta. Em apps como redes sociais, optimizações evitam crashes e melhoram experiência do utilizador, guiando escolhas de algoritmos.

Como a aprendizagem activa ajuda na complexidade algorítmica?

Actividades como cronometrar algoritmos em grupos tornam Big O tangível: alunos medem tempos reais, plotam curvas e debatem trade-offs. Esta experimentação iterativa corrige intuições erradas, fomenta colaboração e liga teoria a prática, melhorando retenção e pensamento computacional.

Quais operações básicas afectam mais a complexidade?

Atribuições são O(1), loops simples O(n), aninhados O(n²). Some contribuições: se um loop n processa uma operação O(n), totaliza O(n²). Análises passo a passo em exercícios guiados revelam dominantes, preparando para optimizações avançadas.