MATERIAL 32

Prévia do material em texto

Material de Estudo 32: Análise de Algoritmos
1. O que é a notação Big O?
a) Uma notação usada para descrever o tempo de execução exato de um algoritmo. b) Uma
notação usada para descrever o limite superior assintótico do tempo de execução ou do uso
de espaço de um algoritmo, em função do tamanho da entrada, representando o pior caso. c)
Uma notação usada para descrever o limite inferior assintótico do tempo de execução de um
algoritmo. d) Uma notação usada para descrever o caso médio do tempo de execução de um
algoritmo. e) Uma ferramenta de debug.
Resposta: b) Justificativa: A notação Big O fornece uma forma de comparar a eficiênci� de
algoritmos de forma simplificada, focando no comportamento para entradas grandes.
2. Qual a complexidade de tempo de um algoritmo de busca linear em um array não
ordenado?
a) O(1) b) O(log n) c) O(n) d) O(n log n) e) O(n²)
Resposta: c) Justificativa: No pior caso, o algoritmo de busca linear precisa percorrer todos os
n elementos do array.
3. Um algoritmo com complexidade de tempo O(n²) é mais eficiente do que um
algoritmo com complexidade de tempo O(n log n)? a) Sim, sempre. b) Não, pois O(n
log n) cresce mais lentamente que O(n²) para valores grandes de n. c) Depende do
tamanho da entrada. d) Depende da linguagem de programação. e) Depende do
hardware.
Resposta: b) Justificativa: Para entradas suficientemente grandes, um algoritmo O(n log n)
será mais rápido que um O(n²).
4. O que significa dizer que um algoritmo é recursivo?
a) Que ele utiliza um loop para iterar sobre os dados. b) Que ele chama a si mesmo, direta ou
indiretamente, durante sua execução, geralmente dividindo um problema em subproblemas
menores. c) Que ele utiliza uma estrutura de dados específica, como uma pilha. d) Que ele é
muito eficiente. e) Que ele não utiliza variáveis.
Resposta: b) Justificativa: A recursão é uma técnica poderosa, mas deve ser usada com
cuidado para evitar st�ck overflow.
5. Qual é a principal vantagem da progr�m�ção dinâmic�? a) Reduzir o tempo de
execução de algoritmos recursivos, evitando recalcular soluções para subproblemas
que já foram resolvidos, armazenando os resultados em uma tabela (memoização). b)
Tornar o código mais fácil de entender. c) Reduzir o uso de memória. d) Simplificar a
estrutura do código. e) Eliminar a necessidade de testes.
Resposta: a) Justificativa: A programação dinâmica é uma técnica de otimização que pode
transformar algoritmos exponenciais em polinomiais, em muitos casos.
6. Qual a complexidade de tempo, no pior caso, do algoritmo quicksort?
a) O(n) b) O(log n) c) O(n log n) d) O(n²) e) O(1)
Resposta: d) Justificativa: Embora o caso médio do quicksort seja O(n log n), o pior caso
(quando o pivô escolhido é sempre o menor ou o maior elemento) é O(n²). Porém, na prátic�,
o quicksort é frequentemente mais rápido que outros algoritmos O(n log n) devido a
constantes menores e otimizações.
7. O que é uma árvore de decisão em algoritmos de classificação?
a) Uma estrutura de dados usada para armazenar os elementos a serem ordenados. b) Um
modelo que representa todas as possíveis comparações e decisões que um algoritmo de
classificação baseado em comparações pode fazer, ajudando a determinar um limite inferior
para a complexidade do algoritmo. c) Um algoritmo de ordenação específico. d) Uma forma de
visualizar o código de um algoritmo. e) Uma técnica de debug.
Resposta: b) Justificativa: A árvore de decisão é uma ferramenta teórica para analisar
algoritmos de classificação.
8. Qual a diferença entre �nálise de pior c�so, �nálise de c�so médio e �nálise de melhor
c�so de um algoritmo?
a) Não há diferença; são apenas diferentes formas de expressar a mesma coisa. b) A análise de
pior caso considera o cenário em que o algoritmo leva mais tempo (ou usa mais espaço); a
análise de caso médio considera o tempo (ou espaço) médio, considerando todas as possíveis
entradas e suas probabilidades; a análise de melhor caso considera o cenário em que o
algoritmo leva menos tempo (ou usa menos espaço). c) A análise de pior caso é sempre mais
importante que as outras. d) A análise de caso médio é sempre mais importante que as outras.
e) A análise de melhor caso é a mais útil na prática.
Resposta: b) Justificativa: Cada tipo de análise fornece informações diferentes sobre o
desempenho do algoritmo. A análise de pior caso é frequentemente a mais relevante para
garantir que o algoritmo não tenha um desempenho in�ceit�velmente ruim.