Introdução a Análise de Algoritmos – Parte #2

Algoritmos, Análise de Algoritmos, Insertion Sort, Ordenação 1 Response »
out 092011

O primeiro algoritmo que analisaremos será o INSERTION SORT (null), cujo código está descrito abaixo em C#. Eu recomendo fortemente que você o implemente para se familiarizar com seu funcionamento e caso tenha dúvidas recorra aos vídeos sugeridos que são altamente didáticos e estão disponíveis na seção de links deste post.

Tempo de Execução

O tempo de execução deste algoritmo depende de alguns fatores, dentre eles:

  • A entrada em sí: Se a entrada já se encontra ordenada o insertion sort tem muito pouco trabalho a fazer, já que não precisa executar o looping interno nenhuma vez. Perceba que o pior caso para este algoritmo é quando o vetor de entrada se encontra reversamente ordenado, onde para todas as iterações do looping externo ele executa outras null iterações.
  • Tamanho da entrada: Leva-se mais tempo para ordenar 1000 elementos do que apenas 6. Portanto fala-se to tempo de execução como uma função do número de elementos na entrada.

Quando estamos analisando o tempo de execução nós geralmente queremos o tempo máximo, ou o limite superior deste tempo, pois desta maneira temos uma garantia de que o mesmo não excederá um dado limite. Se é dito que o limite inferior de um algoritmo é de 3 segundos não podemos deduzir que seu tempo máximo será 3 minutos ou 3 anos, não fornecendo uma informação relevante ao usuário. Desta forma temos alguns tipos de análise:

  • Pior caso (geralmente): Tempo máximo para qualquer entrada de tamanho null.
  • Caso médio (algumas vezes): Tempo esperado para todas as entradas de tamanho null. Para esta análise é necessária uma premissa a respeito da distribuição estatística das entradas. Uma premissa comum é de que todas as entradas são igualmente prováveis (ou distribuição uniforme).
  • Melhor caso (nunca): Algum algoritmo pior pode trabalhar mais rápido para uma entrada específica, e portanto este tipo de análise não provê garantia alguma a respeito de seu tempo de execução.

Então qual o tempo de execução de pior caso do insertion sort? Poderíamos inicialmente responder de que depende da máquina, mas na verdade estamos interessados em saber um tempo de execução relativo, independente de hardware, pois é claro que se estivermos executando o mesmo algoritmo em uma máquina mais eficiente teremos um menor tempo. Utilizamos a ideia da análise assintótica para ignorar constantes relativas a máquina e olhar então apenas para o crescimento do tempo de execução a medida que o número de entradas se aproxima do infinito (null).

Análise Assintótica

Notação-Θ: Descarta-se termos de menor ordem e ignora-se constantes. Veja um exemplo abaixo.

null

Podemos dizer que um algoritmo null sempre ultrapassa, ou sempre é mais performático que um null , mesmo executando o último em um computador mais poderoso. A notação assintótica portanto resolve nosso problema em  sermos capazes de comparar velocidades relativas e absolutas, independentemente de computador ou plataforma específicos. Embora hajam diferenças nas constantes específicas de cada máquina podemos afirmar que sempre haverá um ponto onde a função null passa a executar mais rapidamente que null. Porém algumas vezes este ponto pode ser tão grande que mesmo uma função assintoticamente pior pode ser mais vantajosa quando lidamos com um universo entradas menor que este ponto. O gráfico abaixo ilustra esta idéia.

Análise do Insertion Sort

Após termos introduzido o conceito de análise assintótica podemos finalmente obter o tempo de execução do insertion sort. Para isso, nós consideramos que cada operação elemental custa uma quantia constante de tempo, onde não precisamos nos importar com seu valor já que analisaremos assintoticamente. Na listagem abaixo apresentamos novamente o insertion sort porém em cada linha são apresentados mais dois valores, um que representa seu custo computacional e outro que representa o número de execuções desta linha. Para este exemplo null e null o número de vezes que o loop interno null é executado para cada valor de null.

O tempo de execução de um algoritmo é a soma dos tempos de execução de cada linha. Se uma linha custa null para ser executada e é executada null vezes, então ela contribuirá com null para o tempo total. Para o insertion sort temos:

Para concluirmos nossa análise precisamos decidir a respeito de null. Imagine que fossemos analisar o melhor caso, então fica claro que o loop interno nunca seria executado, pois sua condição nunca seria verdadeira (os números já estão ordenados, null nunca seria maior que null), nesta ocasião poderíamos substituir o primeiro somatório acima por null, que seria apenas o custo da sua verificação para cada iteracao de zero a null, o segundo e terceiro somatórios seriam excluídos da nossa fórmula já que seriam instruções que nunca seriam executadas. No entanto estamos interessados no pior caso, onde para cada chave no índice null o algoritmo percorre todo o array até o primeiro índice, ou seja, o número de iterações do loop interno é o próprio valor de null, portanto para o pior caso null.

Desta maneira nossos somatórios acima se transformam respectivamente em (haverá um post apenas sobre o background matemático dessas conclusões):

null

null

Substituindo temos

null

Aplicando a distributiva e colocando em evidência os fatores null e null temos:

null

Que é uma função quadratica da forma

null

Analisando assintoticamente (descartando os termos de menor ordem e desconsiderando constantes) chegamos a conclusão que o tempo de execução, ou a ordem de crescimento do insertion sort é null.

Consideramos que um algoritmo é mais eficiente quando seu tempo de pior caso tem uma ordem de crescimento menor do que outro. Devido a fatores relacionados as constantes e termos de menor ordem esta conclusão pode estar errada para pequenas entradas, mas não para entradas grandes o suficiente.

Posted by Renato Gama at 5:03

Introdução a Análise de Algoritmos – Parte #1

