Notação Assintótica - Estrutura de Dados

soma soma 1 3 Combinacao de Funcoes Consr s unos fn 3n3 2n2 gn 5n3 Dtrmn s fn Θgn 4 Analise de Tempo de Execucao Pr o lortmo xo trmn noto ssntot o tmpo xuo algoritmo buscan se n 1 entao retorna 0 retorna buscan2 1 Calcule 5 O O O 6 S O O O 7 n On n On 8 n On n Ωn 9 n n θmnn n 10 n n θmxn n 11 7n² On 12 2n1 O2n 13 3n ω2n 14 n3 n2 ωn2 15 S fn On lo n nto fn ωn 2 16 n 10 On 17 S fn ogn nto gn ωfn 18 S fn Θgn nto fn gn Θgn 19 lon2 Θlo n 20 S fn Θn2 gn On nto fn gn Θn2 21 n12 on 22 S fn ωgn nto fn Ωgn 23 fn gn Θmxfn gn s fn Ogn 24 fn gn Omxfn2 gn2 25 mxn lo n Θn 26 mxn2 n lo n Θn2 27 mx2n n10 Θ2n 28 mxn3 n3 lo n Θn3 lo n 29 mxlo n n n100 Θn 30 mxn n2 n3 Θn3 3 Exercícios sobre Notação Assintótica Instruções Resolva os seguintes exercícios sobre notação assintótica Justifique todas as suas respostas As respostas deverão ser exclusivamente em manuscrito escrito à mão O a discente deverá tirar foto da folha de resposta e gerar um pdf para enviar no UFLA Virtual Respostas sem identificação da questão ou com problema de legibilidade serão avaliadas em 0 pontos Questões digitadas serão avaliadas em 0 pontos Caso a afirmativa seja falsa prove via contraexemplo mas você não deve provar uma afirmativa verdadeira com contraexemplo 1 Comparação de Funções Considere as funções fn 2n² 3n 1 e gn n² Mostre que fn Ogn 2 Análise de Algoritmo Dado o seguinte pseudocódigo determine a complexidade assintótica em termos de O algoritmo exemplon soma 0 para i de 1 até n faça para j de 1 até i faça Respostas das Questoes de Notacao Assintotica Questoes Iniciais Funcoes fn e gn Considere as funcoes fn 3n3 2n2 e gn 5n3 Determine se fn Θgn Resposta Verdadeiro Justificativa Observe que ambos fn e gn sao polinˆomios cujo termo dominante e da ordem n3 Assim existem constantes positivas c1 c2 e n0 tais que para todo n n0 temos c1 gn fn c2 gn Por exemplo podemos escolher c1 3 5 e c2 1 pois para n suficientemente grande 3 5 5n3 3n3 3n3 2n2 5n3 1 5n3 Portanto fn Θgn Algoritmo busca Considere o algoritmo abaixo algoritmo buscan se n 1 entao retorna 0 retorna buscan2 1 Resposta A notacao assintotica do tempo de execucao deste algoritmo e Olog n Justificativa A cada chamada recursiva o valor de n e dividido por 2 de modo que o numero de chamadas e proporcional a log2n Portanto o tempo de execucao cresce como log n 1 Questoes de 5 a 30 1 Of g Of Og Resposta Verdadeiro Justificativa Seja fn Of1n e gn Og1n Entao fn gn Of1n Og1n De forma intuitiva a notacao BigO de fn gn nao excede a soma das notacoes BigO de f e g Em geral costumase simplificar dizendo que Of g Omaxf g 2 Se g Of e h Of entao g Oh Resposta Falso ExemploContraexemplo Tome fn n gn n e hn 1 Temos gn n On Ofn e hn 1 On Ofn Porem gn n nao e O1 Ohn 3 fn Ogn gn Ofn Resposta Falso Exemplo Seja fn n e gn n2 E verdade que n On2 mas n2 On Logo a implicacao nao vale de forma geral 4 fn Ogn gn Ωfn Resposta Verdadeiro Justificativa Por definicao fn Ogn significa que existem c 0 e n0 tais que para n n0 fn c gn Isso implica diretamente que gn Ωfn 5 fn gn Θminfn gn Resposta Falso Exemplo Seja fn n e gn 1 Entao fn gn n 1 Θn ao passo que minfn gn 1 Θ1 Portanto Θn Θ1 Logo a afirmacao e falsa 6 fn gn Θmaxfn gn Resposta Verdadeiro Justificativa Quando somamos duas funcoes para n grande a funcao que tiver a maior ordem de crescimento domina a soma Por isso fn gn Θmaxfn gn 2 7 7n² On Resposta Falso Justificativa n² cresce mais rapidamente que n Então não existe constante c tal que 7n² c n para todo n grande 8 2n1 O2n Resposta Verdadeiro Justificativa 2n1 2 2n Portanto basta tomar c 2 e verificar 2n1 c 2n 9 3n ω2n Resposta Verdadeiro Justificativa lim n 3n2n lim n 32n Logo 3n cresce mais rapidamente que 2n 10 n³ n² ωn² Resposta Verdadeiro Justificativa O termo dominante de n³ n² é n³ e n³n²n² Assim é ωn² 11 Se fn On log n então fn ωn Resposta Falso ExemploContraexemplo Considere fn n De fato n On log n Mas dizer fn ωn significaria que lim n nn o que é falso a razão é 1 Assim n não é ωn portanto a implicação é falsa 12 n 10 On Resposta Verdadeiro Justificativa Para n 100 por exemplo temos n 10 n n 2 n Logo n 10 On 13 Se fn ogn então gn ωfn Resposta Verdadeiro Justificativa Por definição fn ogn significa que lim n fngn 0 Isso é equivalente a dizer que lim n gnfn isto é gn ωfn 14 Se fn Θgn então fn gn Θgn Resposta Verdadeiro Justificativa Se fn Θgn então para n grande fn e gn são do mesmo nível de ordem de grandeza Assim a soma também será do mesmo nível Θgn 15 logn² Θlog n Resposta Verdadeiro Justificativa logn² 2 log n Como constantes multiplicativas não afetam a notação Θ temos logn² Θlog n 16 Se fn Θn² e gn On então fn gn Θn² Resposta Verdadeiro Justificativa Uma função Θn² domina qualquer On logo Θn² On Θn² 17 n¹² on Resposta Verdadeiro Justificativa lim n n¹²n lim n 1n¹² 0 Portanto n¹² on 18 Se fn ωgn então fn Ωgn Resposta Verdadeiro Justificativa ωgn significa que fn cresce estritamente mais rápido que gn Isso obviamente implica fn ser pelo menos Ωgn ou seja cresce no mínimo tão rápido quanto gn e de fato mais 19 fn gn Θmaxfn gn se fn Ogn Resposta Verdadeiro Justificativa Se fn Ogn então há alguma constante c tal que fn c gn para n suficientemente grande Logo maxfn gn gn em ordem de grandeza e assim fngn Θgn Θmaxfn gn 20 fn gn Omaxfn² gn² Resposta Verdadeiro Justificativa Sem perda de generalidade se fn gn para n grande então fn gn gn² Se ocorrer o contrário gn fn temos fn gn fn² Portanto fn gn maxfn² gn² 21 maxn log n Θn Resposta Verdadeiro Justificativa Para n 2 n é maior ou igual a log n Portanto maxn log n n e isso é Θn 22 maxn² n log n Θn² Resposta Verdadeiro Justificativa Para n suficientemente grande n² domina n log n Assim o máximo entre eles é n² e maxn² n log n Θn² 23 max2n n10 Θ2 Resposta Falso Justificativa Para n suficientemente grande 2n cresce mais rapido que n10 Logo max2n n10 2n que e Θ2n e nao Θ2 24 maxn3 n3 log n Θn3 log n Resposta Verdadeiro Justificativa Para n 2 n3 log n e maior ou igual que n3 Portanto a expressao maxima e n3 log n que e Θn3 log n 25 maxlog n η η100 Θη Resposta Verdadeiro Justificativa Assumindo que η cresce por exemplo η n para valores suficientemente grandes η100 domina log n e n Logo maxlog n n n100 Θn 26 maxn n2 n3 Θπ3 Resposta Falso Justificativa maxn n2 n3 e n3 para n grande e isso e Θn3 π3 e apenas uma constante entao nao faz sentido dizer que maxn n2 n3 e Θπ3 5