Complexidade de tempo

Text Material Preview

Complexidade de tempo 
Qual das opcoes a seguir melhor descreve o conceito de complexidade de tempo em algoritmos?
a) A quantidade de memoria que um algoritmo consome.
b) O numero de operacoes que um algoritmo executa em funcao do tamanho da entrada.
c) O numero de linhas de codigo que um algoritmo possui.
d) O tempo real de execucao medido em segundos, independentemente da entrada.
Resposta explicativa: A resposta correta e b. A complexidade de tempo mede como o numero de
operacoes cresce a medida que o tamanho da entrada aumenta, fornecendo uma forma de analisar
o desempenho teorico de algoritmos sem depender do hardware.
Qual das notacoes a seguir e utilizada para expressar o pior caso da complexidade de um
algoritmo?
a)
(n)
b)
O(n)
c)
(n)
d)
o(n)
Resposta explicativa: A resposta correta e b. A notacao
O(n) descreve o limite superior do numero de operacoes que um algoritmo pode executar, sendo
usada para analisar o pior cenario possivel de execucao.
Considere um algoritmo de busca linear em um vetor de tamanho
n. Qual e a complexidade de tempo no pior caso?
a)
O(1)
b)
O(logn)
c)
O(n)
d)
O(n
2
)
Resposta explicativa: A resposta correta e c. No pior caso, a busca linear precisa percorrer todos os
n elementos do vetor, resultando em uma complexidade linear proporcional ao tamanho da entrada.
Qual das alternativas apresenta corretamente a relacao entre as notacoes
O(n),
(n) e
(n)?
a)
O(n) indica limite inferior,
(n) indica limite superior,
(n) indica crescimento medio.
b)
O(n) indica limite superior,
(n) indica limite exato,
(n) indica limite inferior.
c) Todas indicam exatamente o mesmo conceito, apenas com simbolos diferentes.
d)
O(n) indica limite medio,
(n) indica pior caso,
(n) indica melhor caso.
Resposta explicativa: A resposta correta e b.
O(n) descreve o crescimento maximo do algoritmo,
(n) o minimo, e
(n) indica que o crescimento e assintoticamente exato, ou seja, tanto superior quanto inferior ao
mesmo tempo.
Um algoritmo de ordenacao bolha (bubble sort) possui complexidade de tempo
O(n
2
) no pior caso. O que isso significa na pratica?
a) Que o algoritmo e sempre rapido, independentemente do tamanho da entrada.
b) Que o tempo de execucao cresce aproximadamente com o quadrado do numero de elementos a
serem ordenados.
c) Que o algoritmo e mais eficiente que algoritmos
O(nlogn).
d) Que o algoritmo consome menos memoria do que outros algoritmos de ordenacao.
Resposta explicativa: A resposta correta e b. O tempo de execucao do bubble sort aumenta de
forma quadratica com o aumento do tamanho do vetor, tornando-o pouco eficiente para grandes
entradas.
Qual e a complexidade de tempo media de uma busca binaria em um vetor ordenado de
n elementos?
a)
O(n)
b)
O(logn)
c)
O(n
2
)
d)
O(1)
Resposta explicativa: A resposta correta e b. A busca binaria reduz pela metade a quantidade de
elementos a cada iteracao, resultando em um crescimento logaritmico do numero de comparacoes
em funcao do tamanho da entrada.
Se um algoritmo possui complexidade
O(n!), como ele se comporta quando o tamanho da entrada aumenta?
a) Cresce de forma linear, sendo adequado para grandes entradas.
b) Cresce de forma exponencial, tornando-o inviavel para entradas maiores.
c) Cresce logaritmicamente, sendo muito eficiente.
d) Cresce de forma constante, independente do tamanho da entrada.
Resposta explicativa: A resposta correta e b. Algoritmos com complexidade fatorial tem um
crescimento extremamente rapido, tornando-os impraticaveis para valores altos de
n.
Entre as opcoes abaixo, qual representa a complexidade de tempo mais eficiente para um algoritmo
de ordenacao no pior caso?
a)
O(n
2
)
b)
O(nlogn)
c)
O(n!)
d)
O(2
n
)
Resposta explicativa: A resposta correta e b. Algoritmos como merge sort e heap sort garantem
uma complexidade
O(nlogn) no pior caso, sendo mais eficientes que algoritmos quadraticos ou exponenciais.
Considerando o seguinte trecho de codigo:
java
Copiar codigo
for i = 1 to n:
 for j = 1 to n:
 print(i, j)
