Skip to content

Análise de complexidade de algoritmos

Quando pensamos em algoritmos, logo vem à mente um procedimento onde pode haver entradas e uma sequência de passos e operações para produzir uma saída que satisfaça a resolução de um problema. Segundo Cormen (2002), um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída. Esta afirmação está congruente a nossa linha de pensamento. Para um algoritmo ser satisfatório, temos que ter a capacidade de avaliá-lo para saber se ele atende ou não as nossas expectativas. Simplesmente produzir a saída, não é satisfatório. Imagine um algoritmo simples que efetue uma operação básica de soma, exemplo 20 + 3 + 15 e demora-se 5 minutos para dar um resultado, esse algoritmo é bom? Vamos pensar…

Temos as entradas, o processamento e a saída. Guarde na sua mente que as entradas são as instâncias do problema e é sobre essas instâncias que temos que nos preocupar na hora de implementarmos nossos algoritmos. Por exemplo, um algoritmo que recebe como entrada uma estrutura de dados e gera a ordenação de seus elementos.

É sobre essa ótica que você vai analisar a complexidade do algoritmo com vista no tamanho do problema.

Diferentes computadores, muitas vezes com hardwares idênticos, podem levar tempos diferentes para processar um mesmo algoritmo. Por tanto, avaliar o desempenho de um algoritmo com base apenas no tempo de execução é ineficiente.

Quando estudamos a complexidade de um algoritmo, estamos definindo quão eficiente ele é em relação ao número de operações (passos) necessárias para sua conclusão. A preocupação principal se dá quando temos que processar uma quantidade alta de dados. E é através da análise assintótica que conseguimos analisar o comportamento de um algoritmo tendo em vista esse grande volume de dados de entrada.

Para medir a complexidade de um algoritmo utilizamos uma função de complexidade f , onde f(n) é a medida do tempo/espaço necessário para executar um algoritmo para um problema de tamanho n. Ou seja, função de complexidade de tempo podemos medir o número de operações necessárias para executar um algoritmo e complexidade de espaço medimos a memória necessária para a execução de um algoritmo. Ao relacionarmos o número de instruções com o tamanho do conjunto de dados podemos ter 3 possíveis cenários: melhor caso, caso médio e o pior caso.

O melhor caso corresponde ao menor tempo de execução sobre todas as possíveis entradas de tamanho n.

 f(n) = Ω(1)

O caso médio corresponde à média dos tempos de execução de todas as entradas de tamanho n.

f(n) = θ(n/2)

O pior caso corresponde ao maior tempo de execução sobre todas as entradas de tamanho n.

f(n) = O(n)

Note que utilizamos 3 notações para representar os possíveis casos: Ômega, Theta e Ómicron ou Big O. A maneira mais comum de analisar a complexidade de um algoritmo é pelo pior caso, Big O. Você naturalmente não avalia o melhor caso, porque essas condições não são atingidas com frequência.

Conceitualmente funciona assim: Se um tempo de execução é O(f(n)), então para um n suficientemente grande, o tempo de execução é no máximo c · f(n) para alguma constante c, onde > 0. Dizemos que o tempo de execução é “Big-O de f(n)” ou só “O de f(n)”.

Outra forma mais usual de representar é dizer que f(n) = O(g(n)). Quando dizemos que f(n) = O(g(n)) garantimos que g(n) é um limite superior sobre f(n).  Escrevemos desta forma: f(n) ≤ c · g(n), onde c é uma constante positiva.

A complexidade de tempo não representa tempo diretamente, mas o número de vezes que determinada operação considerada relevante é executada. Deste modo observamos o maior peso relevante para determinar a sua complexidade. Como por exemplo, um algoritmo para capturar o maior valor de um array  de inteiros A[1..n], n ≥ 1, logo f(n) = n−1, para n ≥ 1.  Ou seja, possuem complexidade linear no tamanho da entrada, ou O(n), em que n é o tamanho da entrada.

Outro exemplo, ao analisarmos o algoritmo para ordenação por flutuação Bubble sort, a ideia é percorrer o array diversas vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência.  No pior caso, são feitas n2 operações. A complexidade desse algoritmo é de ordem quadrática, ou O(n2)

O pior caso ocorre quando o array está ordenado em ordem decrescente, pois o algoritmo terá que realizar a troca em todas as iterações. A quantidade de iterações do laço do primeiro for é igual a n-1, já o segundo laço será executado de acordo com o valor de i do primeiro laço for:

