Eficiência e Complexidade Computacional: Conceitos e Exemplos

Introdução O que é eficiência Tempo ou esforço empregado para realizar algo Otimização do uso dos recursos Efici ˆencia Tempo Efici ˆencia Recursos C 2022 Bruno Prado Departamento de Computação UFS 2 43 Introdução Qual a história e por que era importante Os recursos computacionais eram muito limitados Grande consumo de potência e uso compartilhado C 2022 Bruno Prado Departamento de Computação UFS 3 43 Introdução Por que hoje é importante Restrições de custo Baixo consumo de potência C 2022 Bruno Prado Departamento de Computação UFS 4 43 Introdução Quais os tipos de eficiência ou de complexidade computacional Tempo Número de passos executados Espaço Tamanho da alocação em memória C 2022 Bruno Prado Departamento de Computação UFS 5 43 Complexidade de tempo Indicador de eficiência de execução do algoritmo Métrica número de passos executados Problema ordenação de sequência com n números E1E2 En1 En para gerar uma sequência ordenada E 1 E 2 E n1 E n E1 E2 En1 En 0 1 n2 n1 E1 E2 En1 En 0 1 n2 n1 Quantos passos são realizados C 2022 Bruno Prado Departamento de Computação UFS 6 43 Complexidade de tempo Indicador de eficiência de execução do algoritmo Métrica número de passos executados Problema ordenação de sequência com n números E1E2 En1 En para gerar uma sequência ordenada E 1 E 2 E n1 E n E1 E2 En1 En 0 1 n2 n1 E1 E2 En1 En 0 1 n2 n1 Quantos passos são realizados C 2022 Bruno Prado Departamento de Computação UFS 7 43 Complexidade de tempo Indicador de eficiência de execução do algoritmo Métrica número de passos executados Problema ordenação de sequência com n números E1E2 En1 En para gerar uma sequência ordenada E 1 E 2 E n1 E n E1 E2 En1 En 0 1 n2 n1 E1 E2 En1 En 0 1 n2 n1 Quantos passos são realizados C 2022 Bruno Prado Departamento de Computação UFS 8 43 Complexidade de tempo Ordenação por seleção 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Procedimento de ordenação por seleção 5 void selectionsort uint32t V uint32t n 6 foruint32t i 0 i n 1 i 7 uint32t min i 8 foruint32t j i 1 j n j 9 ifVj Vmin min j 10 ifi min trocar Vi Vmin 11 12 Numero de passos n 1 n 2 2 1 n 1 1 n 1 2 n2 C 2022 Bruno Prado Departamento de Computação UFS 9 43 Complexidade de tempo Ordenação por seleção 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Procedimento de ordenação por seleção 5 void selectionsort uint32t V uint32t n 6 foruint32t i 0 i n 1 i 7 uint32t min i 8 foruint32t j i 1 j n j 9 ifVj Vmin min j 10 ifi min trocar Vi Vmin 11 12 Numero de passos n 1 n 2 2 1 n 1 1 n 1 2 n2 C 2022 Bruno Prado Departamento de Computação UFS 10 43 Complexidade de tempo Ordenação por inserção 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Procedimento de ordenação por inserção 5 void insertionsort uint32t V uint32t n 6 foruint32t i 1 i n i 7 foruint32t j i j 0 Vj 1 Vj j 8 trocar Vj Vj 1 9 n Numero de passos n2 C 2022 Bruno Prado Departamento de Computação UFS 11 43 Complexidade de tempo Ordenação por inserção 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Procedimento de ordenação por inserção 5 void insertionsort uint32t V uint32t n 6 foruint32t i 1 i n i 7 foruint32t j i j 0 Vj 1 Vj j 8 trocar Vj Vj 1 9 n Numero de passos n2 C 2022 Bruno Prado Departamento de Computação UFS 12 43 Complexidade de tempo Como calcular a quantidade de passos Análise depende somente do tamanho da entrada n Demais trechos do código são constantes 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Procedimento de exemplo 5 void exemplouint32t n 6 c1 7 foruint32t i 0 i n i 8 c2 9 foruint32t j 0 j n j 10 c3 11 foruint32t k 0 k n k 12 c4 13 C 2022 Bruno Prado Departamento de Computação UFS 13 43 Complexidade de tempo Como calcular a quantidade de passos Expressão em função do valor de n Subrotinas c1 c2 c3 e c4 não dependem de n exemplon c1 n c2 n c3 n c4 c1 n c2 n2 c3 n3 c4 C 2022 Bruno Prado Departamento de Computação UFS 14 43 Complexidade de tempo Como obter o tempo consumido Entrada de tamanho 1000 Valores de c1 200 ns c2 150 ns c3 250 ns e c4 100 ns exemplo1000 200 103 150 106 250 ns 109 100 ns 0 0000002 0 00015 0 25 100 109 ns 100 2501502 109 ns 100 s C 2022 Bruno Prado Departamento de Computação UFS 15 43 Complexidade de tempo Como obter o tempo consumido Quanto maior o valor do tamanho da entrada n maior é o domínio do fator de maior grau da função Para um valor de n suficientemente grande n n0 exemplon gn gn c n3 C 2022 Bruno Prado Departamento de Computação UFS 16 43 Complexidade de tempo Análise assintótica Valores das constantes dependem da máquina Com n se analisa a ordem das funções lim n exemplon gn 0 exemplon gn k exemplon gn exemplon gn C 2022 Bruno Prado Departamento de Computação UFS 17 43 Complexidade de espaço Indicador de eficiência de memória do algoritmo Métrica tamanho da alocação em memória Problema ordenação de sequência com n números E1E2 En1 En para gerar uma sequência ordenada E 1 E 2 E n1 E n E1 E2 En1 En 0 1 n2 n1 E1 E2 En1 En 0 1 n2 n1 Quantas posições de memória são utilizadas C 2022 Bruno Prado Departamento de Computação UFS 18 43 Complexidade de espaço Indicador de eficiência de memória do algoritmo Métrica tamanho da alocação em memória Problema ordenação de sequência com n números E1E2 En1 En para gerar uma sequência ordenada E 1 E 2 E n1 E n E1 E2 En1 En 0 1 n2 n1 E1 E2 En1 En 0 1 n2 n1 Quantas posições de memória são utilizadas C 2022 Bruno Prado Departamento de Computação UFS 19 43 Complexidade de espaço Indicador de eficiência de memória do algoritmo Métrica tamanho da alocação em memória Problema ordenação de sequência com n números E1E2 En1 En para gerar uma sequência ordenada E 1 E 2 E n1 E n E1 E2 En1 En 0 1 n2 n1 E1 E2 En1 En 0 1 n2 n1 Quantas posições de memória são utilizadas C 2022 Bruno Prado Departamento de Computação UFS 20 43 Complexidade de espaço Como calcular a memória alocada Expressão em função do valor de entrada n Constantes dependem do tamanho do dado 1 2 Procedimento de ordenação por inserção 3 void insertionsort uint32t V uint32t n 4 foruint32t i 1 i n i 5 foruint32t j i j 0 Vj 1 Vj j 6 trocar Vj Vj 1 7 insertionsortn 2 cuint32t C 2022 Bruno Prado Departamento de Computação UFS 21 43 Complexidade de espaço Como calcular a memória alocada Expressão em função do valor de entrada n Constantes dependem do tamanho do dado 1 2 Procedimento de ordenação por inserção 3 void insertionsort uint32t V uint32t n 4 foruint32t i 1 i n i 5 foruint32t j i j 0 Vj 1 Vj j 6 trocar Vj Vj 1 7 insertionsortn 2 cuint32t C 2022 Bruno Prado Departamento de Computação UFS 22 43 Complexidade de espaço Como calcular a memória alocada Expressão em função do valor de entrada n Constantes dependem do tamanho do dado 1 2 Procedimento de exemplo 3 void exemplouint32t V uint32t n 4 V uint32t mallocn sizeofuint32t 5 foruint32t i 0 i n i 6 Vi rand 7 exemplon n cuint32t cuint32t C 2022 Bruno Prado Departamento de Computação UFS 23 43 Complexidade de espaço Como calcular a memória alocada Expressão em função do valor de entrada n Constantes dependem do tamanho do dado 1 2 Procedimento de exemplo 3 void exemplouint32t V uint32t n 4 V uint32t mallocn sizeofuint32t 5 foruint32t i 0 i n i 6 Vi rand 7 exemplon n cuint32t cuint32t C 2022 Bruno Prado Departamento de Computação UFS 24 43 Complexidade de espaço Como calcular a memória alocada Quanto maior o valor do tamanho da entrada n maior é o domínio do fator de maior grau da função Para um valor de n suficientemente grande n n0 exemplon gn gn c n C 2022 Bruno Prado Departamento de Computação UFS 25 43 Complexidade de espaço Análise assintótica Valores das constantes dependem da máquina Com n se analisa a ordem das funções lim n exemplon gn 0 exemplon gn k exemplon gn exemplon gn C 2022 Bruno Prado Departamento de Computação UFS 26 43 Ordem de crescimento Classes de complexidade para entrada n n log2 n n n log2 n n2 n3 2n n 101 3 3 101 3 3 101 102 103 103 3 6 106 102 6 6 102 6 6 102 104 106 1 3 1030 9 3 10157 103 10 103 1 0 104 106 109 104 13 104 1 3 105 108 1012 105 17 105 1 7 106 1010 1015 106 20 106 2 0 107 1012 1018 C 2022 Bruno Prado Departamento de Computação UFS 27 43 Exemplo Calcular a complexidade de tempo e de espaco do algoritmo fatorial Descrever sua implementacao iterativa Tudo deve ser claramente justificado n0 Fatorialn nx Fatorialn1 n0O C 2022 Bruno Prado Departamento de Computado UFS 2843 Notação O Necessidade de formalização da complexidade dos algoritmos Notação matemática Análise assintótica Notações para melhor caso Ω pior caso O e caso médio Θ Definições e aplicações C 2022 Bruno Prado Departamento de Computação UFS 29 43 Notação O Função de busca sequencial Descrita pela equação buscan cA cB n 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Procedimento de busca 5 int32t buscaint32t elem int32t V uint32t n 6 int32t r 1 7 foruint32t i 0 r 1 i n i 8 ifVi elem 9 r i 10 return r 11 C 2022 Bruno Prado Departamento de Computação UFS 30 43 Melhor caso O que é a análise de melhor caso de um algoritmo Situação com menor número de passos realizados Estabelece um limitante inferior ou melhor caso Busca sequencial pelo elemento 33 Primeira ocorrência Vetor possui 1000 elementos sem repetições 33 15 1 14 0 1 998 999 C 2022 Bruno Prado Departamento de Computação UFS 31 43 Melhor caso O que é a análise de melhor caso de um algoritmo Situação com menor número de passos realizados Estabelece um limitante inferior ou melhor caso Busca sequencial pelo elemento 33 Primeira ocorrência Vetor possui 1000 elementos sem repetições 33 15 1 14 0 1 998 999 C 2022 Bruno Prado Departamento de Computação UFS 32 43 Melhor caso Análise de melhor caso da busca sequencial Existem constantes positivas c e n0 tal que 0 cgn buscan para todo n n0 Aplicando a notação Ωbuscan Ωgn ΩcA cB cMC n0 fnOmegagn cgn fn C 2022 Bruno Prado Departamento de Computação UFS 33 43 Pior caso O que é a análise de pior caso de um algoritmo Descreve a situação com maior número de passos Estabelece um limitante superior Busca sequencial pelo elemento 14 Última ocorrência Vetor possui 1000 elementos sem repetições 33 15 1 14 0 1 998 999 C 2022 Bruno Prado Departamento de Computação UFS 34 43 Pior caso O que é a análise de pior caso de um algoritmo Descreve a situação com maior número de passos Estabelece um limitante superior Busca sequencial pelo elemento 14 Última ocorrência Vetor possui 1000 elementos sem repetições 33 15 1 14 0 1 998 999 C 2022 Bruno Prado Departamento de Computação UFS 35 43 Pior caso Análise de pior caso da busca sequencial Existem constantes positivas c e n0 tal que 0 buscan cgn para todo n n0 Aplicando a notação Obuscan Ocgn OcA cB n cPC n n0 fnOgn cgn fn C 2022 Bruno Prado Departamento de Computação UFS 36 43 Notação O Propriedades da notação O Termos constantes Oc O1 Multiplicação por constantes Oc fn Ofn Adição Of1n Of2n Of1n f2n Produto Of1n Of2n Of1n f2n C 2022 Bruno Prado Departamento de Computação UFS 37 43 Caso médio Não confundir com caso prático ou real Observa o comportamento real do algoritmo Utiliza dados estatísticos Busca sequencial por um elemento qualquer São executadas na busca entre 1 e n iterações Vetor possui 1000 elementos sem repetições 33 15 1 14 0 1 998 999 C 2022 Bruno Prado Departamento de Computação UFS 38 43 Caso médio Não confundir com caso prático ou real Observa o comportamento real do algoritmo Utiliza dados estatísticos Busca sequencial por um elemento qualquer São executadas na busca entre 1 e n iterações Vetor possui 1000 elementos sem repetições 33 15 1 14 0 1 998 999 C 2022 Bruno Prado Departamento de Computação UFS 39 43 Caso médio Análise de caso médio da busca sequencial Existem constantes positivas c e n0 tal que 0 c1gn buscan c2gn para todo n n0 Aplicando a notação ΩcMC buscan On n0 fnThetagn fn 2gn c 1 c gn C 2022 Bruno Prado Departamento de Computação UFS 40 43 Caso médio Ordem exata de execução de um algoritmo fn fn Ωc1gn e fn Oc2gn fn Θgn C 2022 Bruno Prado Departamento de Computação UFS 41 43 Exemplo Calcule a complexidade de tempo e espaço do código abaixo utilizando as 3 notações vistas 1 Padrão de tipos por tamanho 2 include stdinth 3 4 void exemplouint32t n 5 int a intmalloc nn10 sizeofint 6 forint i 0 i 10 i 7 ai 1 8 forint i 0 i n i 9 int b 3 10 forint j 0 j n j 11 aij b aij 12 forint k 0 k 10 k 13 aijaij ak 14 15 16 forint i n i n n i 17 ai ai 2 18 C 2022 Bruno Prado Departamento de Computação UFS 42 43