Baixe o app para aproveitar ainda mais
Prévia do material em texto
ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação Lista de Exercícios de Fixação 03 Análise de Algoritmos de Busca 1. Considere as técnicas de pesquisa sequencial, pesquisa binária e pesquisa baseada em hashing. Descreva as vantagens e desvantagens de cada uma dessas técnicas, indicando em que situações, são de fato viáveis; Sequencial Binária Hashing Vantagem Simplicidade Eficiência Eficiência Desvantagem Custo elevado Arranjo deve estar ordenado Não recupera em ordem 2. Explique por que a busca binária: a. É mais eficiente do que a busca sequencial. Em cada passo da busca sequencial, ao comparar a chave de busca com a próxima chave do conjunto, diminuímos o tamanho do problema em uma unidade. Na busca binária, a cada passo, diminuímos pela metade o tamanho do problema. Assim, no pior caso, quando a chave de busca não está na lista, a busca sequencial pode levar até n comparações (n é o tamanho da lista), enquanto a busca binária levaria lgn comparações. b. Só pode ser efetuada em um array. Num array ordenado, temos acesso direto à sua mediana por meio dos seus índices. Ao somar os índices das extremidades e dividir por dois, obtemos o endereço do valor mediano. Isso só é possível quando (a) temos acesso a eles e (b) eles são consecutivos. 3. Considere a lista linear sequencial de inteiros no vetor, a seguir. 2 4 6 8 10 12 14 16 a. Considerando o método da busca binária: 1. Quantas comparações (e com quais chaves) são necessárias na busca pelo valor 15? Compara-se com as chaves 8, 12, 14 e 16 (4 comparações) 2. Idem para o inteiro 6. Compara-se com as chaves 8, 4 e 6 (3 comparações) b. Considerando a Busca Sequencial: 100 50 200 300 400 150 250 350 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 1. Quantas comparações (e com quais chaves) são necessárias pelo valor 15? Compara-se com as chaves 2, 4, 6, 8, 10, 12, 14 e 16 (8 comparações) 2. Idem para o inteiro 6. Compara-se com as chaves 2, 4 e 6 (3 comparações) c. Generalize o número máximo de comparações na Busca Binária e na Busca Sequencial, considerando o tamanho do vetor igual a n. Na busca binária lgn e na busca sequencial n. 4. Suponha que você tenha uma árvore binária na qual estão armazenadas uma chave em cada nodo. Suponha também que a árvore foi construída de tal maneira que, ao caminhar nela na ordem central, as chaves são visitadas em ordem crescente. Sendo assim, qual propriedade entre as chaves deve ser satisfeita para que isso seja possível? Todos os registros com chaves menores estão na subárvore esquerda e todos aqueles com chaves maiores estão na subárvore direita. 5. Em uma tabela hash com 100 entradas, as colisões são resolvidas usando listas encadeadas. Para reduzir o tempo de pesquisa, decidiu-se que cada lista seria organizada como uma árvore binária de pesquisa sem balanceamento. A função utilizada é h(k) = k mod 100. Infelizmente, as chaves inseridas seguem o padrão ki = 50i, onde ki corresponde à i-ésima chave inserida. a. Mostre a situação da tabela após a inserção de ki, com i = 1, 2, …, 8 (esquematize); K1 = 50 mod 100 = 50 K2 = 100 mod 100 = 0 K3 = 150 mod 100 = 50 K4 = 200 mod 100 = 0 K5 = 250 mod 100 = 50 K6 = 300 mod 100 = 0 K7 = 350 mod 100 = 50 K8 = 400 mod 100 = 0 0 50 99 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação b. Considerando a busca nessa tabela hash, qual é a complexidade para o pior caso? O pior caso depende da solução utilizada para o tratamento das colisões (no caso, árvore binária de pesquisa sem balanceamento). Com isso, caímos no seu pior caso, ou seja, T(n) = n/2 → O(n). 6. Tabelas de dispersão (tabelas hash) armazenam elementos com base no valor absoluto de suas chaves e em técnicas de tratamento de colisões. As funções de dispersão transformam chaves em endereços-base da tabela, ao passo que o tratamento de colisões resolve conflitos em casos em que mais de uma chave é mapeada para um mesmo endereço-base da tabela. Suponha que uma aplicação utilize uma tabela de dispersão com 23 endereços-base (índices de 0 a 22) e empregue h(x) = x mod 23 como função de dispersão, em que x representa a chave do elemento cujo endereço-base deseja-se computar. Inicialmente, essa tabela de dispersão encontra-se vazia. Em seguida, a aplicação solicita uma sequência de inserções de elementos cujas chaves aparecem na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95. a. Apresente o conjunto das chaves envolvidas em colisões. b. Assuma que a tabela de dispersão trate colisões por meio de encadeamento exterior. Esboce a tabela de dispersão para mostrar seu conteúdo após a sequência de inserções referida. [Similar à questão anterior] 7. Qual é o pior tempo para inserir n elementos em uma tabela hashing inicialmente vazia, com colisões sendo resolvidas por listas encadeadas? Qual seria o melhor caso? Pior caso seria T(n) = n e o melhor caso, T(n) = 1. 8. Considerando que as chaves inseridas em um Hashing não provocaram colisão, independente do algoritmo, podemos dizer que a pesquisa por uma chave na tabela será de ordem de complexidade constante, ou seja, T(n) = 1? Podemos dizer que este algoritmo é ótimo? Justifique. Sim. O algoritmo é ótimo, pois o acesso à chave é direto. Lista de Exercícios de Fixação 03
Compartilhar