Lista 02 - Respondida

Prévia do material em texto

UNIVERSIDADE CATÓLICA DE GOIÁS 
Departamento de Computação 
 
 
Estrutura de Dados 2 
 
 
Exercícios – Lista 2 
 
 
1. A função de complexidade de tempo G foi determinada para um programa. Que 
termo domina assintoticamente G? 
G(n) = 9999999n + 0,0001n2 + n.log(log(n)) + n2/(n - 99) + 0,9n 
 
Resposta: 0,0001n2 
 
2. Qual é a medida de complexidade de tempo para a seguinte rotina que 
multiplica duas matrizes quadradas A e B e armazena o resultado em C? 
for i:=1 to n do 
 begin 
 for j:=1 to n do 
 begin 
 sum:=0; 
 for k:=1 to n do 
 begin 
 sum:=sum + a[i,k]*b[k,j] 
 end; 
 c[i,j]:=sum 
 end 
 end; 
 
Resposta: O(n3) 
3. Coloque em ordem crescente as seguintes funções de complexidade: O(n3), 
O(n.log n), O(1), O(n5), O(2n), O(n!), O(log n), O(n.2n), O(n2), O(n1/2), O(n). 
 
Resposta: O(1), O(log n), O(n1/2), O(n), O(n.log n), O(n2), O(n3), O(n5), O(2n), 
O(n.2n), O(n!). 
 
4. Suponha que uma empresa utiliza um algoritmo de complexidade n2 que, em 
um tempo t, na máquina disponível, resolve um problema de tamanho x. 
Suponha que o tamanho do problema a ser resolvido aumentou em 41%, mas o 
tempo de resposta deve ser mantido. Para isso, a empresa pretende trocar a 
máquina por uma mais rápida. Quão mais rápida deve ser a máquina nova? 
 
Resposta: para a máquina atual (onde f(n) = n2) temos que para um tamanho 
de problema x f(n=x) = x2 , ou seja, são necessárias x2 operações, o que 
equivale a um tempo t; para a máquina nova (k vezes mais rápida, isto é f´(n) 
= n2/k), e um tamanho de problema 41% maior, f´(n=1,41.x) = (1,41.x)2/k; 
como o tempo deve ser o mesmo, temos que (1,41.x)2/k operações devem 
corresponder ao número de operações correspondentes ao tempo t, ou seja 
x2; assim, (1,41.x)2/k = x2 , ou k = 1,99; ou seja, a máquina nova deve ser 
aproximadamente 2 vezes mais rápida. 
 
5. Explique os seguintes termos: problema tratável, algoritmo exponencial, 
algoritmo polinomial, problema intratável. Cite um exemplo de um problema 
tratável e de um intratável. 
 
Resposta: Algoritmo polinomial é aquele cuja função de complexidade é 
O(nc), para c > 0; Algoritmo exponencial é aquele cuja função de 
complexidade é O(cn), para c > 1; Um problema é considerado intratável 
quando ele é tão difícil que não existe um algoritmo polinomial para resolvê-
lo, enquanto um problema é considerado tratável (ou bem resolvido) quando 
existe um algoritmo polinomial para resolvê-lo. Exemplos: Problema tratável – 
ordenação, Problema intratável - caixeiro viajante.