Algoritmos e Estrutura de Dados Avançados

Unidade: U1 Fundamentos de Algoritmos

Aula: A1_ Introdução à Análise e Projeto de Algoritmos

OBJETIVOS Definição dos objetivos da aula prática: Compreender os conceitos de complexidade assintótica (notações Big-O, Big-Ω, Big-Θ). Implementar algoritmos simples em linguagem C para observar seu comportamento com diferentes entradas. Medir o tempo de execução dos algoritmos em diferentes cenários. Relacionar o tempo de execução à análise teórica de complexidade.

SOLUÇÃO DIGITAL: OnlineGDB LINK SOLUÇÃO DIGITAL (EXCETO ALGETEC): https://www.onlinegdb.com/online_c_compiler

PROCEDIMENTOS PRÁTICOS E APLICAÇÕES

Procedimento/Atividade nº 1 Comparação de Complexidade Algorítmica Atividade proposta: 1. Execute e analise os algoritmos abaixo para entender as diferenças de desempenho entre eles: 2. Crie um algoritmo que imprime os números de 1 até N (complexidade O(n)). 3. Crie um algoritmo que imprime todos os pares de números entre 1 e N (complexidade O(n²)). 4. Crie um algoritmo recursivo de fatorial (complexidade O(n)). 5. Meça o tempo de execução dos algoritmos com diferentes valores de N e compare os resultados. 3 Público Procedimentos para a realização da atividade: 1. Acesse o site https://www.onlinegdb.com/online_c_compiler e escolha a linguagem C. 2. Crie um código para cada um dos algoritmos propostos. 3. Use a biblioteca time.h para medir o tempo de execução. 4. Execute cada algoritmo para os valores de entrada: N = 10, 100, 1000 (conforme aplicável). 5. Documente suas observações e compare com a análise teórica de complexidade. Avaliando os resultados: 1) Qual algoritmo tem maior tempo de execução? 2) O comportamento observado se alinha à análise de complexidade? 3) Qual a importância de escolher algoritmos eficientes? 4) Como o tempo cresce à medida que N aumenta? Checklist: ✓ Algoritmos implementados com sucesso. ✓ Tempo de execução foi medido com time.h. ✓ Resultados foram registrados e comparados. ✓ Relatório final entregue com respostas e reflexão.

RESULTADOS Resultados do experimento: Você deverá enviar um arquivo .doc ou .pdf com: Prints ou trechos do código utilizado. Tabelas ou gráficos com os tempos de execução. Análise textual comparando o desempenho dos algoritmos. Conclusão sobre a importância da complexidade assintótica. Referências, se houver. O arquivo não pode exceder o tamanho de 2Mb. Resultados de Aprendizagem: 4 Público Entender e aplicar as noções de complexidade assintótica. Medir desempenho empírico de algoritmos simples. Relacionar teoria da ciência da computação com prática em linguagem C.