Complexidade assintótica

Text Material Preview

Complexidade assintótica 
Qual das alternativas descreve corretamente o conceito de complexidade assintotica de um
algoritmo?
a) A quantidade exata de memoria utilizada pelo algoritmo.
b) O comportamento do tempo de execucao ou uso de recursos do algoritmo quando o tamanho da
entrada tende ao infinito.
c) A velocidade de execucao do algoritmo em um computador especifico.
d) O numero de variaveis usadas pelo algoritmo.
Explicacao: A complexidade assintotica descreve como o tempo de execucao ou o consumo de
recursos cresce em funcao do tamanho da entrada, especialmente quando o tamanho tende a
infinito. Nao mede tempo real nem consumo absoluto de memoria.
Qual notacao assintotica e utilizada para representar o limite superior do crescimento de um
algoritmo?
a) (omega)
b) (teta)
c) O (grande O)
d) o (pequeno o)
Explicacao: A notacao O (grande O) e usada para indicar um limite superior assintotico, ou seja, o
pior caso do crescimento do tempo de execucao ou consumo de recursos do algoritmo em funcao
do tamanho da entrada.
Considere a funcao de tempo T(n) = 3n2 + 5n + 2. Qual e a complexidade assintotica em notacao
O?
a) O(n)
b) O(n2)
c) O(n3)
d) O(1)
Explicacao: Quando n cresce muito, o termo dominante e 3n2. Assim, T(n) cresce
proporcionalmente a n2, e a complexidade assintotica e O(n2).
Qual notacao assintotica indica o limite inferior do crescimento de um algoritmo?
a) O (grande O)
b) (omega)
c) (teta)
d) o (pequeno o)
Explicacao: (omega) indica o limite inferior, ou seja, o melhor caso ou crescimento minimo
assintotico do algoritmo em funcao do tamanho da entrada.
Se um algoritmo tem complexidade O(n log n), isso significa que:
a) O tempo de execucao cresce linearmente com o tamanho da entrada.
b) O tempo de execucao cresce mais rapido que O(n2).
c) O tempo de execucao cresce aproximadamente proporcional a n vezes log n.
d) O tempo de execucao e constante, independente do tamanho da entrada.
Explicacao: O(n log n) significa que o crescimento do tempo de execucao e proporcional ao produto
de n pelo logaritmo de n, tipico de algoritmos eficientes de ordenacao, como mergesort e heapsort.
Qual e a diferenca entre O, e em termos de complexidade assintotica?
a) O representa limite superior, limite inferior e crescimento exato assintotico.
b) O representa limite inferior, limite superior e crescimento aproximado.
c) O, e sao equivalentes e podem ser usados indistintamente.
d) O representa tempo constante, tempo linear e tempo quadratico.
Explicacao: O grande O indica limite superior, limite inferior e indica que o algoritmo cresce
exatamente na ordem do termo dominante, ou seja, O e combinados.
Um algoritmo com complexidade T(n) = 2n3 + 7n2 + 4n + 10 tem complexidade assintotica:
a) O(n2)
b) O(n3)
c) O(n)
d) O(1)
Explicacao: O termo dominante e 2n3. Portanto, o crescimento assintotico e O(n3), pois os outros
termos tornam-se despreziveis para n muito grande.
Considere duas funcoes de complexidade: T1(n) = n2 e T2(n) = n log n. Qual cresce mais
rapidamente para valores grandes de n?
a) T1(n)
b) T2(n)
c) Ambas crescem da mesma forma
d) Depende do valor de n
Explicacao: Para n grande, n2 cresce mais rapidamente que n log n, portanto T1(n) cresce mais
rapido. O logaritmo cresce muito mais lentamente que qualquer funcao polinomial com expoente
maior que 1.
Um algoritmo tem complexidade (n2). Isso significa que:
a) No pior caso, ele cresce como n2, mas no melhor caso pode ser menor.
b) O algoritmo cresce exatamente proporcional a n2, tanto no melhor quanto no pior caso.
c) O algoritmo nunca tera crescimento maior que n2.
d) O algoritmo e linear.
Explicacao: (n2) indica que o crescimento do algoritmo e assintoticamente proporcional a n2, tanto
no melhor quanto no pior caso, ou seja, o termo dominante e n2.
Qual das alternativas representa complexidade assintotica constante?
a) O(n)
b) O(n2)
c) O(1)
d) O(log n)
Explicacao: O(1) significa que o tempo de execucao nao depende do tamanho da entrada; ele e
constante, independente de n.
Qual notacao descreve uma funcao que cresce estritamente menos do que outra funcao?
a) O (grande O)
b) o (pequeno o)
c) (teta)
d) (omega)
Explicacao: A notacao o (pequeno o) indica crescimento estritamente menor, ou seja, f(n) = o(g(n))
significa que f(n)/g(n) 0 quando n .
Um algoritmo de busca em lista nao ordenada possui complexidade no pior caso:
a) O(1)
b) O(log n)
c) O(n)
d) O(n2)
Explicacao: No pior caso, e necessario percorrer toda a lista, logo a complexidade cresce
linearmente com o tamanho da entrada, O(n).
Se uma funcao T(n) = 5n + 20, qual e a complexidade assintotica?
a) O(1)
b) O(n)
c) O(n2)
d) O(log n)
Explicacao: O termo dominante e 5n, entao para n grande, T(n) cresce proporcional a n, ou seja,
O(n).
Qual das seguintes complexidades e considerada mais eficiente para n grande?
a) O(n2)
b) O(n log n)
c) O(n3)
d) O(2^n)
Explicacao: O(n log n) cresce mais lentamente que O(n2), O(n3) ou O(2^n), tornando-se mais
eficiente para entradas grandes.
Um algoritmo recursivo que resolve o problema dividindo-o ao meio a cada passo, e combinando
resultados em tempo linear, possui complexidade:
a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)
Explicacao: Esse padrao e tipico de algoritmos como mergesort, cuja complexidade e O(n log n),
pois ha log n divisoes e cada combinacao leva tempo linear.
Se T(n) = n3 + 100n2 + 1000, podemos desprezar os termos menores ao analisar complexidade
assintotica. Qual e o motivo?
a) Porque eles nao influenciam no crescimento relativo para n grande.
b) Porque sempre devemos considerar apenas o primeiro termo.
c) Porque os outros termos sao irrelevantes em qualquer situacao.
d) Porque nao podem ser calculados.
Explicacao: Para n muito grande, os termos de menor ordem tornam-se insignificantes comparados
ao termo dominante n3, que determina o crescimento assintotico.
A complexidade O(log n) e caracteristica de qual tipo de algoritmo?
a) Busca binaria
b) Ordenacao por bolha
c) Percorrer toda lista
d) Algoritmo de Fibonacci recursivo simples
Explicacao: A busca binaria reduz o problema pela metade a cada passo, resultando em
complexidade O(log n).
Qual das alternativas descreve melhor a diferenca entre complexidade no pior caso e no melhor
caso?
a) O pior caso considera a entrada que maximiza o tempo de execucao, e o melhor caso a que
minimiza.
b) Ambos representam sempre a mesma complexidade.
c) O pior caso e menor que o melhor caso.
d) O melhor caso ignora entradas grandes.
Explicacao: A analise de pior caso considera a entrada mais desfavoravel, enquanto a do melhor
caso considera a entrada mais favoravel.
Um algoritmo tem T(n) = n2 + 50n + 100. Qual e sua complexidade ?
a) (1)
b) (n)
c) (n2)
d) (n3)
Explicacao: O termo dominante tambem define o limite inferior assintotico. Aqui, o crescimento
minimo tambem e proporcional a n2, logo (n2).
Considere duas funcoes: f(n) = 3n2 e g(n) = n2 + 100n. Qual e a relacao assintotica correta?
a) f(n) = (g(n))
b) f(n) = O(g(n2))
c) f(n) = o(g(n))
d) f(n) = (n3)
Explicacao: Ambas crescem proporcionalmente a n2, entao f(n) = (g(n)), indicando crescimento
assintotico equivalente.
Em um algoritmo de ordenacao, se o tempo de execucao cresce rapidamente para n grande,
dizemos que ele possui complexidade:
a) Polinomial alta (como O(n3))
b) Linear
c) Logaritmica
d) Constante
Explicacao: Algoritmos cujo tempo cresce muito rapido com n, como O(n3) ou O(2^n), sao
considerados de alta complexidade polinomial ou exponencial, dependendo do termo dominante.
O que significa dizer que uma funcao f(n) = O(g(n))?
a) Que f(n) cresce mais rapido que g(n)
b) Que f(n) nunca ultrapassa g(n) em qualquer caso
c) Que existe uma constante c tal que f(n) c·g(n) para n suficientemente grande
d) Que f(n) e igual a g(n) para todos os n
Explicacao: A definicao formal de grande O indica que f(n) e limitada superiormente por g(n)
multiplicada por uma constantepara n grande.
Se um algoritmo possui complexidade exponencial O(2^n), isso implica que:
a) Ele e eficiente para entradas grandes.
b) Seu tempo de execucao dobra a cada incremento unitario em n.
c) Ele cresce linearmente.
d) Ele tem complexidade constante.
Explicacao: O tempo de execucao de algoritmos exponenciais cresce muito rapidamente; ao
aumentar n em 1, o tempo aproximadamente dobra.
Qual das alternativas melhor representa um algoritmo com complexidade polinomial?
a) O(n2)
b) O(2^n)
c) O(log n)
d) O(1)
Explicacao: Algoritmos polinomiais tem complexidade O(n^k) para algum k constante; O(n2) e um
exemplo classico.
Considere o algoritmo de Fibonacci recursivo simples: F(n) = F(n-1) + F(n-2). Qual e sua
complexidade assintotica?
a) O(n)
b) O(log n)
c) O(2^n)
d) O(n2)
Explicacao: O algoritmo gera muitas chamadas recursivas redundantes, resultando em crescimento
exponencial, O(2^n).
Um algoritmo que percorre cada elemento de uma matriz n x n possui complexidade:
a) O(n)
b) O(n2)
c) O(log n)
d) O(n3)
Explicacao: Percorrer todos os n2 elementos leva tempo proporcional a n2, portanto complexidade
O(n2).
Se dois algoritmos tem complexidades O(n2) e O(n log n), qual e mais eficiente para grandes n?
a) O(n2)
b) O(n log n)
c) Ambas sao iguais
d) Depende apenas da implementacao
Explicacao: O(n log n) cresce mais lentamente que O(n2) para grandes n, tornando-se mais
eficiente assintoticamente.
Quando dizemos que um algoritmo tem complexidade (n log n), estamos afirmando que:
a) Ele pode crescer mais rapido que n2
b) O crescimento real e proporcional a n log n, nem maior nem menor para n grande
c) O crescimento maximo e n2
d) Ele cresce linearmente
Explicacao: (n log n) indica crescimento assintoticamente exato; o algoritmo cresce proporcional a n
log n para entradas grandes.
Qual e a complexidade assintotica de um algoritmo que realiza duas buscas lineares consecutivas
em uma lista de tamanho n?
a) O(n)
b) O(2n)
c) O(n2)
d) O(log n)
Explicacao: A soma de duas funcoes lineares O(n) + O(n) = O(2n) e assintoticamente O(n), pois
constantes multiplicativas sao desprezadas.
Um algoritmo possui complexidade O(n!) para entrada de tamanho n. Isso significa que:
a) Ele cresce polinomialmente
b) Ele cresce exponencialmente, muito rapidamente
c) Ele e constante
d) Ele cresce linearmente
Explicacao: O(n!) cresce mais rapido que qualquer funcao polinomial ou exponencial simples;
algoritmos com essa complexidade tornam-se inviaveis para n moderadamente grande.
Se desejar, posso continuar gerando mais 40 a 50 perguntas com exemplos, comparacoes e
exercicios praticos, garantindo que o texto ultrapasse facilmente 1000 palavras. Quer que eu faca
isso?