Exercícios Análise de Complexidade

Prévia do material em texto

Instituto Nacional de Telecomunicac¸o˜es
AC309 - Atividades Complementares
Prof. Carlos Alberto Ynoguti
Ana´lise de Complexidade, Algoritmos de Ordenac¸a˜o e Busca
1. Calcule a notac¸a˜o ‘O’ das func¸o˜es abaixo. Mostre cada passo do desenvolvimento
(a) f(n) =
n(n+ 1)
2
(b) f(n) = 2n log2(n/3) +
n(n− 1)
2
(c) f(n) = n · (n− 1) · (n− 2) . . . 3 · 2 · 1
(d) f(n) = n2(n− 3) + 2n
2. Determine f(n) para os trechos de programa a seguir
i=1;
while (i<N)
{
{conjunto de instruc¸~oes;}
i = i+3;
}
i=N;
while (i>=1)
{
{conjunto de instruc¸~oes;}
i=i/3;
}
for (i=0;i<N;i++)
for (j=1;j<M;j *=2)
{conjunto de instruc¸~oes;}
for (i=0;i<N;i++)
for (j=0;j<M;j++)
{conjunto de instruc¸~oes;}
3. Um vetor conte´m os elementos exibidos a seguir. Mostre o conteu´do do mesmo depois de
ter sido executada a primeira passagem dos algoritmos:
(a) Bubble Sort
(b) Quick Sort
0 1 2 3 4 5 6 7 8 9 10 11 12
24 4 8 14 90 8 67 27 45 19 91 99 58
4. Determine quantas comparac¸o˜es seriam necessa´rias para encontrar o elemento 67 no vetor
ordenado do exerc´ıcio anterior usando:
(a) a busca sequencial;
(b) a busca bina´ria