Big Theta

Text Material Preview

Big Theta 
O que a notacao Big Theta (
) representa no contexto da analise de algoritmos?
a) A complexidade no pior caso de um algoritmo
b) A complexidade no melhor caso de um algoritmo
c) A complexidade assintotica de um algoritmo
d) A complexidade no caso medio de um algoritmo
Resposta correta: c) A complexidade assintotica de um algoritmo
Explicacao: A notacao Big Theta descreve uma relacao assintotica entre a complexidade de um
algoritmo, representando tanto o limite superior quanto inferior da funcao de tempo ou espaco. Isso
significa que, se um algoritmo tem complexidade
(f(n)), sua performance estara dentro de
f(n) para grandes valores de
n, sem ser nem muito maior nem muito menor.
Qual e a principal diferenca entre as notacoes Big O (
O) e Big Theta (
)?
a) A notacao Big O e mais precisa que a Big Theta
b) A notacao Big O define um limite inferior e a Big Theta define um limite superior
c) A notacao Big Theta descreve um limite superior e inferior, enquanto a Big O apenas descreve o
limite superior
d) A notacao Big Theta e usada apenas para algoritmos recursivos
Resposta correta: c) A notacao Big Theta descreve um limite superior e inferior, enquanto a Big O
apenas descreve o limite superior
Explicacao: A notacao Big O fornece um limite superior para a complexidade de um algoritmo, ou
seja, um limite maximo de tempo ou espaco. Ja a notacao Big Theta estabelece tanto um limite
superior quanto inferior, fornecendo uma estimativa mais precisa da complexidade do algoritmo em
termos de uma funcao assintotica.
Se a complexidade de um algoritmo e expressa como
f(n)=(n
2
), o que isso significa?
a) O tempo de execucao do algoritmo cresce linearmente com o tamanho da entrada
b) O tempo de execucao do algoritmo cresce quadraticamente com o tamanho da entrada
c) O tempo de execucao do algoritmo cresce exponencialmente com o tamanho da entrada
d) O tempo de execucao do algoritmo cresce logaritmicamente com o tamanho da entrada
Resposta correta: b) O tempo de execucao do algoritmo cresce quadraticamente com o tamanho da
entrada
Explicacao: Quando dizemos que a complexidade de um algoritmo e
f(n)=(n
2
), isso significa que, para entradas de tamanho
n, o tempo de execucao do algoritmo cresce de forma quadratica. Em termos de grandes
n, o tempo de execucao e aproximadamente proporcional a
n
2
.
Em relacao a notacao Big Theta, qual e a definicao formal?
a) Se
f(n)=O(g(n)), entao
f(n) e limitado superiormente por
g(n)
b) Se
f(n)=(g(n)), entao existem constantes
c
1
,
c
2
e
n
0
tais que
c
1
g(n)f(n)c
2
g(n) para todo
nn
0
c) Se
f(n)=(g(n)), entao
f(n) e limitado inferiormente por
g(n)
d) Se
f(n)=(g(n)), entao
f(n) cresce mais rapidamente que
g(n)
Resposta correta: b) Se
f(n)=(g(n)), entao existem constantes
c
1
,
c
2
e
n
0
tais que
c
1
g(n)f(n)c
2
g(n) para todo
nn
0
Explicacao: A definicao formal de Big Theta implica que existem constantes
c
1
,
c
2
e
n
0
que garantem que
f(n) esta "encaixada" entre
c
1
g(n) e
c
2
g(n) para valores suficientemente grandes de
n, o que significa que o comportamento assintotico de
f(n) e semelhante ao de
g(n).
Qual das seguintes expressoes representa um exemplo de complexidade que e
(nlogn)?
a) Algoritmos de busca binaria
b) Algoritmos de ordenacao por selecao
c) Algoritmos de ordenacao rapida (QuickSort) no melhor caso
d) Algoritmos de ordenacao por bolha
Resposta correta: c) Algoritmos de ordenacao rapida (QuickSort) no melhor caso
Explicacao: O algoritmo QuickSort, no melhor caso, tem complexidade
(nlogn), pois a divisao das partes do array em cada recursao ocorre de forma balanceada,
resultando em uma profundidade de recursao logaritmica, com o trabalho realizado em cada nivel
sendo linear.
Quando dizemos que um algoritmo tem complexidade
(1), o que isso implica?
a) O algoritmo tem tempo de execucao constante, independentemente do tamanho da entrada
b) O algoritmo tem tempo de execucao linear em relacao ao tamanho da entrada
c) O algoritmo tem tempo de execucao quadratico em relacao ao tamanho da entrada
d) O algoritmo tem tempo de execucao logaritmico em relacao ao tamanho da entrada
Resposta correta: a) O algoritmo tem tempo de execucao constante, independentemente do
tamanho da entrada
Explicacao: A complexidade
(1) significa que o tempo de execucao do algoritmo nao depende do tamanho da entrada. Isso
implica que o algoritmo realiza o mesmo numero de operacoes independentemente de
n, ou seja, o tempo e constante.
Em termos de notacao Big Theta, como podemos classificar um algoritmo que tem um tempo de
execucao de
f(n)=3n+5?
a)
(n)
b)
(n
2
)
c)
(logn)
d)
(1)
Resposta correta: a)
(n)
Explicacao: Embora a expressao
3n+5 tenha um termo constante, sua complexidade assintotica e linear. Isso porque, para grandes
n, o termo
3n domina o crescimento da funcao, o que a classifica como
(n).
Qual das seguintes afirmativas e verdadeira em relacao a notacao Big Theta?
a) A notacao Big Theta e util para expressar o pior caso de um algoritmo, mas nao o melhor caso
b) A notacao Big Theta descreve a complexidade em termos do melhor e pior caso, fornecendo
uma analise mais precisa
c) A notacao Big Theta e usada apenas para analise de algoritmos recursivos
d) A notacao Big Theta nao tem relacao com a complexidade assintotica de um algoritmo
Resposta correta: b) A notacao Big Theta descreve a complexidade em termos do melhor e pior
caso, fornecendo uma analise mais precisa
Explicacao: A notacao Big Theta e usada para representar a complexidade de um algoritmo no
melhor e no pior caso, ou seja, oferece uma analise mais precisa da performance do algoritmo em
termos assintoticos. Isso ajuda a entender o comportamento do algoritmo para grandes entradas.
Qual das opcoes abaixo e uma funcao assintotica que descreve o comportamento de um algoritmo
de busca binaria?
a)
(n)
b)
(logn)
c)
(n
2
)
d)
(nlogn)
Resposta correta: b)
(logn)
Explicacao: A busca binaria tem complexidade
(logn), pois a cada iteracao, a busca reduz pela metade o tamanho do problema. Isso faz com que
a profundidade da arvore de decisoes seja logaritmica em relacao ao tamanho da entrada.
Se temos um algoritmo com complexidade
(n
3
), qual seria o comportamento do algoritmo para entradas muito grandes de
n?
a) O tempo de execucao cresce linearmente
b) O tempo de execucao cresce quadraticamente
c) O tempo de execucao cresce cubicamente
d) O tempo de execucao cresce exponencialmente
Resposta correta: c) O tempo de execucao cresce cubicamente
Explicacao: Quando dizemos que a complexidade de um algoritmo e
(n
3
), isso significa que, a medida que
n cresce, o tempo de execucao do algoritmo aumenta de forma cubica, ou seja, proporcional a
n
3
. Isso pode fazer com que o algoritmo se torne significativamente mais lento para grandes valores
de
n.
Quais sao as implicacoes praticas de um algoritmo ter complexidade
(nlogn)?
a) O algoritmo sera muito eficiente mesmo para entradas pequenas
b) O algoritmo tera um desempenho pior que um algoritmo com complexidade
(n
2
), mas melhor que um
(n
3
)
c) O algoritmo tera um desempenho linear, mas com um fator logaritmico