Tipos de Dados em C: Inteiros e Ponto Flutuante

Introdução Inteiros com sinal em C Dados com 8 16 32 ou 64 bits Tipo Bits Alcance Formato char 8 27 27 1 c hhi short 16 215 215 1 hi int 16 64 263 263 1 i d long 32 64 263 263 1 li long long 64 263 263 1 lli Valores dependentes da plataforma C 2022 Bruno Prado Departamento de Computação UFS 2 59 Introdução Inteiros sem sinal em C Dados com 8 16 32 ou 64 bits Tipo Bits Alcance Formato unsigned char 8 0 28 1 c hhu unsigned short 16 0 216 1 hu unsigned int 16 64 0 264 1 u unsigned long 32 64 0 264 1 lu unsigned long long 64 0 264 1 llu Valores dependentes da plataforma C 2022 Bruno Prado Departamento de Computação UFS 3 59 Introdução Ponto flutuante em C Dados com 32 64 80 96 ou 128 bits Tipo Bits Alcance Formato float 32 12E38 34E38 f double 64 23E308 17E308 lf long double 80 128 34E4932 11E4932 Lf Valores dependentes da plataforma C 2022 Bruno Prado Departamento de Computação UFS 4 59 Introdução Organização dos bytes na memória Little Endian Primeiro byte é o menos significativo 0xAABBCCDD 0 1 2 3 0xDD 0xCC 0xBB 0xAA Big Endian Primeiro byte é o mais significativo 0xAABBCCDD 0 1 2 3 0xAA 0xBB 0xCC 0xDD C 2022 Bruno Prado Departamento de Computação UFS 5 59 Introdução Organização dos bytes na memória Little Endian Primeiro byte é o menos significativo 0xAABBCCDD 0 1 2 3 0xDD 0xCC 0xBB 0xAA Big Endian Primeiro byte é o mais significativo 0xAABBCCDD 0 1 2 3 0xAA 0xBB 0xCC 0xDD C 2022 Bruno Prado Departamento de Computação UFS 6 59 Introdução Segmentos de memória Pilha stack Alocação dinâmica heap Dados não inicializados bss Dados inicializados data Código text Endereço superior Endereço inferior C 2022 Bruno Prado Departamento de Computação UFS 7 59 Introdução Segmentos de memória Pilha Passagem de parâmetros Controle de fluxo de execução Alocação de variáveis locais Gerenciado pelo compilador Heap Dados alocados dinamicamente Controlado pelo programador Dados Variáveis estáticas declaradas pelo programador com valores inicializados ou definidos pela plataforma Código Contém as operações aritméticas e lógicas controles condicionais e iterativos chamadas de funções etc C 2022 Bruno Prado Departamento de Computação UFS 8 59 Introdução Segmentos de memória Pilha Passagem de parâmetros Controle de fluxo de execução Alocação de variáveis locais Gerenciado pelo compilador Heap Dados alocados dinamicamente Controlado pelo programador Dados Variáveis estáticas declaradas pelo programador com valores inicializados ou definidos pela plataforma Código Contém as operações aritméticas e lógicas controles condicionais e iterativos chamadas de funções etc C 2022 Bruno Prado Departamento de Computação UFS 9 59 Introdução Segmentos de memória Pilha Passagem de parâmetros Controle de fluxo de execução Alocação de variáveis locais Gerenciado pelo compilador Heap Dados alocados dinamicamente Controlado pelo programador Dados Variáveis estáticas declaradas pelo programador com valores inicializados ou definidos pela plataforma Código Contém as operações aritméticas e lógicas controles condicionais e iterativos chamadas de funções etc C 2022 Bruno Prado Departamento de Computação UFS 10 59 Introdução Segmentos de memória Pilha Passagem de parâmetros Controle de fluxo de execução Alocação de variáveis locais Gerenciado pelo compilador Heap Dados alocados dinamicamente Controlado pelo programador Dados Variáveis estáticas declaradas pelo programador com valores inicializados ou definidos pela plataforma Código Contém as operações aritméticas e lógicas controles condicionais e iterativos chamadas de funções etc C 2022 Bruno Prado Departamento de Computação UFS 11 59 Introdução Erros na utilização da memória Falha de segmentação segmentation fault Acesso indevido na memória Ex referência para endereço inválido ou nulo Estouro de pilha stack overflow A pilha sobrescreveu dados do heap Ex função recursiva em laço infinito C 2022 Bruno Prado Departamento de Computação UFS 12 59 Introdução Erros na utilização da memória Falha de segmentação segmentation fault Acesso indevido na memória Ex referência para endereço inválido ou nulo Estouro de pilha stack overflow A pilha sobrescreveu dados do heap Ex função recursiva em laço infinito C 2022 Bruno Prado Departamento de Computação UFS 13 59 Ponteiros O que são apontadores ou ponteiros São um tipo de dado utilizado para referenciar o conteúdo de uma determinada região de memória Armazenam o endereço de memória ao invés do valor da variável 1 Padrão de tipos por tamanho 2 include stdinth 3 Função principal 4 int main 5 Inteiro sem sinal x inicializado com 7 6 uint32t x 7 7 Ponteiro px inicializado como nulo 8 uint32t px NULL 9 Ponteiro px recebe endereço da variável x 10 px x 11 Retornando zero 12 return 0 13 C 2022 Bruno Prado Departamento de Computação UFS 14 59 Ponteiros O que são apontadores ou ponteiros São um tipo de dado utilizado para referenciar o conteúdo de uma determinada região de memória Armazenam o endereço de memória ao invés do valor da variável 1 Padrão de tipos por tamanho 2 include stdinth 3 Função principal 4 int main 5 Inteiro sem sinal x inicializado com 7 6 uint32t x 7 7 Ponteiro px inicializado como nulo 8 uint32t px NULL 9 Ponteiro px recebe endereço da variável x 10 px x 11 Retornando zero 12 return 0 13 C 2022 Bruno Prado Departamento de Computação UFS 15 59 Ponteiros O que são apontadores ou ponteiros São um tipo de dado utilizado para referenciar o conteúdo de uma determinada região de memória Armazenam o endereço de memória ao invés do valor da variável 1 Padrão de tipos por tamanho 2 include stdinth 3 Função principal 4 int main 5 Inteiro sem sinal x inicializado com 7 6 uint32t x 7 7 Ponteiro px inicializado como nulo 8 uint32t px NULL 9 Ponteiro px recebe endereço da variável x 10 px x 11 Retornando zero 12 return 0 13 C 2022 Bruno Prado Departamento de Computação UFS 16 59 Ponteiros Conteúdo da memória Endereço Memória Variável 0x80000004 0x80000000 px 0x80000000 0x00000007 x C 2022 Bruno Prado Departamento de Computação UFS 17 59 Ponteiros Referenciando o ponteiro Operador 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Função principal 6 int main 7 8 Ponteiro px recebe endereço da variável x 9 px x 10 Imprimindo informações 11 printfmainxup px px 12 Atualizando valor de x 13 px 3 14 Retornando zero 15 return 0 16 main x 7 0x80000000 C 2022 Bruno Prado Departamento de Computação UFS 18 59 Ponteiros Conteúdo da memória Endereço Memória Variável 0x80000004 0x80000000 px 0x80000000 0x00000003 x C 2022 Bruno Prado Departamento de Computação UFS 19 59 Ponteiros Passagem de parâmetro por valor 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Função f 6 void fuint32t x 7 Imprimindo o parâmetro x 8 printffxu x 9 Modificando o parâmetro x 10 x 1 11 Imprimindo o parâmetro x 12 printffxu x 13 14 Função principal 15 int main 16 17 C 2022 Bruno Prado Departamento de Computação UFS 20 59 Ponteiros Passagem de parâmetro por valor 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Função f 6 void fuint32t x 7 Imprimindo o parâmetro x 8 printffxu x 9 Modificando o parâmetro x 10 x 1 11 Imprimindo o parâmetro x 12 printffxu x 13 14 Função principal 15 int main 16 17 C 2022 Bruno Prado Departamento de Computação UFS 21 59 Ponteiros Passagem de parâmetro por valor 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Função principal 5 int main 6 Inteiro sem sinal x inicializado com 11 7 uint32t x 11 8 Chamando a função f com parâmetro x 9 fx 10 Imprimindo valor de x 11 printfmainxu x 12 Retornando zero 13 return 0 14 f x 11 f x 1 main x 11 C 2022 Bruno Prado Departamento de Computação UFS 22 59 Ponteiros Conteúdo da memória Endereço Memória Variável 0x80000004 0x80000000 px 0x80000000 0x0000000B x C 2022 Bruno Prado Departamento de Computação UFS 23 59 Ponteiros Passagem de parâmetro por referência 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Função f 6 void fuint32t x 7 Imprimindo o conteúdo de x 8 printffxu x 9 Incrementando o conteúdo de x 10 x 11 Imprimindo o parâmetro x 12 printffxu x 13 14 Função principal 15 int main 16 17 C 2022 Bruno Prado Departamento de Computação UFS 24 59 Ponteiros Passagem de parâmetro por referência 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Função f 6 void fuint32t x 7 Imprimindo o conteúdo de x 8 printffxu x 9 Incrementando o conteúdo de x 10 x 11 Imprimindo o parâmetro x 12 printffxu x 13 14 Função principal 15 int main 16 17 C 2022 Bruno Prado Departamento de Computação UFS 25 59 Ponteiros Passagem de parâmetro por referência 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Função principal 5 int main 6 Inteiro sem sinal x inicializado com 7 7 uint32t x 11 8 Chamando a função f com ponteiro de x 9 fx 10 Imprimindo valor de x 11 printfmainxu x 12 Retornando zero 13 return 0 14 f x 11 f x 12 main x 12 C 2022 Bruno Prado Departamento de Computação UFS 26 59 Ponteiros Conteúdo da memória Endereço Memória Variável 0x80000004 0x80000000 px 0x80000000 0x0000000C x C 2022 Bruno Prado Departamento de Computação UFS 27 59 Ponteiros Modificador const Proteger passagem por referência Permissão de somente leitura 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Função f 5 void fconst uint32t x 6 Exibindo o conteúdo de x 7 printffxu x 8 Modificando o conteúdo de x 9 x 1 10 11 C 2022 Bruno Prado Departamento de Computação UFS 28 59 Ponteiros Modificador const Proteger passagem por referência Permissão de somente leitura 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Função f 5 void fconst uint32t x 6 Exibindo o conteúdo de x 7 printffxu x 8 Modificando o conteúdo de x 9 x 1 10 11 maincpp910 error assignment of readonly location x C 2022 Bruno Prado Departamento de Computação UFS 29 59 Ponteiros Ponteiro de ponteiro 1 Biblioteca de ES 2 include stdioh 3 Função principal 4 int mainint argc char argv 5 args argv 6 char args argv 7 pargs args argv 8 char pargs args 9 Imprimindo parâmetros da main 10 printfmain is argc args 0 11 printfmain is argc pargs0 12 Retornando zero 13 return 0 14 main1 mainbin C 2022 Bruno Prado Departamento de Computação UFS 30 59 Ponteiros Ponteiro de ponteiro 1 Biblioteca de ES 2 include stdioh 3 Função principal 4 int mainint argc char argv 5 args argv 6 char args argv 7 pargs args argv 8 char pargs args 9 Imprimindo parâmetros da main 10 printfmain is argc args 0 11 printfmain is argc pargs0 12 Retornando zero 13 return 0 14 main1 mainbin main1 mainbin C 2022 Bruno Prado Departamento de Computação UFS 31 59 Ponteiros Conteúdo da memória Endereço Memória Variável 0xF0000004 mainbin argv 0xF0000000 0x00000001 argc 0x80000000 0xF0000004 args 0x80000004 0x80000000 pargs C 2022 Bruno Prado Departamento de Computação UFS 32 59 Ponteiros Ponteiro de função 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Função fatorial 6 uint64t fatorialuint32t n 7 Resultado 8 uint64t r 1 9 Iterações de 2 n 10 foruint32t i 2 i n i 11 Multiplicação do resultado por i 12 r r i 13 Retorno do resultado 14 return r 15 16 Função principal 17 int main 18 19 C 2022 Bruno Prado Departamento de Computação UFS 33 59 Ponteiros Ponteiro de função 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 6 Função principal 7 int main 8 Ponteiro de função 9 uint64t pfuint32t NULL 10 Atribuição de endereço da função fatorial 11 pf fatorial 12 Imprimindo fatorial de 5 13 printffatorial 5lu pf5 14 Retornando zero 15 return 0 16 fatorial5 120 C 2022 Bruno Prado Departamento de Computação UFS 34 59 Alocação dinâmica Alocação dinâmica x estática Variáveis de tamanho conhecido em tempo de execução Alocada dinamicamente no segmento heap Gerenciado pelo programador Limitado pela memória disponível Variáveis de tamanho fixo previamente conhecido Alocada estaticamente nos segmentos data e bss Controlado pelo compilador Limitado pelo compilador e SO C 2022 Bruno Prado Departamento de Computação UFS 35 59 Alocação dinâmica Medindo o tamanho em bytes das variáveis Operador sizeof 1 Padrão de tipos por tamanho 2 include stdinth 3 Biblioteca de ES 4 include stdioh 5 Estrutura exemplo 6 typedef struct exemplo 7 Nome 8 const char nome 9 Idade 10 uint8t idade 11 exemplo 12 Função principal 13 int main 14 15 C 2022 Bruno Prado Departamento de Computação UFS 36 59 Alocação dinâmica Medindo o tamanho em bytes das variáveis Operador sizeof 1 2 Função principal 3 int main 4 Instanciando exemplo 5 exemplo a EstruturasdeDados 20 6 Imprimindo tamanho de tipos 7 printfsizeofalu sizeofa 8 printfsizeofanomelu sizeofanome 9 printfsizeofaidadelu sizeofaidade 10 Retornando zero 11 return 0 12 sizeofa 16 C 2022 Bruno Prado Departamento de Computação UFS 37 59 Alocação dinâmica Medindo o tamanho em bytes das variáveis Operador sizeof 1 2 Função principal 3 int main 4 Instanciando exemplo 5 exemplo a EstruturasdeDados 20 6 Imprimindo tamanho de tipos 7 printfsizeofalu sizeofa 8 printfsizeofanomelu sizeofanome 9 printfsizeofaidadelu sizeofaidade 10 Retornando zero 11 return 0 12 sizeofa 16 sizeofanome 8 C 2022 Bruno Prado Departamento de Computação UFS 38 59 Alocação dinâmica Medindo o tamanho em bytes das variáveis Operador sizeof 1 2 Função principal 3 int main 4 Instanciando exemplo 5 exemplo a EstruturasdeDados 20 6 Imprimindo tamanho de tipos 7 printfsizeofalu sizeofa 8 printfsizeofanomelu sizeofanome 9 printfsizeofaidadelu sizeofaidade 10 Retornando zero 11 return 0 12 sizeofa 16 sizeofanome 8 sizeofaidade 1 C 2022 Bruno Prado Departamento de Computação UFS 39 59 Alocação dinâmica Alocando memória dinamicamente Função void mallocsizet size 1 2 Função principal 3 int main 4 Ponteiro de inteiros de 32 bits sem sinal 5 uint32t vetor NULL 6 Alocando vetor com 100 elementos 7 vetor uint32t malloc 100 sizeofuint32t 8 Checagem de alocação 9 ifvetor NULL printfFalhanaalocação 10 else printfSucessonaalocação 11 Retornando zero 12 return 0 13 C 2022 Bruno Prado Departamento de Computação UFS 40 59 Alocação dinâmica Alocando memória dinamicamente Função void mallocsizet size 1 2 Função principal 3 int main 4 Ponteiro de inteiros de 32 bits sem sinal 5 uint32t vetor NULL 6 Alocando vetor com 100 elementos 7 vetor uint32t malloc 100 sizeofuint32t 8 Checagem de alocação 9 ifvetor NULL printfFalhanaalocação 10 else printfSucessonaalocação 11 Retornando zero 12 return 0 13 Falha na alocação C 2022 Bruno Prado Departamento de Computação UFS 41 59 Alocação dinâmica Alocando memória dinamicamente Função void mallocsizet size 1 2 Função principal 3 int main 4 Ponteiro de inteiros de 32 bits sem sinal 5 uint32t vetor NULL 6 Alocando vetor com 100 elementos 7 vetor uint32t malloc 100 sizeofuint32t 8 Checagem de alocação 9 ifvetor NULL printfFalhanaalocação 10 else printfSucessonaalocação 11 Retornando zero 12 return 0 13 Sucesso na alocação C 2022 Bruno Prado Departamento de Computação UFS 42 59 Alocação dinâmica Alocando memória dinamicamente Função void mallocsizet size Endereço base de 0x80000000 Tamanho alocado de 100 4 bytes 0 1 98 99 0x80000000 0x80000004 0x80000188 0x8000018C Ponteiro C 2022 Bruno Prado Departamento de Computação UFS 43 59 Alocação dinâmica Alocando e inicializando memória dinamicamente Função void callocsizet num sizet size 1 2 Função principal 3 int main 4 Ponteiro de inteiros de 32 bits sem sinal 5 uint32t vetor NULL 6 Alocando vetor com 100 elementos 7 vetor uint32t calloc 100 sizeofuint32t 8 Checagem de alocação 9 ifvetor NULL printfFalhanaalocação 10 else printfSucessonaalocação 11 Retornando zero 12 return 0 13 C 2022 Bruno Prado Departamento de Computação UFS 44 59 Alocação dinâmica Alocando e inicializando memória dinamicamente Função void callocsizet num sizet size 1 2 Função principal 3 int main 4 Ponteiro de inteiros de 32 bits sem sinal 5 uint32t vetor NULL 6 Alocando vetor com 100 elementos 7 vetor uint32t calloc 100 sizeofuint32t 8 Checagem de alocação 9 ifvetor NULL printfFalhanaalocação 10 else printfSucessonaalocação 11 Retornando zero 12 return 0 13 Falha na alocação C 2022 Bruno Prado Departamento de Computação UFS 45 59 Alocação dinâmica Alocando e inicializando memória dinamicamente Função void callocsizet num sizet size 1 2 Função principal 3 int main 4 Ponteiro de inteiros de 32 bits sem sinal 5 uint32t vetor NULL 6 Alocando vetor com 100 elementos 7 vetor uint32t calloc 100 sizeofuint32t 8 Checagem de alocação 9 ifvetor NULL printfFalhanaalocação 10 else printfSucessonaalocação 11 Retornando zero 12 return 0 13 Sucesso na alocação C 2022 Bruno Prado Departamento de Computação UFS 46 59 Alocação dinâmica Alocando e inicializando memória dinamicamente Função void callocsizet num sizet size Endereço base de 0x80000000 Tamanho alocado de 100 4 bytes 0 0 0 0 0 1 98 99 0x80000000 0x80000004 0x80000188 0x8000018C Ponteiro C 2022 Bruno Prado Departamento de Computação UFS 47 59 Alocação dinâmica Realocando memória dinamicamente Função void reallocvoid ptr sizet size 1 2 Ponteiro de realocação 3 uint32t r NULL 4 Realocando vetor com 1000 elementos 5 r uint32t reallocvetor 1000 sizeofuint32t 6 Checagem de alocação 7 ifr NULL printfFalhanarealocação 8 else 9 printfSucessonarealocação 10 Atualizando ponteiro 11 vetor r 12 13 Retornando zero 14 return 0 15 C 2022 Bruno Prado Departamento de Computação UFS 48 59 Alocação dinâmica Realocando memória dinamicamente Função void reallocvoid ptr sizet size 1 2 Ponteiro de realocação 3 uint32t r NULL 4 Realocando vetor com 1000 elementos 5 r uint32t reallocvetor 1000 sizeofuint32t 6 Checagem de alocação 7 ifr NULL printfFalhanarealocação 8 else 9 printfSucessonarealocação 10 Atualizando ponteiro 11 vetor r 12 13 Retornando zero 14 return 0 15 Falha na realocação C 2022 Bruno Prado Departamento de Computação UFS 49 59 Alocação dinâmica Realocando memória dinamicamente Função void reallocvoid ptr sizet size 1 2 Ponteiro de realocação 3 uint32t r NULL 4 Realocando vetor com 1000 elementos 5 r uint32t reallocvetor 1000 sizeofuint32t 6 Checagem de alocação 7 ifr NULL printfFalhanarealocação 8 else 9 printfSucessonarealocação 10 Atualizando ponteiro 11 vetor r 12 13 Retornando zero 14 return 0 15 Sucesso na realocação C 2022 Bruno Prado Departamento de Computação UFS 50 59 Alocação dinâmica Realocando memória dinamicamente Função void reallocvoid ptr sizet size 1 2 Ponteiro de realocação 3 uint32t r NULL 4 Realocando vetor com 1000 elementos 5 r uint32t reallocvetor 1000 sizeofuint32t 6 Checagem de alocação 7 ifr NULL printfFalhanarealocação 8 else 9 printfSucessonarealocação 10 Atualizando ponteiro 11 vetor r 12 13 Retornando zero 14 return 0 15 Sucesso na realocação C 2022 Bruno Prado Departamento de Computação UFS 51 59 Alocação dinâmica Realocando memória dinamicamente Função void reallocvoid ptr sizet size Endereço base de 0x80000000 Tamanho alocado de 100 4 bytes 1 2 99 100 0 1 98 99 0x80000000 0x80000004 0x80000188 0x8000018C Ponteiro C 2022 Bruno Prado Departamento de Computação UFS 52 59 Alocação dinâmica Realocando memória dinamicamente Função void reallocvoid ptr sizet size Endereço base 0x80008000 Tamanho realocado de 1000 4 bytes 1 100 0 99 998 999 0x80008000 0x8000818C 0x80008F98 0x80008F9C Ponteiro C 2022 Bruno Prado Departamento de Computação UFS 53 59 Alocação dinâmica Liberando memória alocada Função void freevoid ptr 1 2 Biblioteca padrão 3 include stdlibh 4 5 Função principal 6 int main 7 8 Liberando memória alocada 9 freevetor 10 Invalidando ponteiro 11 vetor NULL 12 Retornando zero 13 return 0 14 C 2022 Bruno Prado Departamento de Computação UFS 54 59 Alocação dinâmica Liberando memória alocada Função void freevoid ptr 1 2 Biblioteca padrão 3 include stdlibh 4 5 Função principal 6 int main 7 8 Liberando memória alocada 9 freevetor 10 Invalidando ponteiro 11 vetor NULL 12 Retornando zero 13 return 0 14 C 2022 Bruno Prado Departamento de Computação UFS 55 59 Alocação dinâmica Erros comuns de programação Ponteiros não inicializados ou não invalidados Segmentation Fault Região de memória sem nenhum ponteiro Memory Leak Falta de controle nos limites de memória Buffer Overflow C 2022 Bruno Prado Departamento de Computação UFS 56 59 Alocação dinâmica Erros comuns de programação Ponteiros não inicializados ou não invalidados Segmentation Fault Região de memória sem nenhum ponteiro Memory Leak Falta de controle nos limites de memória Buffer Overflow C 2022 Bruno Prado Departamento de Computação UFS 57 59 Alocação dinâmica Erros comuns de programação Ponteiros não inicializados ou não invalidados Segmentation Fault Região de memória sem nenhum ponteiro Memory Leak Falta de controle nos limites de memória Buffer Overflow C 2022 Bruno Prado Departamento de Computação UFS 58 59 Introdução O que é uma fila É uma estrutura de dados FirstIn FirstOut FIFO Duas operações principais enfileirar e desenfileirar A restrição imposta é que o primeiro elemento inserido é o primeiro a ser removido C 2022 Bruno Prado Departamento de Computação UFS 2 86 Introdução Fila de pessoas Enfileirar pushback P1 P1 P2 C 2022 Bruno Prado Departamento de Computação UFS 3 86 Introdução Fila de pessoas Enfileirar pushback P1 P2 P1 P2 P3 C 2022 Bruno Prado Departamento de Computação UFS 4 86 Introdução Fila de pessoas Enfileirar pushback P1 P2 P3 P1 P2 P3 P4 C 2022 Bruno Prado Departamento de Computação UFS 5 86 Introdução Fila de pessoas Enfileirar pushback P1 P2 P3 P4 P1 P2 P3 P4 C 2022 Bruno Prado Departamento de Computação UFS 6 86 Introdução Fila de pessoas Desenfileirando popfront P1 P2 P3 P4 P2 P3 P4 P1 C 2022 Bruno Prado Departamento de Computação UFS 7 86 Introdução Fila de pessoas Desenfileirando popfront P2 P3 P4 P3 P4 P2 C 2022 Bruno Prado Departamento de Computação UFS 8 86 Introdução Fila de pessoas Desenfileirando popfront P3 P4 P4 P3 C 2022 Bruno Prado Departamento de Computação UFS 9 86 Introdução Fila de pessoas Desenfileirando popfront P4 P4 C 2022 Bruno Prado Departamento de Computação UFS 10 86 Introdução O que é uma pilha É uma estrutura de dados LastIn FirstOut LIFO Duas operações principais empilhar e desempilhar A restrição imposta é que o último elemento inserido é o primeiro a ser removido C 2022 Bruno Prado Departamento de Computação UFS 11 86 Introdução Pilha de livros Empilhando push L1 L1 C 2022 Bruno Prado Departamento de Computação UFS 12 86 Introdução Pilha de livros Empilhando push L1 L2 L2 L1 C 2022 Bruno Prado Departamento de Computação UFS 13 86 Introdução Pilha de livros Empilhando push L2 L1 L3 L3 L2 L1 C 2022 Bruno Prado Departamento de Computação UFS 14 86 Introdução Pilha de livros Empilhando push L3 L2 L1 L4 L4 L3 L2 L1 C 2022 Bruno Prado Departamento de Computação UFS 15 86 Introdução Pilha de livros Desempilhando pop L4 L3 L2 L1 L3 L2 L1 L4 C 2022 Bruno Prado Departamento de Computação UFS 16 86 Introdução Pilha de livros Desempilhando pop L3 L2 L1 L2 L1 L3 C 2022 Bruno Prado Departamento de Computação UFS 17 86 Introdução Pilha de livros Desempilhando pop L2 L1 L1 L2 C 2022 Bruno Prado Departamento de Computação UFS 18 86 Introdução Pilha de livros Desempilhando pop L1 L1 C 2022 Bruno Prado Departamento de Computação UFS 19 86 Fila Técnicas de implementação Vetor Estrutura de lista Funções auxiliares Verificar se está vazia empty Verificar a quantidade de elementos na fila size Acessar o elemento inicial da fila front Acessar o elemento final da fila back C 2022 Bruno Prado Departamento de Computação UFS 20 86 Fila Técnicas de implementação Vetor Estrutura de lista Funções auxiliares Verificar se está vazia empty Verificar a quantidade de elementos na fila size Acessar o elemento inicial da fila front Acessar o elemento final da fila back C 2022 Bruno Prado Departamento de Computação UFS 21 86 Fila Implementação em C Definição da estrutura com vetor 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de fila 5 typedef struct fila 6 Capacidade alocada do vetor 7 sizet capacidade 8 Índice de inicio do vetor I 9 sizet inicio 10 Índice de fim do vetor F 11 sizet fim 12 Tamanho da fila 13 sizet tamanho 14 Vetor sem sinal de 32 bits 15 uint32t vetor 16 fila C 2022 Bruno Prado Departamento de Computação UFS 22 86 Fila Implementação com vetor Inicialização da estrutura É feita a alocação do vetor com capacidade 4 e com índice de início e de tamanho com valor 0 indicando que não possui nenhum elemento 0 1 2 3 IF Capacidade 4 Início 0 Fim 0 Tamanho 0 C 2022 Bruno Prado Departamento de Computação UFS 23 86 Fila Implementação com vetor Enfileirando os elementos É feito o incremento do tamanho da fila e a posição Inicio Fim mod Capacidade recebe o valor do elemento E1 E1 0 1 2 3 IF Capacidade 4 Início 0 Fim 0 Tamanho 0 C 2022 Bruno Prado Departamento de Computação UFS 24 86 Fila Implementação com vetor Enfileirando os elementos É feito o incremento do tamanho da fila e a posição Inicio Fim mod Capacidade recebe o valor do elemento E2 E1 E2 0 1 2 3 I F Capacidade 4 Início 0 Fim 1 Tamanho 1 C 2022 Bruno Prado Departamento de Computação UFS 25 86 Fila Implementação com vetor Enfileirando os elementos É feito o incremento do tamanho da fila e a posição Inicio Fim mod Capacidade recebe o valor do elemento E3 E1 E2 E3 0 1 2 3 I F Capacidade 4 Início 0 Fim 2 Tamanho 2 C 2022 Bruno Prado Departamento de Computação UFS 26 86 Fila Implementação com vetor Enfileirando os elementos É feito o incremento do tamanho da fila e a posição Inicio Fim mod Capacidade recebe o valor do elemento E4 E1 E2 E3 E4 0 1 2 3 I F Capacidade 4 Início 0 Fim 3 Tamanho 3 C 2022 Bruno Prado Departamento de Computação UFS 27 86 Fila Implementação com vetor Todas as posições do vetor estão ocupadas condição que pode ser verificada através da comparação da capacidade e do tamanho E1 E2 E3 E4 0 1 2 3 IF Capacidade 4 Início 0 Fim 0 Tamanho 4 C 2022 Bruno Prado Departamento de Computação UFS 28 86 Fila Implementação com vetor Desenfileirando os elementos O elemento E1 do início da fila é removido com o incremento do Inicio 1 mod Capacidade E2 E3 E4 E1 0 1 2 3 I F Capacidade 4 Início 1 Fim 0 Tamanho 3 C 2022 Bruno Prado Departamento de Computação UFS 29 86 Fila Implementação com vetor Desenfileirando os elementos O elemento E2 do início da fila é removido com o incremento do Inicio 1 mod Capacidade E3 E4 E2 0 1 2 3 I F Capacidade 4 Início 2 Fim 0 Tamanho 2 C 2022 Bruno Prado Departamento de Computação UFS 30 86 Fila Implementação com vetor Desenfileirando os elementos O elemento E3 do início da fila é removido com o incremento do Inicio 1 mod Capacidade E4 E3 0 1 2 3 I F Capacidade 4 Início 3 Fim 0 Tamanho 1 C 2022 Bruno Prado Departamento de Computação UFS 31 86 Fila Implementação com vetor Desenfileirando os elementos Todos os elementos foram removidos a fila está vazia com índices de início e de tamanho com valor 0 E4 0 1 2 3 IF Capacidade 4 Início 0 Fim 0 Tamanho 0 C 2022 Bruno Prado Departamento de Computação UFS 32 86 Fila Implementação em C Definição da estrutura com lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de elemento 5 typedef struct elemento 6 Ponteiro para próximo elemento 7 elemento P 8 Valor do elemento 9 uint32t valor 10 elemento C 2022 Bruno Prado Departamento de Computação UFS 33 86 Fila Implementação em C Definição da estrutura com lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de fila 5 typedef struct fila 6 Ponteiro inicial 7 elemento I 8 Ponteiro final 9 elemento F 10 fila C 2022 Bruno Prado Departamento de Computação UFS 34 86 Fila Implementação com lista encadeada Inicialização da estrutura A fila está vazia com referências nulas para elementos inicial e final NULL IF C 2022 Bruno Prado Departamento de Computação UFS 35 86 Fila Implementação com lista encadeada Enfileirando os elementos É feita a alocação do elemento E1 e a sua inserção na fila ajustando os ponteiros inicial e final E1 P1 NULL IF C 2022 Bruno Prado Departamento de Computação UFS 36 86 Fila Implementação com lista encadeada Enfileirando os elementos É feita a alocação do elemento E2 e utilizando a referência do final da fila é realizada a sua inserção E1 P1 E2 P2 NULL I F C 2022 Bruno Prado Departamento de Computação UFS 37 86 Fila Implementação com lista encadeada Enfileirando os elementos É feita a alocação do elemento E3 e utilizando a referência do final da fila é realizada a sua inserção E1 P1 E2 P2 E3 P3 NULL I F C 2022 Bruno Prado Departamento de Computação UFS 38 86 Fila Implementação com lista encadeada Enfileirando os elementos É feita a alocação do elemento E4 e utilizando a referência do final da fila é realizada a sua inserção E1 P1 E2 P2 E3 P3 E4 P4 NULL I F C 2022 Bruno Prado Departamento de Computação UFS 39 86 Fila Implementação com lista encadeada Desenfileirando os elementos O elemento E1 referenciado pelo ponteiro inicial é removido da fila e o próximo elemento da sequência E2 passa a ser o inicial E2 P2 E3 P3 E4 P4 NULL I F E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 40 86 Fila Implementação com lista encadeada Desenfileirando os elementos O elemento E2 referenciado pelo ponteiro inicial é removido da fila e o próximo elemento da sequência E3 passa a ser o inicial E3 P3 E4 P4 NULL I F E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 41 86 Fila Implementação com lista encadeada Desenfileirando os elementos O elemento E3 referenciado pelo ponteiro inicial é removido da fila e o próximo elemento da sequência E4 passa a ser o inicial E4 P4 NULL IF E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 42 86 Fila Implementação com lista encadeada Desenfileirando os elementos O elemento E4 referenciado pelo ponteiro inicial é removido da fila e por não ter mais nenhum elemento armazenado ambas as referências são anuladas NULL IF E4 P4 C 2022 Bruno Prado Departamento de Computação UFS 43 86 Fila Análise de complexidade Enfileirar Θ1 Desenfileirar Θ1 C 2022 Bruno Prado Departamento de Computação UFS 44 86 Aplicações Escalonamento de processos Navegador Editor de texto Terminal Compilador Início da fila Processo em execução Tamanho da fila Quantidade de processos C 2022 Bruno Prado Departamento de Computação UFS 45 86 Aplicações Troca de informações entre processos ou sistemas Rede TCPIP Sistema A Rede TCPIP Sistema B Interface de comunicação pipe Processo X Pipe Processo Y C 2022 Bruno Prado Departamento de Computação UFS 46 86 Aplicações Troca de informações entre processos ou sistemas Rede TCPIP Sistema A Rede TCPIP Sistema B Interface de comunicação pipe Processo X Pipe Processo Y C 2022 Bruno Prado Departamento de Computação UFS 47 86 Pilha Técnicas de implementação Vetor Estrutura de lista Funções auxiliares Verificar se está vazia empty Verificar a quantidade de elementos na pilha size Acessar o elemento do topo da pilha top C 2022 Bruno Prado Departamento de Computação UFS 48 86 Pilha Técnicas de implementação Vetor Estrutura de lista Funções auxiliares Verificar se está vazia empty Verificar a quantidade de elementos na pilha size Acessar o elemento do topo da pilha top C 2022 Bruno Prado Departamento de Computação UFS 49 86 Pilha Implementação em C Definição da estrutura com vetor 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de pilha 5 typedef struct pilha 6 Capacidade alocada do vetor 7 sizet capacidade 8 Topo da pilha 9 sizet topo 10 Vetor sem sinal de 32 bits 11 uint32t vetor 12 pilha C 2022 Bruno Prado Departamento de Computação UFS 50 86 Pilha Implementação com vetor Inicialização da estrutura É feita a alocação do vetor com capacidade 4 e com índice de topo negativo indicando que não possui nenhum elemento 0 1 2 3 Capacidade 4 Topo 1 C 2022 Bruno Prado Departamento de Computação UFS 51 86 Pilha Implementação com vetor Empilhando os elementos É feito o incremento do topo da pilha e a posição recebe o valor do elemento E1 E1 0 1 2 3 Capacidade 4 Topo 1 C 2022 Bruno Prado Departamento de Computação UFS 52 86 Pilha Implementação com vetor Empilhando os elementos É feito o incremento do topo da pilha e a posição recebe o valor do elemento E2 E1 E2 0 1 2 3 Capacidade 4 Topo 0 C 2022 Bruno Prado Departamento de Computação UFS 53 86 Pilha Implementação com vetor Empilhando os elementos É feito o incremento do topo da pilha e a posição recebe o valor do elemento E3 E2 E1 E3 0 1 2 3 Capacidade 4 Topo 1 C 2022 Bruno Prado Departamento de Computação UFS 54 86 Pilha Implementação com vetor Empilhando os elementos É feito o incremento do topo da pilha e a posição recebe o valor do elemento E4 E3 E2 E1 E4 0 1 2 3 Capacidade 4 Topo 2 C 2022 Bruno Prado Departamento de Computação UFS 55 86 Pilha Implementação com vetor Todas as posições do vetor estão ocupadas caso seja feita uma operação de empilhamento é preciso realizar a realocação do vetor e atualizar sua capacidade E4 E3 E2 E1 0 1 2 3 Capacidade 4 Topo 3 C 2022 Bruno Prado Departamento de Computação UFS 56 86 Pilha Implementação com vetor Desempilhando os elementos O elemento E4 é removido da pilha e o valor do topo é decrementado E3 E2 E1 E4 0 1 2 3 Capacidade 4 Topo 2 C 2022 Bruno Prado Departamento de Computação UFS 57 86 Pilha Implementação com vetor Desempilhando os elementos O elemento E3 é removido da pilha e o valor do topo é decrementado E2 E1 E3 0 1 2 3 Capacidade 4 Topo 1 C 2022 Bruno Prado Departamento de Computação UFS 58 86 Pilha Implementação com vetor Desempilhando os elementos O elemento E2 é removido da pilha e o valor do topo é decrementado E1 E2 0 1 2 3 Capacidade 4 Topo 0 C 2022 Bruno Prado Departamento de Computação UFS 59 86 Pilha Implementação com vetor Desempilhando os elementos O elemento E1 é removido da pilha e o valor do topo é decrementado E1 0 1 2 3 Capacidade 4 Topo 1 C 2022 Bruno Prado Departamento de Computação UFS 60 86 Pilha Implementação com vetor O índice de topo negativo indica que a pilha não possui nenhum elemento armazenado 0 1 2 3 Capacidade 4 Topo 1 C 2022 Bruno Prado Departamento de Computação UFS 61 86 Pilha Implementação em C Definição da estrutura com lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de elemento 5 typedef struct elemento 6 Ponteiro para próximo elemento 7 elemento P 8 Valor do elemento 9 uint32t valor 10 elemento C 2022 Bruno Prado Departamento de Computação UFS 62 86 Pilha Implementação em C Definição da estrutura com lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de pilha 5 typedef struct pilha 6 Ponteiro para topo da pilha 7 elemento T 8 pilha C 2022 Bruno Prado Departamento de Computação UFS 63 86 Pilha Implementação com lista encadeada Inicialização da estrutura A pilha está vazia com o topo da pilha com referência nula NULL T C 2022 Bruno Prado Departamento de Computação UFS 64 86 Pilha Implementação com lista encadeada Empilhando os elementos O elemento E1 é empilhado e o topo da pilha é ajustado com novo endereço E1 P1 NULL T C 2022 Bruno Prado Departamento de Computação UFS 65 86 Pilha Implementação com lista encadeada Empilhando os elementos O elemento E2 é empilhado e o topo da pilha é ajustado com novo endereço E2 P2 E1 P1 NULL T C 2022 Bruno Prado Departamento de Computação UFS 66 86 Pilha Implementação com lista encadeada Empilhando os elementos O elemento E3 é empilhado e o topo da pilha é ajustado com novo endereço E3 P3 E2 P2 E1 P1 NULL T C 2022 Bruno Prado Departamento de Computação UFS 67 86 Pilha Implementação com lista encadeada Empilhando os elementos O elemento E4 é empilhado e o topo da pilha é ajustado com novo endereço E4 P4 E3 P3 E2 P2 E1 P1 NULL T C 2022 Bruno Prado Departamento de Computação UFS 68 86 Pilha Implementação com lista encadeada Desempilhando os elementos O elemento E4 é desempilhado e o topo da pilha é ajustado com novo endereço E3 P3 E2 P2 E1 P1 NULL T E4 P4 C 2022 Bruno Prado Departamento de Computação UFS 69 86 Pilha Implementação com lista encadeada Desempilhando os elementos O elemento E3 é desempilhado e o topo da pilha é ajustado com novo endereço E2 P2 E1 P1 NULL T E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 70 86 Pilha Implementação com lista encadeada Desempilhando os elementos O elemento E2 é desempilhado e o topo da pilha é ajustado com novo endereço E1 P1 NULL T E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 71 86 Pilha Implementação com lista encadeada Desempilhando os elementos A pilha está vazia com o topo da pilha com referência nula NULL T E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 72 86 Pilha Análise de complexidade Empilhar Θ1 Desempilhar Θ1 C 2022 Bruno Prado Departamento de Computação UFS 73 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 74 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 75 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 3 fatorial2 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 76 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 2 fatorial1 3 fatorial2 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 77 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 1 fatorial0 2 fatorial1 3 fatorial2 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 78 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 1 1 1 2 fatorial1 3 fatorial2 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 79 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 2 1 2 3 fatorial2 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 80 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 3 2 6 4 fatorial3 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 81 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n 4 6 24 fatorial4 Topo C 2022 Bruno Prado Departamento de Computação UFS 82 86 Aplicações Suporte a recursão Função recursiva uint64t fatorialuint32t n fatorial4 24 Topo C 2022 Bruno Prado Departamento de Computação UFS 83 86 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 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 Introdução Estrutura de lista São sequências de elementos Ei Utiliza ponteiros Pi para referenciar o próximo elemento da sequência E1 P1 E2 P2 En1 Pn1 En Pn NULL C 2022 Bruno Prado Departamento de Computação UFS 2 51 Introdução Lista encadeada Armazenamento descontínuo em memória Tempo de acesso sequencial E1 P1 E2 P2 En1 Pn1 En Pn NULL Vetor Armazenamento contínuo em memória Tempo de acesso constante E1 E2 En1 En 0 1 n2 n1 C 2022 Bruno Prado Departamento de Computação UFS 3 51 Introdução Lista encadeada Armazenamento descontínuo em memória Tempo de acesso sequencial E1 P1 E2 P2 En1 Pn1 En Pn NULL Vetor Armazenamento contínuo em memória Tempo de acesso constante E1 E2 En1 En 0 1 n2 n1 C 2022 Bruno Prado Departamento de Computação UFS 4 51 Introdução Operações principais Busca Inserção Remoção Modificação C 2022 Bruno Prado Departamento de Computação UFS 5 51 Lista encadeada Coleção de elementos Cabeça primeiro elemento da lista Cauda último elemento da lista E1 P1 E2 P2 En1 Pn1 En Pn NULL Cabeça Cauda Cada elemento possui somente um ponteiro unidirecional para o próximo elemento da sequência C 2022 Bruno Prado Departamento de Computação UFS 6 51 Lista encadeada Coleção de elementos Cabeça primeiro elemento da lista Cauda último elemento da lista E1 P1 E2 P2 En1 Pn1 En Pn NULL Cabeça Cauda Cada elemento possui somente um ponteiro unidirecional para o próximo elemento da sequência C 2022 Bruno Prado Departamento de Computação UFS 7 51 Lista encadeada Implementação em C Definição do elemento 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de elemento 5 typedef struct elemento 6 Valor 7 uint32t E 8 Ponteiro 9 elemento P 10 elemento C 2022 Bruno Prado Departamento de Computação UFS 8 51 Lista encadeada Implementação em C Definição da lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de lista 5 typedef struct lista 6 Ponteiro 7 elemento L 8 lista C 2022 Bruno Prado Departamento de Computação UFS 9 51 Lista encadeada Inserção A cabeça da lista é acessada É feita a busca do ponteiro para o próximo elemento até que uma referência nula seja encontrada NULL C 2022 Bruno Prado Departamento de Computação UFS 10 51 Lista encadeada Inserção É feita a alocação dinâmica do elemento O ponteiro é atualizado para referenciar o novo elemento inserido na lista E1 P1 NULL C 2022 Bruno Prado Departamento de Computação UFS 11 51 Lista encadeada Inserção A cabeça da lista é acessada É feita a busca do ponteiro para o próximo elemento até que uma referência nula seja encontrada E1 P1 E2 P2 NULL C 2022 Bruno Prado Departamento de Computação UFS 12 51 Lista encadeada Inserção É feita a alocação dinâmica do elemento O ponteiro é atualizado para referenciar o novo elemento inserido na lista E1 P1 E2 P2 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 13 51 Lista encadeada Análise de complexidade Busca Ω1 e On Inserção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 14 51 Lista encadeada Remoção É feita a busca pelo valor do elemento E2 O ponteiro P1 é preparado para remoção E1 P1 E2 P2 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 15 51 Lista encadeada Remoção É removido da sequência o elemento E2 O ponteiro P1 é atualizado para referenciar o elemento E3 que é o sucessor do elemento removido E1 P1 E3 P3 NULL E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 16 51 Lista encadeada Análise de complexidade Busca Ω1 e On Remoção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 17 51 Lista encadeada Modificação É feita a busca pelo valor do elemento E3 O valor do ponteiro P1 é armazenado E1 P1 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 18 51 Lista encadeada Modificação A estrutura do elemento E3 é acessado através de sua referência e o seu valor é atualizado E1 P1 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 19 51 Lista encadeada Análise de complexidade Busca Ω1 e On Modificação Θ1 C 2022 Bruno Prado Departamento de Computação UFS 20 51 Lista circular É uma lista encadeada cíclica As operações são equivalentes as realizadas nas listas encadeadas mantendo o ponteiro do último elemento apontando para o primeiro E1 P1 E2 P2 En1 Pn1 En Pn C 2022 Bruno Prado Departamento de Computação UFS 21 51 Lista circular Inserção Como não existem elementos em uma lista vazia não existe a referência circular NULL C 2022 Bruno Prado Departamento de Computação UFS 22 51 Lista circular Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 23 51 Lista circular Inserção É feita a alocação dinâmica do elemento O novo elemento é apontado e faz referência ao primeiro elemento da lista E1 P1 E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 24 51 Lista circular Inserção É feita a alocação dinâmica do elemento O novo elemento é apontado e faz referência ao primeiro elemento da lista E1 P1 E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 25 51 Lista circular Análise de complexidade Busca Ω1 e On Inserção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 26 51 Lista circular Remoção É feita a busca pelo valor do elemento E1 O ponteiro da lista é preparado para remoção E1 P1 E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 27 51 Lista circular Remoção É removido da sequência o elemento E1 O ponteiro da lista é atualizado para referenciar o elemento E2 e assim como o último elemento E3 E2 P2 E3 P3 E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 28 51 Lista circular Análise de complexidade Busca Ω1 e On Remoção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 29 51 Lista circular Modificação É feita a busca pelo valor do elemento E3 O valor do ponteiro P2 é armazenado E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 30 51 Lista circular Modificação A estrutura do elemento E3 é acessado através de sua referência e o seu valor é atualizado E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 31 51 Lista circular Análise de complexidade Busca Ω1 e On Modificação Θ1 C 2022 Bruno Prado Departamento de Computação UFS 32 51 Lista duplamente encadeada Lista encadeada com dois ponteiros Ponteiros do elemento referenciam o elemento anterior e próximo da sequência Navegação em ambas direções A1 E1 P1 A2 E2 P2 An1 En1 Pn1 An En Pn C 2022 Bruno Prado Departamento de Computação UFS 33 51 Lista duplamente encadeada Implementação em C Definição do elemento 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de elemento 5 typedef struct elemento 6 Valor 7 uint32t E 8 Ponteiro para anterior 9 elemento A 10 Ponteiro para próximo 11 elemento P 12 elemento C 2022 Bruno Prado Departamento de Computação UFS 34 51 Lista duplamente encadeada Implementação em C Definição da lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de lista 5 typedef struct lista 6 Ponteiro 7 elemento L 8 lista C 2022 Bruno Prado Departamento de Computação UFS 35 51 Lista duplamente encadeada Inserção A cabeça da lista é acessada É feita a busca do ponteiro para o próximo elemento até que uma referência nula seja encontrada NULL C 2022 Bruno Prado Departamento de Computação UFS 36 51 Lista duplamente encadeada Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista A1 E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 37 51 Lista duplamente encadeada Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista A1 E1 P1 A2 E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 38 51 Lista duplamente encadeada Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista A1 E1 P1 A2 E2 P2 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 39 51 Lista duplamente encadeada Análise de complexidade Busca Ω1 e On Inserção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 40 51 Lista duplamente encadeada Remoção É feita a busca pelo valor do elemento E2 Os ponteiros P1 e A3 são preparados para remoção A1 E1 P1 A2 E2 P2 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 41 51 Lista duplamente encadeada Remoção O elemento E2 é removido da sequência Os ponteiros P1 e A3 são atualizados A1 E1 P1 A2 E2 P2 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 42 51 Lista duplamente encadeada Análise de complexidade Busca Ω1 e On Remoção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 43 51 Lista duplamente encadeada Modificação É feita a busca pelo valor do elemento E3 O valor do ponteiro A1 ou P1 é armazenado A1 E1 P1 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 44 51 Lista duplamente encadeada Modificação A estrutura do elemento E3 é acessado através de sua referência e o seu valor é atualizado A1 E1 P1 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 45 51 Lista duplamente encadeada Análise de complexidade Busca Ω1 e On Modificação Θ1 C 2022 Bruno Prado Departamento de Computação UFS 46 51 Aplicações Aplicações Introdução Implementação iterativa do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial iterativo 4 uint64t fatorialuint32t n 5 uint64t r 1 6 foruint32t i 2 i n i 7 r r i 8 return r 9 fatorialn c1 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 2 42 Introdução Implementação iterativa do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial iterativo 4 uint64t fatorialuint32t n 5 uint64t r 1 6 foruint32t i 2 i n i 7 r r i 8 return r 9 fatorialn c1 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 3 42 Introdução Implementação recursiva do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial recursivo 4 uint64t fatorialuint32t n 5 ifn 0 6 return 1 7 else 8 return n fatorialn 1 9 fatorialn C 2022 Bruno Prado Departamento de Computação UFS 4 42 Introdução Implementação recursiva do algoritmo de fatorial Complexidade de tempo 1 Padrão de tipos por tamanho 2 include stdinth 3 Fatorial recursivo 4 uint64t fatorialuint32t n 5 ifn 0 6 return 1 7 else 8 return n fatorialn 1 9 fatorialn C 2022 Bruno Prado Departamento de Computação UFS 5 42 Relações de recorrência O que é uma relação recorrente É uma função recursiva que define uma sequência O que é uma função recursiva É uma função descrita em seus próprios termos Composta por duas partes Caso base Recorrência C 2022 Bruno Prado Departamento de Computação UFS 6 42 Relações de recorrência O que é uma relação recorrente É uma função recursiva que define uma sequência O que é uma função recursiva É uma função descrita em seus próprios termos Composta por duas partes Caso base Recorrência C 2022 Bruno Prado Departamento de Computação UFS 7 42 Relacoes de recorrencia Implementacao recursiva do algoritmo de fatorial Caso base n 0 Padrao de tipos por tamanho include stdinth Fatorial recursivo uint64t fatorialuint32t n ifn 0 return 1 else return n fatorialn 1 fatorialn 1 n 0 fatorialn 1 1 n 0 Relacoes de recorrencia Implementacao recursiva do algoritmo de fatorial Recorrencia n 0 Padrao de tipos por tamanho include stdinth Fatorial recursivo uint64t fatorialuint32t n ifn 0 return 1 else return n fatorialn 1 fatorialn 1 n 0 fatorialn 1 1 n 0 Relações de recorrência Como resolver estas relações de recorrência Método de substituição Método de árvore de recursão Método mestre C 2022 Bruno Prado Departamento de Computação UFS 10 42 Relacoes de recorrencia Metodo de substituicao Tn fatorialn Tn 1 n 0 Tn 1 1 n 0 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 12 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 13 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 14 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 15 42 Relações de recorrência Método de substituição Encontrar um padrão nas substituições Tn Tn 1 1 Tn 2 1 1 Tn 3 1 2 Tn 4 1 3 Tn k k C 2022 Bruno Prado Departamento de Computação UFS 16 42 Relações de recorrência Método de substituição Aplicar o caso base para encontrar o valor de k Tn Tn k k Tn k 1 n k 0 k n Substituindo na equação Tn T0 n 1 n On C 2022 Bruno Prado Departamento de Computação UFS 17 42 Relações de recorrência Método de substituição Aplicar o caso base para encontrar o valor de k Tn Tn k k Tn k 1 n k 0 k n Substituindo na equação Tn T0 n 1 n On C 2022 Bruno Prado Departamento de Computação UFS 18 42 Relações de recorrência Método de árvore de recursão Tn factorialn Tn 1 n 0 Tn 1 1 n 0 Relações de recorrência Método de árvore de recursão Solução gráfica Tn 1 Tn1 1 1 Tn2 1 1 1 T0 n 1 Tn n 1 On C 2022 Bruno Prado Departamento de Computação UFS 20 42 Relações de recorrência Método de árvore de recursão Solução gráfica Tn 1 Tn1 1 1 Tn2 1 1 1 T0 n 1 Tn n 1 On C 2022 Bruno Prado Departamento de Computação UFS 21 42 Relações de recorrência Método mestre Resolução de relações de recorrência no formato Tn aT n b fn a 1 número de subproblemas b 1 tamanho de cada subproblema fn assintoticamente positiva custo de combinar soluções C 2022 Bruno Prado Departamento de Computação UFS 22 42 Relações de recorrência Método mestre Caso 1 fn Onlogb aϵ com ϵ 0 Regra Tn Θnlogb a Exemplo Tn 4T n 2 n a 4 a 1 b 2 b 1 fn n n fn 0 fn n Onlogb aϵ 1 logb a ϵ ϵ log2 4 1 ϵ 1 Tn Θn2 C 2022 Bruno Prado Departamento de Computação UFS 23 42 Relações de recorrência Método mestre Caso 2 fn Θnlogb a Regra Tn Θnlogb a log n Exemplo Tn 2T n 2 n a 2 a 1 b 2 b 1 fn n n fn 0 fn n Θnlogb a 1 logb a 1 log2 2 1 1 Tn Θnlog2 2 log n Θn log n C 2022 Bruno Prado Departamento de Computação UFS 24 42 Relações de recorrência Método mestre Caso 3 fn Ωnlogb aϵ com ϵ 0 af n b cfn c 1 e n suficientemente grande Regra Tn Θfn Exemplo Tn 2T n 2 n2 a 2 a 1 b 2 b 1 fn n2 n fn 0 fn n2 Ωnlogb aϵ 2 logb a ϵ ϵ 2 log2 2 ϵ 1 C 2022 Bruno Prado Departamento de Computação UFS 25 42 Relações de recorrência Método mestre Caso 3 fn Ωnlogb aϵ com ϵ 0 af n b cfn c 1 e n suficientemente grande Regra Tn Θfn Exemplo Tn 2T n 2 n2 a 2 a 1 b 2 b 1 fn n2 n fn 0 af n b cfn n2 2 cn2 n c 1 2 Tn Θfn Θn2 C 2022 Bruno Prado Departamento de Computação UFS 26 42 Relações de recorrência Método mestre É preciso memorizar os casos Não resolve todas as recorrências como no cálculo do fatorial e da sequência de Fibonacci C 2022 Bruno Prado Departamento de Computação UFS 27 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Caso base n 1 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci recursivo 4 uint64t fibonacciuint32t n 5 ifn 1 6 return n 7 else 8 return fibonaccin 1 fibonaccin 2 9 fibonaccin 0 n 0 1 n 1 fibonaccin 1 fibonaccin 2 n 1 C 2022 Bruno Prado Departamento de Computação UFS 28 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Recorrência n 1 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci recursivo 4 uint64t fibonacciuint32t n 5 ifn 1 6 return n 7 else 8 return fibonaccin 1 fibonaccin 2 9 fibonaccin 0 n 0 1 n 1 fibonaccin 1 fibonaccin 2 n 1 C 2022 Bruno Prado Departamento de Computação UFS 29 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da substituição Tn Tn 1 Tn 2 2Tn 2 Tn 3 3Tn 3 2Tn 4 5Tn 4 3Tn 5 8Tn 5 5Tn 6 rn1Tn 1 rn2Tn 2 rn rn1 rn2 r2 r 1 0 r12 1 5 2 Recorrência de segunda ordem com raízes distintas C 2022 Bruno Prado Departamento de Computação UFS 30 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da substituição Tn Tn 1 Tn 2 2Tn 2 Tn 3 3Tn 3 2Tn 4 5Tn 4 3Tn 5 8Tn 5 5Tn 6 rn1Tn 1 rn2Tn 2 rn rn1 rn2 r2 r 1 0 r12 1 5 2 Recorrência de segunda ordem com raízes distintas C 2022 Bruno Prado Departamento de Computação UFS 31 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Raízes distintas Tn αρ₁ⁿ βρ₂ⁿ T0 α1 52⁰ β1 52⁰ 0 T1 α1 52¹ β1 52¹ 1 Tn 151 52ⁿ 1 52ⁿ Tn 1516ⁿ O16ⁿ Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da árvore de recursão T5 T4 T3 T2 T1 T0 T1 T2 T1 T0 T3 T2 T1 T0 T1 Árvore com altura n e em cada nó existem 2 filhos Complexidade é O2n C 2022 Bruno Prado Departamento de Computação UFS 33 42 Relações de recorrência Implementação recursiva do algoritmo de Fibonacci Método da árvore de recursão T5 T4 T3 T2 T1 T0 T1 T2 T1 T0 T3 T2 T1 T0 T1 Árvore com altura n e em cada nó existem 2 filhos Complexidade é O2n C 2022 Bruno Prado Departamento de Computação UFS 34 42 Relações de recorrência Implementação iterativa do algoritmo de Fibonacci 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci iterativo 4 uint64t fibonacciuint32t n 5 uint64t r n tn2 0 tn1 1 6 foruint32t i 1 i n i 7 r tn2 tn1 8 tn2 tn1 9 tn1 r 10 11 return r 12 fibonaccin c1 3 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 35 42 Relações de recorrência Implementação iterativa do algoritmo de Fibonacci 1 Padrão de tipos por tamanho 2 include stdinth 3 Fibonacci iterativo 4 uint64t fibonacciuint32t n 5 uint64t r n tn2 0 tn1 1 6 foruint32t i 1 i n i 7 r tn2 tn1 8 tn2 tn1 9 tn1 r 10 11 return r 12 fibonaccin c1 3 c2 n 1 Θn C 2022 Bruno Prado Departamento de Computação UFS 36 42 Exemplo Identifique qual dos algoritmos já visto possui a seguinte recorrência Resolva a recorrência para determinar a complexidade Tn 1 n 1 Tn 1 n n 1 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 38 42 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 39 42 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 40 42 Exemplo Método da substituição Série aritmética Tn Tn 1 n Tn 2 n 1 n Tn 3 n 2 n 1 n T1 n 2 n 1 n nn 1 2 n2 n 2 On2 C 2022 Bruno Prado Departamento de Computação UFS 41 42