Análise de Algoritmos, Insertion Sort, Merge Sort, Performance 1 Response »
out 032011

Bem, este vai ser o primeiro post da série relacionada a análise de algoritmos. Este post tem o objetivo de ser curto e trazer alguns conceitos básicos relacionados ao tema, portanto espero que ele seja curto porém interessante, ao menos para mim que me considero (semi-)leigo no assunto.

O conteúdo abaixo representa uma síntese da minha compreensão do primeiro e um pouco do segundo capítulo do livro [1] e do vídeo [2]

Introdução

O que são algoritmos?

Algoritmo é qualquer procedimento computacional bem definido que recebe um valor, ou conjunto de valores, como entrada e  produz algum valor ou conjunto de valores como saída. Um algoritmo é portanto uma sequência de passos computacionais que transformam a entrada na saída . [1, TL].

O que é análise de algoritmos?

Análise de algoritmos é o estudo teórico da performance e uso de recursos de um programa de computador. [2, TL].

Obviamente podem haver mais definições, mas para o contexto do meu estudo, que compartilho aqui vocês, creio que estas duas são adequadas.

Hoje em dia, quando pensamos em computação pensamos em várias coisas, que muitas vezes são mais importantes que performance, vejamos:

  1. Corretude
  2. Simplicidade
  3. Manutebilidade
  4. Custo
  5. Robusteza
  6. Funcionalidades
  7. Modularidade
  8. Segurança
  9. Escalabilidade
  10. Interface amigável

Então porque estudar performance? Bem, façamos uma analogia, imagine que tenhamos muito dinheiro, várias pilhas de notas de 100USD, por exemplo. Para que as pilhas de dinheiro em sí servem? Em sí, elas são inúteis, quer dizer, poderiamos ao menos utilizalas como combustível para uma fogueira casos nos encontrassemos perdidos em uma ilha ou algo do gênero. Porém, muito útil são as coisas pelas quais o dinheiro pode ser trocado, por exemplo: comida, água, abrigo (hotel, casa, apartamento), transporte, e por aí vai.

Podemos pensar na performance como o nosso dinheiro para comprar todos os itens especificados acima, e também podemos pensar que a evolução da tecnologia dos algoritmos nos possibilita atingir um nível cada vez mais avançado e satisfatório de necessidades como estas. A performance cria então uma base comum para todas as outras coisas que nos importamos.

Desta forma a performance mede o que é factível ou não na computação. Exemplificando esta afirmação, pense em um sistema de tempo real onde caso o requisito temporal não seja atingido o sistema se torna completamente inútil. Além disso, a análise de algoritmos provê uma linguagem comum para nos referirmos ao comportamento de um programa.

E se… os computadores fossem infinitamente rápidos e memória fosse grátis. Mesmo assim ainda haveriam razões para continuar se estudando algoritmos? SIM. A menos que você não estivesse preocupado em provar que seu algoritmo termina e faz isso com a resposta correta, além de não estar interessado em manter-se no limiar das boas práticas da engenharia de software.

Eficiência

Algoritmos planejados para resolver o mesmo problema frequentemente diferem na sua eficiência. Essas diferenças podem ser muito mais significantes do que diferenças relacionadas a hardware.

Vejamos dois algoritmos com o mesmo propósito, ordenar números em um array. Digamos que um leva instruções para ordenar itens, onde  é uma constante que não depende de  e que não está relacionada a eficiência instrinseca do algoritmo. O segundo algoritmo leva onde significa , e outra constante. Embora o algoritmo 2 tenha um fator no seu tempo de execução, que é muito menor que que fator  do algoritmo 1, veremos que para um dado número de elementos grande o suficiente, o algoritmo 2 mais do que compensa a diferença entre as constantes e , caso seja muito maior que . Ou seja, não importa quanto seja menor que , sempre haverá um ponto de cruzamento onde o algoritmo 2 será mais rápido que o 1. O algoritmo 1 é conhecido como INSERTION SORT, e o 2 como MERGE SORT.

Para um exemplo concreto suponha um computador rápido A rodando o INSERTION SORT e um mais lento B rodando o MERGE SORT. Ambos precisam ordenar um array com um milhão de números. Suponha que o computador A execute um bilhão de instruções por segundo e que o computador B execute dez milhões de instruções por segundo, ou seja, o computador A é 100 vezes mais rápido que o B. Para tornar o exemplo ainda mais apelativo, imagine que o algoritmo rodando no computador A foi codificado por um programador muito habilidoso e que portanto roda em instruções para ordenar números (onde ) e que o MERGE SORT foi foi codificado por um programador mediano e que ainda por cima utilizou uma linguagem de alto nível, necessitando então de instruções (onde ). Calculando-se o tempo necessário para a execução de cada algoritmo obtemos:

Por utilizar um algoritmo cujo tempo de execução cresce mais lentamente, mesmo com um compilador mais fraco o computador B executa 20 vezes mais rápido. A vantagem do MERGE SORT é ainda mais evidente quando organizamos 10 milhões de números: enquanto o INSERTION SORT leva aproximadamente 2,3 dias o MERGE SORT leva menos de 20 minutos. Em geral, a medida que o número de elementos cresce também cresce a vantagem relativa do MERGE SORT.

Como vimos na comparação anterior podemos perceber que são em grandes problemas que se diferenciam as eficiências entre os algoritmos. Ter uma base sólida de conhecimento em algoritmos e técnicas é o que realmente separa programadores qualificados dos iniciantes.

A figura abaixo ilustra o crescimento de algumas funções mais importantes. Perceba que este gráfico esta desenhado em uma escala para representar a relação entre as funções e as linhas não representam exatamente as inclinações de cada função. [3]

Posted by Renato Gama at 0:02
© 2013 Renato Gama Suffusion theme by Sayontan Sinha