Qual e a complexidade de tempo desse algoritmo?
a)
O(n)
b)
O(nlogn)
c)
O(n
2
)
d)
O(n!)
Resposta explicativa: A resposta correta e c. O laco externo roda
n vezes, e para cada iteracao do laco externo, o interno tambem roda
n vezes. Portanto, o numero total de operacoes e
n×n=n
2
.
Em qual cenario a analise de complexidade de tempo e mais relevante?
a) Quando queremos medir a memoria utilizada por um algoritmo.
b) Quando queremos prever como o tempo de execucao aumentara com entradas maiores.
c) Quando queremos contar quantas linhas de codigo o algoritmo possui.
d) Quando precisamos apenas executar o algoritmo uma vez.
Resposta explicativa: A resposta correta e b. A complexidade de tempo permite estimar o
desempenho do algoritmo a medida que o tamanho da entrada cresce, independentemente do
hardware ou do tempo real de execucao.
Qual das alternativas descreve corretamente a diferenca entre complexidade de tempo no melhor e
no pior caso?
a) O melhor caso e sempre maior que o pior caso.
b) O pior caso representa a entrada que faz o algoritmo executar o menor numero de operacoes.
c) O melhor caso e a entrada que permite que o algoritmo execute o menor numero de operacoes,
enquanto o pior caso e aquela que exige o maior numero de operacoes.
d) Nao ha diferenca entre melhor e pior caso.
Resposta explicativa: A resposta correta e c. O melhor caso ocorre quando o algoritmo encontra
rapidamente a solucao ou realiza poucas operacoes, enquanto o pior caso ocorre quando ele
precisa realizar o maximo de operacoes possiveis.
Um algoritmo tem complexidade
O(n
3
). Se o tamanho da entrada triplica, aproximadamente quantas vezes maior sera o numero de
operacoes?
a) 3 vezes
b) 6 vezes
c) 9 vezes
d) 27 vezes
Resposta explicativa: A resposta correta e d. A complexidade cubica significa que o numero de
operacoes cresce com o cubo do tamanho da entrada. Se
n triplica, o numero de operacoes cresce aproximadamente
3
3
=27 vezes.
Qual e a complexidade de tempo de percorrer uma lista ligada de tamanho
n para buscar um elemento especifico?
a)
O(1)
b)
O(logn)
c)
O(n)
d)
O(n
2
)
Resposta explicativa: A resposta correta e c. Em uma lista ligada, nao ha acesso direto a elementos
intermediarios, portanto, no pior caso, e necessario percorrer todos os
n elementos ate encontrar o alvo.
Para um algoritmo de ordenacao quicksort, qual e a complexidade de tempo no pior caso e no caso
medio?
a) Pior caso
O(n
2
), caso medio
O(nlogn)
b) Pior caso
O(n), caso medio
O(n
2
)
c) Pior caso
O(logn), caso medio
O(nlogn)
d) Pior caso
O(nlogn), caso medio
O(n)
Resposta explicativa: A resposta correta e a. O quicksort atinge
O(n
2
) quando a escolha do pivo e desfavoravel repetidamente, mas em media ele funciona com
complexidade
O(nlogn).
O que significa quando um algoritmo tem complexidade
O(1)?
a) Que seu tempo de execucao depende linearmente do tamanho da entrada.
b) Que seu tempo de execucao nao depende do tamanho da entrada.
c) Que seu tempo de execucao cresce quadraticamente com a entrada.
d) Que seu tempo de execucao e exponencial.
Resposta explicativa: A resposta correta e b. Um algoritmo com complexidade constante executa
aproximadamente o mesmo numero de operacoes independentemente do tamanho da entrada.
Qual das alternativas abaixo e uma caracteristica tipica de algoritmos com complexidade
O(logn)?
a) Crescem rapidamente com o aumento da entrada.
b) Reduzem o espaco de busca pela metade a cada iteracao.
c) Sempre possuem duas camadas de loops aninhados.
d) Sao sempre menos eficientes que algoritmos
O(n).
Resposta explicativa: A resposta correta e b. Algoritmos logaritmicos, como a busca binaria,
funcionam dividindo o problema em partes menores, geralmente pela metade, em cada passo.
Qual e a complexidade de tempo de somar todos os elementos de um vetor de tamanho
n?
a)
O(1)
b)
O(logn)
c)
O(n)
d)O(n
2
)
Resposta explicativa: A resposta correta e c. Para somar todos os elementos, cada elemento
precisa ser visitado uma vez, resultando em tempo de execucao linear em funcao do tamanho do
vetor.
Um algoritmo realiza dois loops consecutivos: o primeiro percorre
n elementos e o segundo tambem percorre
n elementos, mas de forma independente. Qual e a complexidade de tempo total?
a)
O(n)
b)
O(2n)
c)
O(n
2
)
d)
O(nlogn)
Resposta explicativa: A resposta correta e a. Loops consecutivos somam complexidades lineares:
O(n)+O(n)=O(2n), que, em notacao assintotica, e simplificada para
O(n).
Qual e a relacao entre complexidade de tempo e eficiencia de um algoritmo?
a) Quanto maior a complexidade de tempo, mais eficiente e o algoritmo.
b) Quanto menor a complexidade de tempo, mais eficiente e o algoritmo.
c) Complexidade de tempo nao tem relacao com eficiencia.
d) Complexidade de tempo e relevante apenas para algoritmos recursivos.
Resposta explicativa: A resposta correta e b. Algoritmos com menor complexidade de tempo
geralmente executam menos operacoes e sao mais rapidos, especialmente para entradas grandes.
Em um algoritmo recursivo, como a complexidade de tempo pode ser calculada?
a) Apenas contando as linhas de codigo.
b) Usando equacoes de recorrencia que descrevem a quantidade de operacoes em funcao do
tamanho da entrada.
c) Medindo o tempo de execucao em segundos.
d) Verificando a quantidade de chamadas de funcoes auxiliares.
Resposta explicativa: A resposta correta e b. Equacoes de recorrencia permitem modelar o
comportamento de algoritmos recursivos e determinar sua complexidade assintotica.
Se voce quiser, posso continuar ate expandir para um documento detalhado de mais de 1000
palavras, mantendo o mesmo estilo natural e humano. Quer que eu faca isso agora?