Analise de Algoritmos e Estruturas de Dados - Complexidade e Busca em Grafos

4 No desenvolvimento de um sistema um analista utilizou um algoritmo que soluciona um problema dividindoo em 8 subproblemas cada uns dos quais com um tamanho 12 do tamanho original Levando um tempo de On² para dividir o problema em subproblemas e combinar as soluções dadas aos subproblemas na solução para o problema original Se é conhecido que o tempo do algoritmo quando n1 é Tn1 a Defina a relação de recorrência para a solução proposta pelo analista b Resolver a recorrência usando o método iterativo expansão ou soma telescópica b Obter limites assintóticos da recorrência usando o teorema mestre Na figura se mostra um algoritmo na linguagem C para incrementar o valor de duas variáveis void p2 int n int i j x y x y 0 for i1 in i for ji jn j x x 1 for j1 ji j y y 1 a Calcule a complexidade do algoritmo para o pior caso Deve definir os somatórios para o cálculo e mostrar a complexidade assintótica do algoritmo b Qual é a complexidade no melhor caso c Que propriedades da notação Big O foi preciso utilizar no cálculo da complexidade do algoritmo 2 No Grafo da figura a Represente a ordem em que podem ser visitados os vértices usando uma busca em largura b Qual é a complexidade do algoritmo utilizado c Que outra estrutura de dados auxiliar é preciso usar no algoritmo de busca em largura d Qual paradigma de projeto de algoritmo pode ser utilizado para o problema de visitar todos os vértices na busca em largura Questão 1 a Vamos inicialmente considerar que as linhas int i j x y x y 0 x x 1 y y 1 possuem custo unitário O número de iterações será dado pelo 𝐶 número de vezes que as instruções são executadas Portanto os laços for representam somatórios Logo a quantidade de instruções executadas é dada por 𝐶 𝐶 𝑖1 𝑛 𝑗𝑖 𝑛 𝐶 𝑗1 𝑖1 𝐶 2𝐶 𝑖1 𝑛 𝑗1 𝑛 𝐶 2𝐶 𝑖1 𝑛 𝐶𝑛 2𝐶 𝐶𝑛 2 Portanto a complexidade do algoritmo é 𝑂𝑛 2 b Se teremos sempre a mesma ordem de complexidade 𝑛 0 quadrática Porém se temos que os laços não serão executados 𝑛 0 logo o algoritmo tem complexidade constante neste caso c Foi utilizado as seguintes propriedades onde e 𝑎𝑝𝑛 𝑝 𝑎𝑝1𝑛 𝑝1 𝑎0𝑛 0 𝑂𝑎𝑝𝑛 𝑝 𝑎𝑝 0 𝑝 1 onde e 𝑎𝑝𝑛 𝑝 𝑂𝑛 𝑝 𝑎𝑝 0 𝑝 0 Questão 2 a A Z P N T I K F b onde é o número de vértices e é o número de 𝑂𝑉 𝐸 𝑉 𝐸 arestas c A estrutura de dados fila d Programação dinâmica Questão 4 a 𝑇𝑛 8𝑇 𝑛 2 𝑂𝑛 2 𝑇1 1 b 𝑇𝑛 8𝑇 𝑛 2 𝑛 2 𝑇𝑛 88𝑇 𝑛 4 𝑛 2 2 𝑛 2 88𝑇 𝑛 4 𝑛 2 4 𝑛 2 64𝑇 𝑛 4 2𝑛 2 𝑛 2 𝑇𝑛 648𝑇 𝑛 8 𝑛 4 2 2𝑛 2 𝑛 2 648𝑇 𝑛 8 𝑛 2 16 2𝑛 2 𝑛 2 𝑇𝑛 512𝑇 𝑛 8 4𝑛 2 2𝑛 2 𝑛 2 𝑇𝑛 8 𝑘𝑇 𝑛 2 𝑘 2 𝑘1𝑛 2 4𝑛 2 2𝑛 2 𝑛 2 2 𝑘 3𝑇 𝑛 2 𝑘 𝑛 2 𝑖0 𝑘1 2 𝑘 𝑇𝑛 2 𝑘 3𝑇 𝑛 2 𝑘 𝑛 2 2 𝑘 1 Se temos que 𝑛 2 𝑘 𝑘 𝑙𝑔 𝑛 𝑇𝑛 𝑛 3𝑇1 𝑛 2 𝑛 1 𝑇𝑛 𝑛 3 1 𝑛 3 𝑛 𝑇𝑛 2𝑛 3 𝑛 𝑇𝑛 Θ𝑛 3 c Se pensarmos na recorrência na forma temos que 𝑇𝑛 𝑎𝑇 𝑛 𝑏 𝑛 𝑐 e 𝑎 8 𝑏 2 𝑐 2 Como temos que pelo teorema mestre 𝑛 𝑐 𝑂𝑛 𝑙𝑔𝑎 𝑏 𝑇𝑛 𝑂𝑛 𝑙𝑔𝑎 𝑏 𝑂𝑛 𝑙𝑔2 8 𝑂𝑛 3 Questão 1 a Vamos inicialmente considerar que as linhas int i j x y x y 0 x x 1 y y 1 possuem custo unitário C O número de iterações será dado pelo número de vezes que as instruções são executadas Portanto os laços for representam somatórios Logo a quantidade de instruções executadas é dada por CC i1 n 2C i1 n j1 n C 2C i1 n Cn 2CC n 2 Portanto a complexidade do algoritmo é On 2 b Se n0 teremos sempre a mesma ordem de complexidade quadrática Porém se n0 temos que os laços não serão executados logo o algoritmo tem complexidade constante neste caso c Foi utilizado as seguintes propriedades a pn pap1n p1a0n 0Oapn p onde a p0 e p1 a pn pOn p onde a p0 e p0 Questão 2 a A Z P N T I K F b O onde V é o número de vértices e E é o número de arestas c A estrutura de dados fila d Programação dinâmica Questão 4 a T n8T n 2On 2 T 11 b T n8T n 2n 2 T n8 T n64 T n512T n 8 4n 22n 2n 2 T n8 kT n 2 k 2 k1n 24n 22n 2n 2 T n Se n2 k klgn temos que T nn 3T 1n 2n1 T nn 31n 3n T n2n 3n T nΘn 3 c Se pensarmos na recorrência na forma T naT n b n c temos que a8 b2 e c2 Como n cOn lga b temos que pelo teorema mestre T nOn lga b On lg2 8 On 3