Exercícios sobre complexidade de algoritmos

Prévia do material em texto

<p>(8973100) Algoritmos e > Questionários Exercícios sobre complexida... PUC Minas Graduação Presencial Síncro. Exercícios sobre complexidade de algoritmos Detalhes do envio: Conta Página inicial 4.556 Teams Entrega 15 set em 23:59 Pontos 1 Perguntas 5 Tempo: minutos Painel de Disponível 11 set em 10:00 15 set em 23:59 Limite de tempo Nenhum Tarefas controle Pontuação 1 1 Fóruns atual: Instruções Cursos Notas Pontuação 1 1 Biblioteca PUC mantida: Grupos Minas ALGORITMOS E Pessoas Calendário ESTRUTURAS DE DADOS Páginas 111 Arquivos Caixa de entrada Programa Prezados alunos, Testes Histórico Módulos Esses exercícios devem ser realizados individualmente e encerrados até o dia às 23:59. Essa atividade tem Colaborações valor de 1 ponto. Studio Office 365 Bons estudos! Medalhas Ajuda João Pesquisa inteligente Este teste foi travado 15 set em 23:59. Lucid (Whiteboard) Avaliação CPA Histórico de tentativas Tentativa Tempo Pontuação MAIS RECENTE Tentativa 1 4.556 minutos 1 Pontuação deste teste: 1 de 1 Enviado 14 set em 23:57 Esta tentativa levou 4.556 minutos. Pergunta 1 pts Considere dois vetores ordenados. Assuma ainda que cada um desses vetores apresente n elementos. Precisa-se formar então um terceiro vetor, correspondente à junção desses dois vetores ordenados mencionados anteriormente. Dessa esse terceiro vetor apresentará 2n elementos, que também serão armazenados de forma ordenada. Pode- se afirmar que a ordem de complexidade desse processo será: Correto! O(n log n) O(1) O(log n) Pergunta 2 0,2 0,2 pts Leia as afirmativas a seguir, considerando que f1(n) e f2(n) são funções positivas. 1. Se f2(n) é O(f1(n)), um algoritmo de função de complexidade de tempo f1(n) possui ordem de complexidade f2(n). 2. Se f2(n) é O(f1(n)), então f1(n) é um limite superior para 3. Se a função f2(n) 5 log(n) + então a função f2(n) é O(log(n)) 4 Se f2(n) = temos que f2(n) é e f1(n) é O(f2(n)). 5. Se f2(n) = n, temos que f2(n) = O(f1(n)). Assinale a alternativa que apresenta somente as afirmativas CORRETAS. 1.3.4.5</p><p>1,2,4,5 2,3,4 Correto! 2,3,4,5 Pergunta 3 0,2/0,2 pts Abaixo temos um gráfico que evidencia a relação de domínio assintótico entre diversas funções de complexidade de algoritmos. f4 2n 200 150 Tempo 100 f3 50 f2 n 2 4 6 8 10 Tamanho do problema Analisando o gráfico apresentado, podemos afirmar que: limite superior do comportamento do custo de uma função de complexidade f(n) é quando aproxima-se de 2n. A ordem de complexidade de f3 corresponde a O(log2n). A complexidade de f1 corresponde a Correto! f3 e f4 apresentam desempenho melhor que A notação permite comparar os limites superiores dos comportamentos de algoritmos. Assim, podemos afirmar que um programa O(f4) é sempre melhor que um algoritmo O(f3). Pergunta 4 pts Considere o código abaixo, implementado utilizando-se a linguagem de programação Java: public static boolean A. intl B) { for (int 0; < A.length; i++) for (int j = i < B.length; j++) if return false; return } Considere ainda que cada um dos vetores "A" e "B" apresenta n elementos. A ordem de complexidade desse algoritmo é: Correto! O(n log n) n)</p><p>O(n) O(log n) Pergunta 5 0.2 0,2 pts Um ponto importante a ser considerado no projeto de um algoritmo é a eficiência da solução proposta. Essa eficiência tradicionalmente relaciona o tamanho da entrada com o tempo de execução ou espaço de memória necessários para a execução do algoritmo. Sabendo que a função de complexidade de tempo de um algoritmo é f (n) = + 5n - 4, analise as afirmações abaixo sobre a ordem de complexidade desse algoritmo: I. II. (n2) III. (n). É correto o que se afirma em Correto! apenas II. e III. III. I. CORRETA: Como a função de complexidade de tempo do algoritmo é f (n) = 3n2 + 5n - 4, sua ordem de complexidade é consequentemente, o de qualquer função maior que f (n) = II. CORRETA: Como a função de complexidade de tempo do algoritmo é - 4, sua ordem de complexidade é III. ERRADA: Como a função de complexidade de tempo do algoritmo é (n) = 3n2 + 5n - 4, sua ordem de complexidade é (n2), não podendo ser da ordem de uma função menor que f (n) =n2 Pontuação do teste: 1 de 1 Anterior Próximo</p>