Analise Assintotica e Funcoes de Custo-Exercicios Resolvidos

1 FUNÇÕES DE CUSTO E ANÁLISE ASSINTÓTICA 1 Encontre a função de complexidade do custo das atribuições dos trechos de código a seguir a fork 0 k n 2 k fori k 1 i n i x vetkj vetki vetik vetik x b i 0 whilei n j 0 whilej n aij bij cij j i 2 c forx 0 j 1 j n j fori 1 i j i x d void funcaoint number int i j k fori 1 i 4 i forj i j n 1 j fork i k j 1 k number number i j k e forcnt3 0 i 1 i n i 2 forj 1 j n j cnt3 f forcnt4 0 i 1 i n i 2 forj 1 j i j cnt4 5 Qual das seguintes afirmações sobre o crescimento assintótico das funções não é verdadeira a 2n² 3n 1 On² b log n² Olog n c Se fn Ogn e gn Ohn então fn Ohn d Se fn Ogn então gn Ofn e 2n1 O2n f 22n O2n g fn Oun e gn Ovn então fn gn Oun vn h fn Oun e gn Ovn então fn gn Oun vn 6 Considere as seguintes funções 1 fn 2n 2 gn n 3 hn n log n Assinale a alternativa correta a respeito do comportamento assintótico de fn gn e hn a fn Ogn gn Ohn b fn Ωgn gn Ohn c gn Ofn hn Ofn d hn Ofn gn Ωfn e Nenhuma das anteriores 7 Considere a seguinte função em C void funcaoint n int ij fori 1 i n i forj 1 j logi j printfd i j Lembrese de que log n log 1 2 3 n log 1 log 2 log 3 log n n log n A complexidade dessa função é a Θn log n b Θn² c Θlog n d Θn e Θn² log n 1 d O laço mais externo vai de i 1 até i 3 Σ³ᵢ₁ gm fm O segundo laço vai de j i até j m Σᵐⱼᵢ hm gm O terceiro laço vai de k i até k j Σʲₖᵢ 1 j i 1 hm gm Σᵐⱼᵢ j i 1 Σᵐⱼᵢ j i Σᵐⱼᵢ 1 Σᵐⱼᵢ 1 m2 1m imi1 mi1 fm Σ³ᵢ₁ m2 1m i m i² i m i 1 3m2 1m 3m 3 Σ³ᵢ₁ im2 Σ³ᵢ₁ i² 3m2 1m 3m 3 m2 6 14 3m²2 3m2 3m 6m 3 12 14 3m²2 3m2 5 e O laço mais externo vai de i 1 até i m multiplicando por 2 Ou seja i 1 2 4 8 m portanto é executado log₂m vezes O laço interno vai de j 1 até m fm Σᵐᵢ₁ Σᵐⱼ₁ 1 Σᵐᵢ₁ m m log₂m f O laço externo vai de i 1 até i m multiplicando por 2 podemos escrever da seguinte forma Σˡᵒᵍ₂mᵢ₀ gm fm O laço interno vai de j 1 até j i2 Δ gm Σ²ⁱⱼ₁ 1 2ⁱ fm Σˡᵒᵍ₂mᵢ₀ 2ⁱ 2⁰ 2¹ 2² 2ˡᵒᵍ₁₂m 2m g cont 0 fori 0 i n 4 i forj i j n j cont h Técnica de eliminação de Gauss para transformar a matriz em uma matriz triangular superior fori 0 i n i ifaii 00 printfErro break forj i 1 j n j ratio ajiaii fork 0 k n k ajk ajk ratio aik 2 O algoritmo apresentado no slide 32 para encontrar a maior sequência crescente em um vetor é ineficiente já que não há necessidade de continuar a procurar outra sequência no vetor se o comprimento já encontrado é maior do que o comprimento da próxima sequência ou subvetor a ser analisado Assim se o vetor inteiro já está em ordem crescente podemos parar a busca convertendo o pior caso no melhor caso A mudança necessária está no laço mais externo que agora tem mais um teste fori 0 comprimento 1 i n 1 comprimento n i i Qual é o pior caso agora A eficiência do pior caso é ainda uma função de custo de complexidade quadrática 3 Para cada função a seguir encontre os pares de valores para c e n0 para cada função de acordo com o limite assintótico superior e inferior isto é Ogrande e Ωgrande a fn 3n3 2n2 n b fn 2n2 4n 15 c fn 3n 7 d gn 3n2 1 e fn 5 log2 n 4 Classifique cada par de funções fn e gn a seguir para verificar se gn é um limite assintótico para fn tais como fn Ogn fn Ωgn e fn Θgn a fn 3n 7 e gn 5n 2 b fn 5 log2 n 7 e gn 5n 1 c fn 5 2n 3 e gn 3n2 5n d fn 5n 7 e gn 3n2 1 e fn 5n 7 e gn 3n2 1 f fn n2 3n 7 e gn n3 2n 1 1 a O laço mais do for pode ser representado como k0m3 O laço mais interno pode ser representado como ik1m3 1 m k Portanto fm k0m3 m k k0m3 m k0m3 k mm2 0 m 3 m22 m2 2m m22 5m2 62 m22 m2 3 b O laço mais externo vai de 0 a m1 incrementando de 2 em 2 ou seja é executado m2 vezes i0m21 gm onde gm é a curto do laço interno O laço mais interno vai de 0 a m gm j0m 1 m 1 fm j0m21 m 1 m 1 i0m21 1 m 1m 12 1 m22 m2 m m 12 1 m22 m 12 c O laço mais interno vai de i 1 até i j gm j1j 1 j O laço mais externo vai de j 1 até j m j1m gm Portanto fm j1m j 1 2 3 m m2 m 1 7 A quantidade de vezes que a função printf é chamada é logi vezes dentro do laço de i que varia de 1 a m fm i1m logi m log m portanto Θm log m RESPOSTA a 6 As possibilidades seriam descritas pela tabela abaixo Ofm Ogm Ohm Ωfm Ωgm Ωhm fm V V V V F F gm F V F V V V hm F V V V F V Nenhuma alternativa se encaixa nas relações da tabela portanto a resposta é E 5 g fm Oum c1 um fm gm Ovm c2 vm gm SOMANDO AS DESIGUALDADES c1 um c2 vm fm gm Escolhendo C max c1 c2 Temos C um vm fm gm Portanto fm gm Oum vm Alternativa verdadeira h c1 um fm c2 vm gm SUBTRAINDO AS DESIGUALDADES c1 um c2 vm fm gm Tomando um contraexemplo um m3 fm m2 vm m gm m A desigualdade não é verdadeira portanto a afirmação é falsa 5 a fm 2m2 3m 1 Om2 pois 100 m2 fm V VERDADEIRA b fm log m2 Olog m pois 3 log m 2 log m V VERDADEIRA c VERDADEIRA fm c1 gm V m m0 D fm Ogm gm c2 hm D c1 gm c1 c2 hm fm c1 c2 hm V m m0 D fm Ohm d FALSA Contraexemplo fm m gm m fm Ogm mas gm não pode ter Ofm e VERDADEIRA fm 2 2m Oxm 3 2m 2 2m V m 1 f FALSA fm 2m gm 2m pois C 2m c 2m V m m0 Analisando a inequação D log2 3m log2 c log2 2m 2m log2 c m m log2 c Como c é constante à medida que m cresce a desigualdade se torna falsa 3 e fm 5 log2 m Ogrande 5 log2 m c log2 m c 5 m0 1 Q grande 5 log2 m c log2 m c 5 m0 1 4 a fm Ogm b fm Ogm c fm Ω gm d fm Ogm e fm Ogm f fm Ω gm 3 a fm 3m3 2m2 m Ogrande 3m3 2m2m cm3 3 2m 1m2 c m01 c6 Ωgrande 3m3 2m2 m cm3 c3 m01 b fm2m2 4m 15 Ogrande 2m2 4m 15 c m2 2 4m 15m2 c c3 m0 1 Ωgrande 2m2 4m 15 c m2 c1 m03 c fm 3m 7 Ogrande 3m 7 c m 3 7m c c10 m0 1 Ωgrande 3m 7 c m c3 m01 d gm 3m2 1 Ogrande 3m2 1 c m2 c4 m01 Ωgrande 3m2 1 c m2 c3 m01 2 Sem perda de generalidade somos supi m par O pior caso agora é um vetor com sua metado crescente 1 2 3 4 m2 1 2 3 4 m2 Na primeira iteracão somos identifico o comprimento máximo de tamanho m2 porém ainda vai chegar ás próximas m2 posições gm i1 até m2 ji até m2 1 1 i1 até m2 m2 i 1 Om2 1 a O laço externo vai de i0 a im mod 4 1 fm i0 até m mod 4 1 gm O laço interno vai de ji a jm1 gm ji até m1 1 mi fm i0 até m mod 4 1 m i0 até m mod 4 1 i mm mod 4 1 m mod 4 m mod 4 12 FAZENDO k m mod 4 fm m k 1 k2 k1 fm m k n k22 k2 h O primeiro laço vai de i0 a in1 fm i0 até m1 gm O segundo laço vai de jj1 a jn1 gm ji1 até m1 hm O terceiro laço vai de k0 a km1 hm k0 até m1 1 m gm ji1 até m1 m mm1i11 m mi1 m2 m i m fm i0 até m1 m2 m i0 até m1 i m i0 até m1 1 m3 m32 mm2 m1 fm m3 m32 m22 m22 m32 m32