Baixe o app para aproveitar ainda mais
Prévia do material em texto
ANÁLISE DE ALGORITMOS Bacharelado em Ciência da Computação Trabalho Prático 01 Praticando a Análise de Algoritmos Objetivo: Exercitar a análise analítica de algoritmos e estruturas de dados simples. Modalidade de desenvolvimento: equipe (até 2 componentes) Modalidade da apresentação: envio de arquivo .odt1 para flaviacoelho@ufersa.edu.br Data de entrega: até Domingo, 14/08/2016 Artefatos de entrega: soluções das questões, a seguir. 1. Considere dois computadores que executam 107 (C1) e 109 (C2) operações por segundo e um algoritmo de ordenação cujo tempo de execução é 50nlog10n. Qual é o computador mais indicado (com menor tempo de execução) para ordenar 106 elementos? Justifique (apresentando os cálculos). 2. Prove que g(n) = (n + 1)2 é O(n2). 3. Há diferença entre O(1) e O(2)? Justifique. 4. É verdade que 2nn + 2nnlgn é O(2n)? Justifique. 5. Caracterize o melhor, pior e caso médio para o algoritmo a seguir, utilizando a notação assintótica (apresente todos os cálculos efetuados). algoritmo somaPrefixos Entrada: Um arranjo A que armazena n 1 elementos. Saída: Soma dos prefixos de A. s 0← para i 0 ← até n1 faça s s + A[0]← para j 1 ← até i faça s s + A[j]← retorna s 1 Requerida para viabilizar o registro de alterações e comentários via LibreOffice Writer – vide modelo. 1 ANÁLISE DE ALGORITMOS Bacharelado em Ciência da Computação 6. É verdadeira a seguinte afirmação? Justifique. 7. Calcule a complexidade de melhor e pior casos para o seguinte trecho de programa. if (x == y){ for(i = 0; i < n; i++){ for(j = 0; j <= n; j++){ //instruções } } for(i = 0; i < n; i++){ //instruções } } else{ for(i = 0; i < n; i++) for(j = 0; j < n; j++) for(k = 0; k < n; k++) //instruções } 8. Calcule a T(n) e determine a complexidade assintótica para o seguinte código. 9. Joãozinho tem n reais. Todo dia, ele compra exatamente 1 chocolate (2 reais) ou 1 brigadeiro (1 real) ou 1 sorvete (2 reais). Determine a relação de recorrência que fornece o número de possíveis modos de gastar n reais, sendo n ≥ 3. 10. Determine a ordem de complexidade das relações a seguir. a. T(n) = T(n/2) + 1, T(1) = 1 b. T(n) = 2T(n/2) + (n – 1), T(1) = 1 2 ANÁLISE DE ALGORITMOS Bacharelado em Ciência da Computação c. T(n) = 2T(n – 1) + 1, T(1) = 1 d. T(n) = T(n – 1) + (n – 1), T(1) = 0 3 Trabalho Prático 01
Compartilhar