Baixe o app para aproveitar ainda mais
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.
Compartilhar