Introdução à análise assintótica Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Introdução à análise assintótica – Teoria dos Grafos e Análise de
Algoritmos 
Exercícios
1. O comportamento assintótico de funções pode ser expresso de forma precisa por
meio do usa da notação O. Sobre essa técnica utilizada para indicar o limite
superior de funções, veja as afirmativas a seguir:
I. 2n+1 = O(2n)
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n))
III. 22n = O(2n)
IV. 6n3 = O(n2)
Quais estão corretas?
Resposta correta.
A. I e II.
I. 2n+1 = O(2n) 
Verdadeira, pois 2n+1 = 2 · 2n = 2 · O(2n) = O(2n)
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n))
Verdadeira, pois, para c e m positivos, tem-se f(n) <= ch(n), com n > m, e 
para c' e m', tem-se g(n) <= c'h(n), com n > m'. Tomando-se n > max｛m, m'｝, 
pode-se afirmar que f(n) + g(n) <= ch(n) + c'h(n). Então, f(n) + g(n) <= (c + 
c')h(n) para todo n > max{m, m'}, o que corresponde exatamente a afirmar que f(n) 
+ g(n) = O(h(n)).
III. 22n = O(2n)
Falsa, pois, se fosse verdade, então
22n <= c2n, para algum c, n0 > 0 e todo n > n0
2nlog2(2) <= log2c + nlog2(2)
2n <= log2c + n
n <= log2c. Porém, não existe uma constante c que satisfaça essa desigualdade.
IV. 6n3 = O(n2)
Falsa, pois, se fosse verdade, então 6n3 <= cn2 para c e m > 0 e todo n > m. Isso 
implicaria que 6n <= c (dividindo-se a desigualdade por n2). Porém, não existe 
constante c que satisfaça essa desigualdade.
2. Um modelo largamente utilizado para a subsidiar a análise da eficiência de
algoritmos é conhecido como modelo de computação RAM.
Com base nesse modelo e na função Misterio abaixo, marque V para verdadeiro e F
para falso para os itens a seguir.
função Misterio(n)
    // n é um número inteiro não negativo
    S = 0
    para i = 0 até n faça
        S = S + i * i
    fim para
    retorna S
