Lista 2 Noções de Análise de Algoritmos

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
Curso: Engenharia de Produção 1o semestre de 2018
Disciplina: Algoritmos e Estruturas de Dados I Data: 10/05/18
Professor: Alexandre Magno de Sousa
Noções de Análise de Complexidade
1. Encontre a função de complexidade do custo das atribuições dos seguintes trechos de código:
(a) for(k = 0; k < n - 2; k++)
for(i = k + 1; i <= n; i++){
x = vet[k][j];
vet[k][i] = vet[i][k];
vet[i][k] = x;
}
(b) i = 0;
while(i < n){
j = 0;
while(j <= n){
a[i][j] = b[i][j] + c[i][j];
j++;
}
i += 2;
}
(c) for(x = 0, j = 1; j <= n; j++)
for(i = 1; i <= j ; i++)
++x;
(d) void funcao(int *number){
int i, j, k;
for (i = 1; i < 4; i++)
for (j = i; j < n + 1; j++)
for (k = i; k < j + 1; k++)
*number = *number + i + j + k;
}
2. Considere o problema onde existem um conjunto de 2n números inteiros distintos, dos quais
n são sorteados aleatoriamente para compor um vetor A de tamanho n. Considere agora
que você quer pesquisar se um elemento x qualquer dentre os 2n elementos está presente
no vetor, retornando o índice dele, caso esteja presente, ou -1, caso não esteja. Dê o que se
pede:
(a) Escreva um algoritmo de pesquisa linear que percorre o vetor sequencialmente procu-
rando pelo valor x.
(b) Qual é a função de complexidade do seu algoritmo para o número de comparações
de elementos no melhor caso, pior caso e caso médio. Para o caso médio, leve em
consideração uma pesquisa com sucesso e uma pesquisa sem sucesso e calcule baseado
na distribuição de probabilidade do número de elementos do conjunto.
(c) Se você criasse um algoritmo que fizesse uma busca no vetor pelo elemento x de maneira
que não utilizasse um laço de repetição mas sorteasse aleatoriamente um índice entre
0 e n e que realizasse uma única comparação para verificar se o elemento no índice
sorteado é igual ao elemento x, qual seria a probabilidade de encontrar o elemento
pesquisado?
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
3. Qual das seguintes afirmações sobre o crescimento assintótico das funções não é verdadeira:
(a) 2n2 + 3n + 1 = O(n2).
(b) logn2 = O(logn).
(c) Se f(n) = O(g(n)) e g(n) = O(h(n)), então f(n) = O(h(n)).
(d) Se f(n) = O(g(n)), então g(n) = O(f(n))
(e) 2n+1 = O(2n).
(f) 22n = O(2n).
(g) f(n) = O(u(n)) e g(n) = O(v(n)) então f(n) + g(n) = O(u(n) + v(n))
(h) f(n) = O(u(n)) e g(n) = O(v(n)) então f(n)− g(n) = O(u(n)− v(n))
4. Sejam duas funções f(n) e g(n) que mapeiam números inteiros positivos em números reais
positivos. Com respeito às notações assintóticas de complexidade, avalie as afirmativas a
seguir.
A análise PERMITE CONCLUIR que
I. Diz-se que f(n) é O(g(n)) se existe uma constante real c > 0 e existe uma constante
inteira n0 ≥ 1 tal que f(n) ≤ c× g(n) para todo inteiro n ≥ n0.
II. Diz-se que f(n) é o(g(n)) se para toda constante real c > 0 existe uma constante inteira
n0 ≥ 1 tal que f(n) < c× g(n) para todo inteiro n ≥ n0.
III. Diz-se que f(n) é Ω(g(n)) se existe uma constante real c > 0 e existe uma constante
inteira n0 ≥ 1 tal que f(n) ≥ c× g(n) para todo inteiro n ≥ n0.
IV. Diz-se que f(n) é ω(g(n)) se para toda constante real c > 0 existe uma constante
inteira n0 ≥ 1 tal que f(n) > c× g(n) para todo inteiro n ≥ n0.
V. Diz-se que f(n) é Θ(g(n)) se, e somente se, f(n) é O(g(n)) e f(n) é Ω(g(n)).
(a) todas as afirmativas são falsas.
(b) todas as afirmativas são verdadeiras.
(c) apenas as afirmativas I e III são verdadeiras.
(d) apenas as afirmativas II e IV são verdadeiras.
(e) apenas a afirmativa V é falsa
5. Observe as funções representadas no gráfico da Figura 1. Assinale a afirmativa FALSA
sobre o crescimento assintótico dessas funções:
(a) f(n) = O(h(n)) e i(n) = Ω(g(n)).
(b) f(n) = Θ(h(n)) e i(n) = Ω(h(n)).
(c) g(n) = O(i(n)) e h(n) = Ω(g(n)).
(d) g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n)).
(e) h(n) = Ω(i(n)), logo, i(n) = O(h(n)).
Page 2
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
Figura 1: comportamento assintótico das funções f(n), g(n), h(n) e i(n).
Page 3