Algoritmos de Busca: Análise da Busca Linear

Algoritmos para Pesquisa Monael Pinheiro Ribeiro DSc Universidade Federal do ABC Centro de Matemática Computação e Cognição Problema da Busca Formalmente Suponha uma coleção V de elementos de tamanho n V v0 v1 v2 vn1 E um elemento x qualquer Averiguar se x vi onde 0 i n Informalmente Verificar se um elemento x está no vetor V de tamanho n Se sim retorne o índice i tal que vi x caso contrário retorno 1 Busca Linear Acesse cada posição i 0 i n do vetor V averiguando se vi x Caso verdade retorne i Caso contrário verifique o próximo i Caso todo vetor seja verificado e nunca satisfez a condição vi x então retorne 1 Busca Linear 0 1 2 3 4 5 6 7 8 9 Buscar na lista Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Encontramos com 6 comparações Busca Linear 0 1 2 3 4 5 6 7 8 9 Qual o pior caso desse Algoritmo Quando ele terá o maior esforço computacional Quando ele fará o maior número de comparações Busca Linear 0 1 2 3 4 5 6 7 8 9 Buscar na lista Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Busca Linear 0 1 2 3 4 5 6 7 8 9 Foram necessárias 10 comparações para determinar que não aparece na lista Busca Linear 0 1 2 3 4 5 6 7 8 9 Foram necessárias 10 comparações para determinar que não aparece na lista E se a lista tivesse 100 elementos Busca Linear 0 1 2 3 4 5 6 7 8 9 Foram necessárias 10 comparações para determinar que não aparece na lista E se a lista tivesse 100 elementos E se a lista tivesse 1x106 E se a lista tivesse n elementos Complexidade de Algoritmos Foram necessárias 10 comparações para determinar que não aparece na lista E se a lista tivesse 100 elementos E se a lista tivesse 1x106 E se a lista tivesse n elementos Perceba que a quantidade de comparações aumenta conforme aumenta o tamanho da lista Complexidade de Algoritmos Perceba que a quantidade de comparações aumenta conforme aumenta o tamanho da lista O esforço do algoritmo quantidade de comparações aumenta conforme aumentase o tamanho da lista a uma taxa linear Tamanho Comparações 10 10 100 100 1x106 1x106 1x10100 1x10100 Complexidade de Algoritmos Linear On Busca Linear Algoritmo em JAVA 01 public static int buscaint v int n int x 02 03 int i 04 fori0 in i 05 06 ifvi x 07 08 return i 09 10 11 return 1 12 Complexidade de Algoritmos Existe algum algoritmo mais eficiente para se realizar a busca Complexidade de Algoritmos Existe algum algoritmo mais eficiente para se realizar a busca Sim Entretanto a lista de elementos deve estar ordenada Busca Binária Suponha que a lista de elementos esteja ordenada pelo campo ao qual você deseja realizar a busca Na busca linear iterativa quantas comparações são necessárias para encontrar o elemento 95 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 Busca Binária Suponha que a lista de elementos esteja ordenada pelo campo ao qual você deseja realizar a busca Na busca linear iterativa quantas comparações são necessárias para encontrar o elemento 95 A Busca Binária faz isso com 2 comparações 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 95 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 95 3 Elemento na posição meio é 95 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 95 3 Elemento na posição meio é 95 31 Não Então esq meio1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 95 3 Elemento na posição meio é 95 31 Não Então esq meio1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 95 3 Elemento na posição meio é 95 31 Não Então esq meio1 Volte ao 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 95 3 Elemento na posição meio é 95 31 Não Então esq meio1 Volte ao 1 meio Busca Binária Pior caso Na busca linear iterativa quantas comparações são necessárias para determinar que o elemento 74 não está na lista 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 Busca Binária Pior caso Na busca linear iterativa quantas comparações são necessárias para determinar que o elemento 74 não está na lista A busca binária faz isso com 4 comparações 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 32 Sim Então dir meio 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 esq dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 dir esq meio Busca Binária Funcionamento 0 1 2 3 4 5 6 7 8 9 43 65 69 76 85 89 93 95 99 107 dir 1 meio esqdir2 2 É o 74 3 Elemento na posição meio é 74 31 Não Então esq meio1 Volte ao passo 1 32 Sim Então dir meio 1 Volte ao passo 1 meio esq ficou maior que dir Portanto a busca terminou sem encontrar o 74 Deste modo antes do passo 1 devese sempre verificar se esqdir esq Busca Binária Algoritmo em JAVA public static int buscaBinint v int n int x int esq0 dirn1 meio whileesqdir meio esqdir2 ifvmeio x return meio else ifvmeio x dir meio1 else esq meio 1 return 1 Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 Comparações 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 Comparações 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 Comparações 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 3 Comparações 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 3 Comparações 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 3 1 Comparações 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 3 1 Comparações 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos No pior caso elemento não existir qual o esforço computacional da Busca Binária Quantas comparações a Busca Binária fará Perceba que a cada iteração o vetor é dividido pela metade Tamanho do Espaço de Busca 16 7 3 1 0 Comparações 0 1 2 3 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir esq meio Análise de Algoritmos Pensem Tamanho Comparações 16 1 7 11 3 111 1 1111 0 Análise de Algoritmos Pensem Tamanho Total de Comparações 24 1 231 2 221 3 211 4 201 Análise de Algoritmos Pensem Sempre divido o vetor pela metade Quantas vezes consigo dividilo pela metade Tamanho Total de Comparações 24 1 231 2 221 3 211 4 201 Análise de Algoritmos Pensem Sempre divido o vetor pela metade Quantas vezes consigo dividilo pela metade Quantas vezes consigo dividir um vetor de tamanho 16 pela metade Tamanho Total de Comparações 24 1 231 2 221 3 211 4 201 Pensem Sempre divido o vetor pela metade Quantas vezes consigo dividilo pela metade Quantas vezes consigo dividir um vetor de tamanho 16 pela metade Análise de Algoritmos Tamanho Total de Comparações 24 1 231 2 221 3 211 4 201 Análise de Algoritmos Pior Caso Busca Binária No pior caso são necessárias log2 n comparações Portanto a Busca Binária é um algoritmo logarítmico ou Olog2 n Análise de Algoritmos Pior Caso Busca Binária Olog2 n Análise de Algoritmos Algoritmo Linear x Algoritmo Logarítmico