Exercicio Analise De Algoritmo

Universidade Federal do Piau { UFPI

Universidade Aberta do Piau { UAPI

Bacharelado em Sistemas de Informac~ao

Projeto e Analise de Algoritmos

Prof.: Jose Ricardo Mello Viana Perodo: 2014.1

Lista de exerccios - Gabarito

1. Expresse a func~ao n3=1000 .. 100n2 .. 100n + 3 em termos da notac~ao :

R: (n3). Leva-se em considerac~ao apenas o maior expoente.

2. Analise o algoritmo abaixo e identique seu pior caso usando a notac~ao 

exibe matriz 3D(M)

for i 1 to comprimento x[M]

for j 1 to comprimento y[M]

for k 1 to comprimento z[M]

do escreva(M[i][j][k]))

R: Considerando a dimens~ao da matriz M de entrada n x n x n, temos que o

primeiro for leva, no pior caso, (n). Da mesma forma o segundo for tambem

leva (n). E o terceiro for tambem levara o mesmo tempo (n). Como os

tr^es for est~ao aninhados, para calcular a complexidade total multiplicamos

os 3 valores encontrados, o que nos leva a n . n . n = (n3)

3. Considere a ordenac~ao de n numeros armazenados no arranjo A, localizando primeiro

o menor elemento de A e trocando esse elemento com o contido em A[1]. Em seguida,

encontre o segundo menor e troque com o da posic~ao A[2]. Continue dessa maneira

para os n - 1 primeiros elementos de A. Escreva o pseudocodigo para esse algoritmo

conhecido como ordenac~ao por selec~ao e calcule o tempo do pior caso de execuc~ao

deste algoritmo escrevendo-o segundo a notac~ao .

R: Algoritmo

ordena vetor(A)

for i 1 to comprimento[A]

menor A[i]

for j i + 1 to comprimento[A]

se menor  A[j] ent~ao

menor A[j]

A[i] menor

A complexidade desse algoritmo e O(n2), pois temos um for dentro do outro

e, no pior caso, cada um deles executa n passos.

4. Suponhamos 2 algoritmos de ordenac~ao, A e B. Vamos executa-los na mesma maquina.

A e executado em 8n2 etapas, enquanto B necessita de 64n log n. Qual dos dois

e melhor? Em que condic~oes? (Suponha n pot^encia de 2).

R:

1 2 4 8 16 32 64 128

8n2 8 32 128 512 2048 8192 32768 131072

64n log n 0 128 512 1536 4096 10240 24576 57344

Vemos que ate valores de n iguais a 32 (excetuando n=1) a func~ao 8n2 e

melhor, ou seja, leva menos passos. A partir da, para qualquer valor maior,

a func~ao 64n log n tras resultados mais rapidamente. Se considerassemos o

pior caso, a segunda func~ao seria melhor, pois nos importamos apenas com

valores muito grandes de n (para um n t~ao grande quanto se queira).

5. Coloque em ordem crescente de complexidade as principais classes de problemas

listadas a seguir.

O(n!); O(n log n); O(n); O(log n); O(1); O(2n); O(n3);O(n2)

R: O(1); O(log n); O(n); O(n log n); O(n2); O(n3); O(2n); O(n!)

6. Dizemos que f(n) e O(g(n)) se f(n) < c  g(n) para todo n > n0. Sabemos que um

algoritmos com custo (n+1)2 e O(n2). Encontre valores para c e n0 que conrmem essa

armac~ao.

R: n2 < c  (n + 1)2

n2 < c  (n2 + 2n + 1)

n2 < cn2 + c2n + c

n2 .. cn2 < c2n + c ! (Podemos escolher convenientemente c = 1)

n2 .. 1  n2 < 1  2n + 1

n2 .. n2 < 2n + 1

0 < 2n + 1

2n + 1 > 0

2n > ..1

n > ..1=2

Podemos usar os valores c = 1 e n0 = ..1=2

7. Dado um algoritmo para encontrar o maior valor em um vetor:

2

int max(int vet[ ], int n)f

int maior = vet[0];

for (int i = 1; i < n; i++) f

if