domingo, 1 de setembro de 2013

Por que devemos conhecer algoritmos

Existem diversos livros sobre algoritmos no mercado. Somente como exemplo mostro alguns abaixo:


 

 

O conhecimento de algoritmos é importante para podermos criar bons programas. Vamos mostrar no vídeo a seguir que utilizar uma aproximação errada por gerar um programa fácil de ler porém extremamente ineficiente. O melhor exemplo disto é a implementação do cálculo do número da série de Fibonacci.

Pesquisa de bits

Vamos ver neste post duas formas de pesquisa que apresentam vantagens diferentes dependendo do tipo de dados que estamos utilizando. Consideraremos como exemplo a avaliação de uma sequencia de bits. Esta sequencia será passada para o programa como um vetor de inteiros, desta forma queremos achar o primeiro a[i] cujo valor é igual a 1, isto é, que divide o array em duas partes, a inferior contendo "0"s e a superior contendo "1"s.

O primeiro tipo de pesquisa que iremos utilizar é denominado busca linear ou busca sequencial. Este tipo de pesquisa é aplicado em vetores ou listas de modo sequencial, i. e., elemento por elemento, do menor para o maior (ou vice-versa). Deste modo o tempo de execução é função do do número de elementos. Num vetor ordenado, essa não é a pesquisa mais eficiente. No nosso caso veremos que se esperamos que existam poucos bits "0", esta será a melhor opção.

Uma outra pesquisa é a busca binária, onde o tempo de pesquisa é logaritmo em relação ao número de elementos. Este tipo de pesquisa segue o paradigma de dividir e conquistar um vetor ordenado. Funciona mediante sucessivas divisões do espaço de busca, comparando o elemento buscado (ou chave - no nosso caso o primeiro elemento com bit 1) com o elemento no meio do subvetor pesquisado. Este procedimento é facilmente implementado recursivamente.

Vamos ver nosso exemplo: