Lista de Exercicios Resolvidos - Complexidade de Algoritmos e Notacao Big O

EXERCÍCIOS Complexidade de Tempo de Algoritmos Teoria da Computação 20222 Dupla Observação 1 Este exercício não deve ser manuscrito e nem conter imagens com detalhes manuscritos Observação 2 Deve ser mantida a formatação do texto e os enunciados dos exercícios propostos 1 Apresente a definição formal da notação O O grande 2 A somatória dos números de 1 até n pode ser calculada através da fórmula somatn 1n2n Escreva uma função usando uma notação similar à linguagem C que calcule a somatória de 1 até n usando esta fórmula e calcule a complexidade de pior caso da sua função obtida Qual função é mais eficiente a sua ou aquela anteriormente apresentada em aula Justifique 3 Escreva uma função para realizar busca sequencial em um vetor de números inteiros e calcule a complexidade da sua função nas seguintes situações melhor caso quando o elemento buscado se encontra na primeira posição do vetor e pior caso quando o elemento buscado não ocorre no vetor 4 Considerando uma função chamada outraFn de complexidade de tempo n2 qual será a complexidade de tempo do melhor e do por caso do código abaixo Calcule cuidadosamente Note que a linha do for foi quebrada em 3 pois cada parte tem uma quantidade de execuções diferente das demais for int i 0 i n i if arri k k e constante outraFn 5 Considerando uma função chamada outraFn de complexidade de tempo 1 qual será a complexidade de tempo do melhor e do por caso do código abaixo Calcule cuidadosamente for int i 0 i 100 i if arri k k e constante outraFn Teoria da Computação 20222 LISTA 1 Apresente a definição formal da notação O O grande RESOLUÇÃO Conforme o Wikipedia a definição matemática formal da notação O grande é tal que dadas duas funções fx e gx ambas definidas no mesmo subconjunto dos números reais temos que fx O gx x se e somente se existe uma constante positiva M tal que para todo valor suficientemente grande de x o módulo de fx é no máximo M multiplicado pelo módulo de gx M x0 fx M gx x x0 1 2 A somatória dos números de 1 até n pode ser calculada através da fórmula somatn 1 n2 n Escreva uma função usando uma notação similar à linguagem C que calcule a somatória de 1 até n usando esta fórmula e calcule a complexidade de pior caso da sua função obtida Qual função é mais eficiente a sua ou aquela anteriormente apresentada em aula Justifique RESOLUÇÃO Para usar a fórmula bastanos apenas aplicar a mesma detro da função veja 1 int somatint n 2 return nn12 3 A escolha dessa ordem das operações foi feita para que o número a ser dividido por 2 seja sempre par resultando sempre em um número inteiro visto que variáveis do tipo ponto flutuante tem quase sempre erros de arredondamento Vamos agora de fato analisar a complexidade do algoritmo se comparado à função dada em aula Na versão estudada em aula os números a serem somados são percorridos de 1 até n e somados individualmente ou seja o número de operações realizadas é proporcional a n isto é a complexidade é O n Para a função feita nesse exercício e exibida acima temos apenas uma operação independente do valor do parâmetro e independente se é melhor ou pior caso de forma que a complexidade é O 1 Dessa forma podemos dizer que para grandes valores de n a função desse exercício é mais eficiente Mas aproveitando a oportunidade é bom destacar que isso não necessariamente é válido para qualquer valor de n vejamos por exemplo o seguinte teste comparando as duas funções 1 include timeh 2 include stdioh 3 4 int somatint n 5 return nn12 6 7 8 int somatoriaaulaint n 9 int result 0 10 int i 1 11 whilei n 12 result 1 13 i 14 15 return result 16 17 18 int main 19 int n 10000 20 clockt t0 t 21 t0 clock 22 somatn 23 t clock 24 printfsomat d micro segundos 25 int1e6doublet t0CLOCKSPERSEC 26 t0 clock 27 somatoriaaulan 28 t clock 29 printfsomatoriaaula d micro segundos 30 int1e6doublet t0CLOCKSPERSEC 31 return 0 32 Ao compilarmos e executarmos teremos um resultado próximo de 2 gcc testec o teste teste somat 2 micro segundos somatoriaaula 32 micro segundos Mas veja se fizermos o mesmo para pequenos valores de n por exemplo n 2 gcc testec o teste teste somat 3 micro segundos somatoriaaula 2 micro segundos Ou seja é bom destacar que a análise de complexidade é válida para grandes valores de n 3 3 Escreva uma função para realizar busca sequencial em um vetor de números inteiros e calcule a complexidade da sua função nas seguintes situações melhor caso quando o elemento buscado se encontra na primeira posição do vetor e pior caso quando o elemento buscado não ocorre no vetor RESOLUÇÃO Para começar vamos escrever a função A seguinte função faz o que se pede verificando elemento a elemento do vetor v que tem tam elementos se o valor val se encontra Em caso positivo retorna a posição do mesmo Em caso negativo retorna 1 1 int buscaint val int v int tam 2 forint i0 itam i 3 ifvi val 4 return i 5 return 1 6 O melhor caso como o próprio enunciado indica ocorre quando o elemento procurado está na primeira posição isto porque a função precisa fazer apenas uma comparação para encontrálo saindo da função imediatamente Nesse caso em específico teremos portanto O 1 O pior caso como o próprio enunciado também indica ocorre quando o elemento procurado não está no vetor isto porque a função precisa fazer todas as n comparações e além disso ainda precisa sair do for e retornar o valor resultante Nesse caso em específico teremos portanto O n 4 4 Considerando uma função chamada outraFn de complexidade de tempo Θn² qual será a complexidade de tempo do melhor e do pior caso do código abaixo Calcule cuidadosamente Note que a linha do for foi quebrada em 3 pois cada parte tem uma quantidade de execuções diferente das demais for int i 0 i n i if arri k k e constante outraFn RESOLUÇÃO Para a análise desse código vamos considerar os seguintes tempos Criação de variável tᵥ Atribuição tₐ Comparação t𝚌 Soma tₛ Acesso a elemento de vetor tᵢ Chamada de função t𝚏 Execução da função Θn² tₑn² Retorno de função tᵣ Definidas as constantes vamos analisar o código linha a linha no melhor caso Nesse caso temos que fazer a menor quantidade de operações possível para isso não podemos nunca entrar no if ou seja sua condição deve ser sempre falsa Linha 1 Essa parte do for é a inicialização e é executada apenas uma vez Aqui temos uma criação de variável e uma atribuição T₁ tᵥ tₐ Linha 2 Essa parte do for é executada até que seja falsa Como i vai de 0 a n teremos n1 comparações T₂ n1t𝚌 Linha 3 Essa última parte do for é executada ao final de cada iteração que ocorrer ou seja sempre que a condição da linha anterior for verdadeira essa instrução é executada ao final da iteração e ela consiste de uma soma e uma atribuição T₃ ntₛ tₐ Linha 4 Nessa linha há o acesso ao elemento do vetor e a comparação e é executada para toda iteração do for em que a condição seja verdadeira T₄ ntᵢ t𝚌 Linha 5 Estamos analisando o melhor caso Nessa situação a função nunca é executada pois a condição anterior sempre é falsa de forma que esse tempo é sempre nulo T₅ 0 Somando os tampos anteriores temos Tₘₑₗₕₒᵣ tᵥ tₐ n1t𝚌 ntₛ tₐ ntᵢ t𝚌 0 Rearranjando temos Tₘₑₗₕₒᵣ t𝚌 tₛ tₐ tᵢ t𝚌n tᵥ tₐ t𝚌 Tₘₑₗₕₒᵣ 2t𝚌 tₛ tₐ tᵢ n tᵥ tₐ t𝚌 Para n grande o termo independente de n é desprezível Tₘₑₗₕₒᵣ 2t𝚌 tₛ tₐ tᵢn E para a análise de complexidade desprezamos constantes multiplicativas Tₘₑₗₕₒᵣ On Para o pior caso a condição do if será sempre verdadeira de forma que a função será sempre executada Dessa forma o tempo das 4 primeiras linhas vão se manter e o da quinta mudará de forma que teremos a chamada da função a execução da mesma e seu retorno T₅ nt𝚏 tₑn² tᵣ Refazendo a soma temos Tₚᵢₒᵣ tᵥ tₐ n1t𝚌 ntₛ tₐ ntᵢ t𝚌 nt𝚏 tₑn² tᵣ Rearranjando temos Tₚᵢₒᵣ tₑn³ t𝚌 tₛ tₐ tᵢ t𝚌 t𝚏 tᵣn tᵥ tₐ t𝚌 Tₚᵢₒᵣ tₑn³ 2t𝚌 tₛ tₐ tᵢ t𝚏 tᵣn tᵥ tₐ t𝚌 Para n grande o termo independente de n e o termo linear são desprezíveis Tₚᵢₒᵣ tₑn³ E para a análise de complexidade desprezamos constantes multiplicativas Tₚᵢₒᵣ On³ 5 Considerando uma função chamada outraFn de complexidade de tempo Θ 1 qual será a complexidade de tempo do melhor e do pior caso do código abaixo Calcule cuidadosamente 1 for int i 0 2 i 100 3 i 4 if arri k k e constante 5 outraFn RESOLUÇÃO Perceba que esse exercício é muito semelhante ao anterior mudando somente a complexidade da função e o limite superior do for Dessa forma a resolução será também muito semelhante Para a análise desse código vamos considerar a mesma notação de tempos do exercício anterior Definidas as constantes vamos analisar o código linha a linha no melhor caso Nesse caso temos que fazer a menor quantidade de operações possível para isso não podemos nunca entrar no if ou seja sua condição deve ser sempre falsa Linha 1 Essa parte do for é a inicialização e é executada apenas uma vez Aqui temos uma criação de variável e uma atribuição T1 tv ta Linha 2 Essa parte do for é executada até que seja falsa Como i vai de 0 a 100 teremos 101 comparações T2 101tc Linha 3 Essa última parte do for é executada ao final de cada iteração que ocorrer ou seja sempre que a condição da linha anterior for verdadeira essa instrução é executada ao final da iteração e ela consiste de uma soma e uma atribuição T3 100 ts ta Linha 4 Nessa linha há o acesso ao elemento do vetor e a comparação e é executada para toda iteração do for em que a condição seja verdadeira T4 100 ti tc Linha 5 Estamos analisando o melhor caso Nessa situação a função nunca é executada pois a condição anterior sempre é falsa de forma que esse tempo é sempre nulo T5 0 Somando os tampos anteriores temos Tmelhor tv ta 101tc n ts ta 100 ti tc 0 Rearranjando temos Tmelhor 100 tc ts ta ti tc tv ta tc Tmelhor 201tc 100ts 101ta 100ti tv Como não há nenhuma dependência com n dizemos que a complexidade é constante Tmelhor O 1 Para o pior caso a condição do if será sempre verdadeira de forma que a função será sempre executada Dessa forma o tempo das 4 primeiras linhas vão se manter e o da quinta mudará de forma que teremos a chamada da função a execução da mesma e seu retorno 7 T₅ 100t𝚏 tₑn² tᵣ Refazendo a soma temos Tₚᵢₒᵣ tᵥ tₐ 101t𝚌 ntₛ tₐ 100tᵢ t𝚌 100t𝚏 tₑn² tᵣ Rearranjando temos Tₚᵢₒᵣ 100tₑn² 201t𝚌 100tₛ 101tₐ 100tᵢ 100t𝚏 100tᵣ tᵥ Para n grande o termo independente de n é desprezível Tₚᵢₒᵣ 100tₑn² E para a análise de complexidade desprezamos constantes multiplicativas Tₚᵢₒᵣ On²