A resolução se dá por:

A notação Big O é a mais utilizada na análise de complexidade de algoritmos em geral, normalmente para pior caso (entretanto, há casos como o algoritmo QuickSort, por exemplo, que a notação O também é utilizada para o caso médio). As outras são raramente utilizadas: a notação é usada algumas vezes para definição de limites inferiores. Porém, é importante lembrar que as definições de notações são independentes da análise de algoritmos, podendo ser utilizados para outros fins.

Ao compararmos dois algoritmos para medir a sua eficiência, o algoritmo mais eficiente (mais rápido) será aquele cuja função de complexidade cresce mais lentamente à medida em que aumentamos o tamanho da sua entrada. As complexidades assintóticas mais comuns são:

  • O(1) = Complexidade constante o tempo de execução do algoritmo é independe do tamanho da entrada.
  • O(log(n)) = Complexidade logarítmica o tempo de execução pode ser considerado menor do que uma constante grande.
  • O(n) = Complexidade linear o algoritmo realiza um número fixo de operações sobre cada elemento de entrada
  • O(n log(n)) = Típico de algoritmos que dividem um problema em subproblemas, resolve cada subproblema de forma independente, e depois combina os resultados
  • O(n2) = Complexidade quadrática. Itens são processados aos pares, geralmente com um loop dentro do outro um loop.
  • O(n3) = Complexidade cúbica é útil para resolver problemas pequenos como multiplicação de matrizes.
  • O(mn) = Complexidade exponencial. O número de instruções também cresce muito rápido (exponencialmente), ainda que em uma taxa menor do que o anterior. Típicos de algoritmos que fazem busca exaustiva (força bruta) para resolver um problema
  • O(n!) = Complexidade fatorial. Também é considerado uma complexidade exponencial, apesar de que a complexidade fatorial tem comportamento muito pior.

A entrada dos dados, como já mencionei,  é um fator de extrema importância no que tange a análise assintótica. Ou seja, a análise é “input bound”, a entrada influenciará diretamente no resultado. Você perceberá com maior ênfase analisando a simulação distribuída a seguir. A medida que aumenta o valor de n, impacta diretamente no consumo quando se é necessário uma utilização maior de recursos no algoritmo:

Esse assunto é muito mais abrangente do que o disposto neste artigo. Para uma maior profundidade, recomendo a leitura do  livro Algoritmos Teoria e Prática de Thomas Cormen. O objetivo principal deste artigo é demonstrar a necessidade de utilizarmos técnicas de medições de complexidade dos nossos algoritmos de modo a buscarmos sempre construir algoritmos eficientes não apenas eficazes. A diferença entre eficácia e eficiência é que enquanto a eficácia refere-se a fazer a tarefa certa, completar atividades e alcançar metas, a eficiência é sobre tudo, fazer as coisas de forma otimizada, de maneira mais rápida ou com menos gastos. Pensem nisso! Nos vemos no próximo artigo!

Confiança Sempre!!!

Referências:

  • P. Feofiloff,  Minicurso de Análise de Algoritmos, 2009.
  • Thomas Cormen; Charles Leiserson and Ronald. Rivest, Algoritmos Teoria e Prática, Elsevier, 2012.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,  Introduction to Algorithms, 3rd edition,  MIT Press, 2009.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,  Introduction to Algorithms, 2nd edition, MIT Press & McGraw-Hill, 2001.
  • Jon Kleinberg, Éva Tardos, Algorithm Design,  Addison-Wesley, 2005.
  • S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani,  Algorithms,  McGraw-Hill, 2006
  • G. Brassard, P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
  • Kurt Mehlhorn, Peter Sanders,  Algorithms and Data Structures – The Basic Toolbox, Springer, 2008
  • Steven Skiena,  The Algorithm Design Manual,  Telos/Springer-Verlag, 1998.

 

Publicado emAlgoritmos

2 Comentários

  1. Henry Henry

    Excelente artigo, o uso de estruturas de dados em nossa carreira de desenvolvedor é essencial e deve ser aperfeiçoado com frequência, tal abordagem nos ajuda a resolver muitas problemáticas do nosso dia-a-dia.

    • Walmir Silva Walmir Silva

      É isso mesmo Henry! Obrigado pelo comentário!

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Copyright 2018 · Walmir Silva · www.likesys.com.br
shares