Complexidade de Algoritmos

Prévia do material em texto

Questão 1/5 - Estrutura de Dados
A complexidade de um algoritmo pode ser mensurada matematicamente em termos de uma função de custo
do algoritmo.
Acerca da função custo de um algoritmo, assinale a alternativa CORRETA:
Nota: 20.0
A
A ordem de como os dados de entradas estão organizados não tem impacto no desempenho do
algoritmo em tempo de execução.
Tem impacto. Conforme mostrado na AULA 1 – TEMA 2.
B
O custo matemático de um algoritmo é dado, exclusivamente, pelo custo de tempo de execução de um
algoritmo.
É dado pelo tempo de execução e pelo uso de memória, embora este segundo não esteja sendo
investigado em nossa disciplina.
C
O custo matemático de tempo de execução de um algoritmo pode ser mensurado através da contagem
de instruções em uma linguagem de alto nível.
Você acertou!
AULA 1 – TEMA 2. CORRETO.
D
A função custo é dada em função do tamanho do conjunto de dados de entrada n, ou seja, em função
da quantidade de instruções a serem executadas.
n representa a quantidade de dados a serem manipulados, como por exemplo, um vetor de entrada de
tamanho n. E não significa as instruções contadas.
E
O custo de tempo de execução de um algoritmo corresponde a quantos núcleos paralelos o algoritmo
está sendo executado.
Tempo de execução significa o quão rápido um algoritmo executa para resolver um problema. Não
tendo relação com o paralelismo.
Questão 2/5 - Estrutura de Dados
A recursividade é um recurso de programação bastante empregado, e consiste no ato de uma função em um
código realizar chamadas de si mesmo, abrindo diferentes instâncias de uma mesma função na memória do
programa.
Acerca de recursividade e algoritmos recursivos, assinale a alternativa INCORRETA:
Nota: 20.0
A Diversos problemas computacionais que poderiam ser resolvidos utilizando algoritmos iterativos, ouseja, laços de repetição, podem também ser resolvidos usando recursividade.
B
Um algoritmo recursivo terá uma complexidade logarítmica, apresentando um desempenho inferior
em tempo de execução superior a um algoritmo construído de forma iterativa.
Você acertou!
AULA 1 – TEMA 4. O desempenho em tempo de execução é superior.
C Uma possível desvantagem de um algoritmo recursivo é o seu uso de memória mais elevado, uma vezque diversas instâncias de uma mesma função precisam ser alocadas na memória.
D
Um algoritmo que executa uma função denominada de soma, e que realiza a chamada de uma função
denominada compara, não pode ser considerado um algoritmo recursivo, uma vez que não realizada
chamadas de si mesma.
E
Um algoritmo recursivo comumente serve para resolver problemas do tipo “dividir para conquistar”,
onde dividimos um problema em partes menores e mais fáceis de solucionar, para posteriormente
agregar as pequenas soluções em uma maior.
Questão 3/5 - Estrutura de Dados
No primeiro assunto de nossa disciplina investigamos o que são estruturas de dados e como podemos
classificá-las em tipos.
Acerca deste assunto, assinale a alternativa INCORRETA:
Nota: 20.0
A Um dado que pode ser decomposto em partes mais simples, é considerado um dado estruturado e,portanto, uma estrutura de dados.
B
Os tipos de dados manipulados por um algoritmo podem ser classificados em duas categorias
distintas: os atômicos, que são dados indivisíveis, e os dados compostos, que podem ser divisíveis em
mais partes menores.
C
Podemos classificar uma estrutura de dados como sendo do tipo homogênea (como registros) ou do
tipo heterogênea (como vetores e matrizes).
Você acertou!
AULA 1 – TEMA 1. Podemos classificar uma estrutura de dados como sendo do tipo heterogênea
(como registros) ou do tipo homogênea (como vetores e matrizes).
D Uma estrutura homogênea é aquela cujo tipo dos dados nela armazenados são de um único tipo, comointeiro, real, caractere ou lógico
E Uma estrutura contendo dados do tipo caractere e do tipo real pode ser considerada uma estrutura dedados heterogênea.
Questão 4/5 - Estrutura de Dados
Uma implementação do algoritmo de ordenação do tipo bubble sort pode ser visto abaixo. As partes que
envolvem impressão de dados na tela e leitura de dados foram omitidas para um melhor entendimento do que
é necessário na questão. 
 
X[TAMANHOVETOR], i, j, aux: inteiro
 para i de 1 até TAMANHOVETOR faça 
 para j de 0 até (TAMANHOVETOR - 2) faça 
 se (X[j] > X[j + 1]) então 
 aux <- X[j]
 X[j] <- X[j + 1]
 X[j + 1] <- aux
 fimse
 fimpara
 fimpara
Acerca deste algoritmo, assinale a alternativa CORRETA:
 
Nota: 20.0
A
O algoritmo apresentado no exercício realizado a ordenação de dados numéricos, inteiros, em ordem
decrescente.
Ordenação é crescente.
B
As linhas de código que correspondem a troca dos valores usando uma variável auxiliar poderiam ser
também escritas da seguinte maneira:
 aux <- X[j+1]
 X[j+1] <- X[j]
 X[j] <- aux
Você acertou!
AULA 2 – TEMA 2. CORRETO.
C
Se precisarmos ordenar dados não numéricos, como caracteres, precisaremos repensar em toda a
lógica do bubble sort, não sendo possível adaptar o código facilmente.
Basta adaptarmos a linha da condicional para funcionar com outro tipo de dado.
D Não é possível implementar o bubble sort com laços de repetição do tipo enquanto.É possível implementar com qualquer tipo de laço, para, enquanto ou repita.
E A complexidade deste algoritmo, para o pior caso, é O(logn).Complexidade O(n²).
Questão 5/5 - Estrutura de Dados
Chamamos de análise assintótica de algoritmos quando encontramos a complexidade de um algoritmo de
maneira aproximada através de uma curva de tendência. Este tipo de análise e é a mais adotada para
compararmos desempenho de algoritmos.
Acerca da análise assintótica de um algoritmo, assinale a alternativa INCORRETA:
Nota: 20.0
A Um algoritmo com três laços de repetição não encadeados contém uma complexidade assintótica,para o pior caso, O(n).
B Na análise assintótica, fazemos o conjunto de dados de entrada da função custo tender ao infinito,mantendo na equação somente o termo de maior grau, ou seja, aquele que mais cresce na equação.
C Um algoritmo com três laços de repetição aninhados contém uma complexidade assintótica, para opior caso, O(n³).
D
A complexidade assintótica para o pior caso, também conhecida como BigO, representa o pior
cenário para um algoritmo, ou seja, quando mais instruções precisam ser executadas, levando mais
tempo para finalizar a execução.
E
A complexidade assintótica para o pior caso de um algoritmo contendo dois laços de repetição
aninhados, sendo que o segundo laço só será executado caso uma condicional simples seja verdadeira,
será O(n).
Você acertou!
AULA 1 – TEMA 3. O pior caso (BigO) nos diz que todas as linhas devem ser executadas, ou seja, a
condicional será sempre verdadeira, e ambos laços de repetição serão sempre executados, sendo
assim, complexidade O(n²).