Trabalho sobre Algoritimos

Análise de Complexidade do Problema dos Números Ímpares Marco A S Mangan Escola Politécnica Pontifícia Universidade Católica do Rio Grande do Sul PUCRS Avenida Ipiranga 6681 Prédio 30 Bloco C Sala 101 CEP 90619900 Porto Alegre RS Brasil marcomanganpucrsbr Abstract Complexity analysis determines algorithm behavior using BigO notation This paper problem complexity of Even Number problems is determined as On ie a linear behavior as the value of n increases In order to determinate the complexity the following results were obtained a an algorithm b a computer program c program validation d algorithm analysis and e operation count of different program executions Data from operation counting confirm the initial analysis Resumo A análise de complexidade determina o comportamento de um algoritmo em notação O Neste texto a complexidade do problema Números Ímpares é determinada como On ou seja como um comportamento linear a medida que o valor de n aumenta Para determinar a complexidade foram desenvolvidos a um algoritmo b um programa c validação do programa d análise do algoritmo e e contagem de operações sobre diferentes execuções do programa Os dados da contagem confirmam a análise realizada 1 Introdução A análise de algoritmos está relacionada com o consumo de recursos pela execução de um programa em geral memória ou processador A descrição do problema dos Números Ímpares é apresentada no Beecrowd BEECROWD 2023 O objetivo deste trabalho é determinar a classe de complexidade de uma solução do problema em notação O O restante deste trabalho está organizado como segue A Seção 2 apresenta o método adotado A Seção 3 apresenta o algoritmo desenvolvido e a análise de sua complexidade A Seção 4 apresenta uma implementação do algoritmo em linguagem Java e a validação desse algoritmo junto ao Beecrowd A Seção 5 apresenta uma modificação do programa que apresenta uma contagem de operações realizadas para diferentes valores de n 2 Método Para elaborar o algoritmo foi analisada a descrição do problema e um algoritmo foi descrito diretamente a partir do enunciado A variável de entrada n representa o tamanho do problema Pode se notar que quanto maior o valor de n maior o número de valores a serem apresentados e portanto o número de operações a ser executado Do algoritmo foi escrito um programa em Java que permite a entrada de um valor de n conforme solicitado no enunciado do problema O programa foi enviado ao Beecrowd para validar a correção do programa implementado Em seguida o programa foi alterado para permitir a coleta de diferentes números de operações executadas para diferentes valores de n Os dados coletados foram organizados em uma tabela e um gráfico foi elaborado para obter uma confirmação visual da reta característica de um comportamento linear simples On 3 O Algoritmo O problema apresenta ao menos duas variações conhecidas Primeiro o problema de apresentar todos os números inteiros de 1 até n Esta variação tem complexidade On Segundo o problema da soma dos números inteiros de 1 até n Esta variação tem uma implementação iterativa em On e outra implementação com fórmula fechada em O1 A fórmula fechada não se aplica caso pela necessidade de apresentar cada um dos valores O algoritmo pode ser apresentado em poucas linhas ÍMPARESn 1 for i 1 to n 2 if i é ímpar 3 then mostrar i No problema dos números ímpares esperase que n2 números sejam ímpares no intervalo 1 n indicando uma complexidade de On Uma otimização pode ser estabelecida evitando o condicional ÍMPARESPLUSn 1 for i 1 to n step 2 2 mostrar i Esta segunda revisão permanece com uma complexidade de On apesar das melhorias 4 O Programa A implementação de um programa deve atender ao requisito de entrada via teclado e demais exigências da avaliação automática pelo Beecrowd 1 import javautilScanner 2 3 public class Main 4 public static void mainString args 5 Scanner in new ScannerSystemin 6 int x innextInt 7 for int i 1 i x i2 8 Systemoutprintlni 9 10 inclose 11 12 A avaliação pelo Beecrowd confirma o cálculo e apresentação correta da saída esperada Figura 1 Figura 1 O resultado da avaliação do programa no Beecrowd Com a confirmação da correção do programa a etapa a seguir é obter uma contagem de operações para confirmar a análise inicial 5 A Contagem Para realizar a instrumentação da contagem foi criado um segundo programa que coleta dados da execução para diferentes valores de entrada entre 1 e 1000 1 X 1000 Para determinar a complexidade foram utilizados somente valores entre 1 e 10 usando um comando for O programa recebeu uma variável adicional op que é incrementada na linha onde ocorre a saída para determinar quantas vezes a linha é repetida para diferentes valores de x Os dados coletados indicam uma escada ascendente similar a que indicaria um comportamento logarítmico Tabela 1 Entretanto um comportamento logarítmico apresentaria degraus com larguras crescentes O comportamento confirma On com uma equação como opn n1 2 Uma confirmação ocorre ao tentar ajustar uma linha de tendência para uma equação linear e outra linha de tendência para uma equação logarítmica Figura 2 O ajuste da equação linear é melhor 09697 O cálculo da equação não conseguiu obter a equação proposta que apresentaria ajuste perfeito 10000 Tabela 1 Os dados coletados para diferentes valores de entrada n op 1 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 Figura 2 Linhas de tendência linear e logarítmica com suas equações e valores de ajuste O programa modificado para permitir a análise se encontra no Anexo A 6 Conclusão O problema dos Números Ímpares apresenta uma complexidade On pela necessidade de apresentar todos os valores individualmente O algoritmo e o programa apresentam a mesma complexidade On A contagem de operações confirma a complexidade de On Referências BEECROWD 2023 Problema 1067 Números Ímpares Disponível em httpswwwbeecrowdcombrjudgeptproblemsview1067 Consultado em setembro de 2023 Cormen Thomas et alli 2012 Algoritmos Teoria e Prática Rio de Janeiro LTC y 04848x 03333 R² 09697 y 18929lnx 01409 R² 08663 0 1 2 3 4 5 6 0 2 4 6 8 10 12 ANEXO A Programa modificado public class Main public static void mainString args int op for int n 1 n 10 n op 0 for int i 1 i n i2 Systemoutprintlni op Systemoutprintfd dn n op Trabalho T1 Olimpíada de Programação Simulada A programação competitiva e as olimpíadas de programação são eventos em que equipes de participantes resolvem enunciados propostos por uma comissão organizadora Nesta simulação os enunciados estão disponíveis no BeeCrowd O acesso é realizado após cadastro na plataforma Neste trabalho são considerados somente os problemas adhoc que estão agrupados na Seção 2 BEECROWD 2023 Os problemas tem diferentes níveis de dificuldade de 1 até 9 O trabalho consiste em resolver confirmar a resposta no BeeCrowd e calcular e indicar suaa complexidade O trabalho deve ser realizado em grupos de até três participantes Para a condução do trabalho as seguintes regras devem ser observadas Regras de escolha dos problemas 1 Somente podem ser escolhidos problemas com nível maior ou igual a 4 na Seção 2 2 Cada problema escolhido deve ser anunciado no fórum do trabalho informando o grupo e o número do problema Entregas sem reserva não serão consideradas 3 A quantidade de problemas a serem resolvidos depende do nível de dificuldade de cada problema A soma do nível dos problemas escolhidos deve ser maior ou igual a 10 Para cada problema escolhido 1 Devese resolver cada o problema conforme o enunciado e a solução deve ser confirmada pela plataforma BeeCrowd 2 Devese realizar uma análise de complexidade da solução proposta Para realizar a análise é importante considerar que o tamanho do problema possa aumentar de acordo com certas condições Dito isto descreva como o problema original poderia aumentar A seguir calcule e indique a classe de complexidade a partir da contagem de operações e análise assintótica Pode ser utilizado um gráfico mostrando a contagem do número de operações para diferentes valores de entrada ou análise do códigofonte O que deverá ser entregue Um relatório contendo para cada problema a enunciado do problema escolhido b códigofonte da solução c nível de dificuldade d tela do BeeCrowd com a confirmação da solução e classe de complexidade da solução com a justificativa f todas as referências consultadas devem ser citadas O que não será aceito 1 Plágio ou fraude toda fonte consultada ou ajuda recebida deve ser citada 2 Soluções incompletas trabalhos entregues com erro de compilação ou que não apresentem os itens esperado não serão aceitos Referências BEECROWD 2 Adhoc Última consulta em agosto de 2023 httpswwwbeecrowdcombrjudgeptproblemsindex2 PUCRSEscola Politécnica 2024II Algoritmos e Estruturas de Dados I T1