fim função
( ) A operação básica de comparação do algoritmo precisa considerar a
precedência de operadores aritméticos.
( ) A função executa n + 1 operações básicas para qualquer entrada de tamanho n.
( ) Considerando a complexidade de melhor caso da função, ela apresenta mais
eficiência que no pior caso.
( ) Em comparação com a complexidade de pior caso da busca sequencial, ambas
as funções apresentam a mesma eficiência.
Feito isso, assinale a alternativa que apresenta a sequência correta:
Resposta correta.
B. F - F - F – V.
(F)   A   operação   básica   de   comparação   do   algoritmo   precisa   considerar   a
precedência   de   operadores   aritméticos.   Falsa,   porque   a   operação   elementar
básica da função é corresponde a uma adição e a uma multiplicação.
(F)   A   função   executa n   +   1 operações   básicas   para   qualquer   entrada   de
tamanho n. Falsa, porque a função executa uma adição e uma multiplicação para
cada   uma   da n iterações,   totalizando   2n   operações.   Porém,   há   ainda   uma
atribuição inicial (S = 0), o que resulta em 2n + 1 operações básicas.
(F) Considerando a complexidade de melhor caso da função, ela apresenta mais
eficiência que no pior caso. Falsa, porque ambas as complexidades de melhor e
pior caso são da ordem de O(n); logo, apresentam a mesma relação de eficiência.
(V)   Em   comparação   com   a   complexidade   de   pior   caso   da   busca   sequencial,
ambas   as   funções   apresentam   a   mesma   eficiência.   Verdadeiro,   porque   a
complexidade  de  pior   caso  da  busca  sequencial  é O(n),  o  que  corresponde  à
mesma ordem de complexidade da função.
3. Considerando a função f(n) = 5n2 + 2n + 4, pode-se afirmar que ela é dominada
assintoticamente pela função g(n) = _____. Isso quer dizer que existem constantes
positivas c e m tais que, para n => m, é válido que _____.Valores de c e m que
validam essa inequação são _____, respectivamente.
Assinale a alternativa que preenche corretamente as lacunas.
Você acertou!
C. n3 / |f(n)| <= c · |g(n)| / 11 e 1
Pode-se afirmar que g(n) = n3 domina f(n), pois existem c e m positivos tais que |
f(n)| <= c · |g(n)|. De fato, é verdadeiro que 5n2 + 2n + 4 <= 5n3+ 2n3 + 4n3 =
11n3. Logo, tomando-se c = 11 e m = 1, tem-se que |f(n)| <= c · |g(n)| para todo n >
m. Se os valores de c = 1 e m = 4 fossem utilizados, não seria possível afirmar que
f(n) é dominada assintoticamente por n3, pois, para n = 5 > m, f(n) = 125 + 10 + 4
> 125 = g(n). Além disso, não é possível encontrar uma constante c positiva que
torne as desigualdades 5n2 + 2n + 4 <= cn2 e 5n2 + 2n + 4 <= cn verdadeiras.
Portanto, f(n) não é dominada assintoticamente nem por g(n) = n2, nem por g(n) =
n.
4. A avaliação das complexidades de melhor e pior caso está vinculada aos passos
executados por um algoritmo e pela operação elementar básica considerada. Seja a
função EncontraMaior, que retorna o maior elemento de um vetor de números não
negativos:
função EncontraMaior(vetor)
    maior = -1
    para pos = 1 até n faça // n é o tamanho do vetor
        se maior < vetor[pos] então
            maior = vetor[pos] 
        fim se
    fim para
    retorna maior
fim função
Assinale a alternativa que indica as complexidades de melhor e pior caso do
algoritmo, considerando a operação elementar básica como a atribuição à
variável maior.
Resposta correta.
D. Melhor caso: O(1); pior caso: O(n).
Considerando a operação básica de atribuição, o melhor caso vai ocorrer quando
o vetor  está  ordenado de  forma decrescente.  Assim,  além da atribuição   inicial
(maior = -1), apenas uma nova atribuição acontecerá quando a primeira posição
do   vetor   for   verificada.   Logo, o melhor caso tem complexidade O(1).   Em
contrapartida, o pior caso acontecerá quando o vetor estiver ordenado de forma
crescente. Nesse caso, a variável maior receberá um novo valor a cada posição
verificada   do   vetor.   Logo,   para   um  vetor   de   tamanho n, serão   executadas n   +
1 atribuições, ou seja, a complexidade do pior caso é O(n).
5. A notação O, juntamente com outras duas notações complementares (ômega e
teta), possibilita descrever o comportamento assintótico de funções de maneira
precisa.
Sejam as funções f(n) = 6n2 e g(n) = n2log2(n), assinale a alternativa que expressa
corretamente a relação assintótica entre as duas funções.
Resposta correta.
E. g(n) é um limite superior para f(n).
É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)).
Para   isso,   é   preciso   provar   que   existem c e m positivos   tais   que,   para   todo   n
> m, é verdadeiro que f(n) <= cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2,
tem-se   que   6   <=   clog2(n).   Tomando-se c   =   6 e m   =   1,   essa   desigualdade   é
satisfeita. Portanto, g(n) é limite superior para f(n). Resta verificar se g(n) também
é um  limite  superior  para   f(n).  Nesse caso,  seria  verdadeiro  que n2log2(n)  <=
c'6n2, com c' positivo e n > m'  > 0. De maneira análoga, obtém-se que og2(n) <=
6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'.
Portanto, g(n) não é um limite superior para f(n). Consequentemente, g(n) também
não é um limite justo para f(n).
	Introdução à análise assintótica – Teoria dos Grafos e Análise de Algoritmos
	Exercícios