Devo confessar que durante a minha graduação, nunca prestei muita atenção na parte mais “teórica” da computação. O que eu queria era sentar e “codar”, sem realmente me preocupar com algoritmos, estruturas de dados, ou com os impactos que a minha solução ocasionaria em um determinado ambiente.
Com a idade vem a experiência, e com a experiência vem a necessidade de estressar diferentes pontos de vista antes de adotar solução X ou Y. Foi a partir dessa necessidade que fui obrigado a revisitar alguns conceitos básicos da Ciência da Computação, e fatalmente me senti motivado a compilar esse conhecimento em uma série de artigos, aqui para o Profissionais TI.
Se você, assim como eu, deu aquela dormida nas aulas de Teoria da Complexidade Computacional, junte-se a mim e vamos relembrar esses conceitos juntos.
Algoritmos e tempos de execução
Segundo o Wikipedia, um Algoritmo é:
(…) uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais devendo ser executadas mecânica ou eletronicamente em um intervalo de tempo finito e com uma quantidade de esforço finita.
A sua aplicação pode ser composta por uma porção de algoritmos, cada um destinado a um fim muito específico. Por exemplo, você pode ter um algoritmo responsável por encontrar todos os pedidos vendidos no último mês, que contenham um determinado produto. Com o advento do Big Data, inúmeros algoritmos são postos em prática para mineração e análise de dados, então, mesmo que exista uma aplicação ou serviço resolvendo esses problemas para você, acredite… os algoritmos estarão lá.
![algorithms](http://s.profissionaisti.com.br/wp-content/uploads/2016/06/algorithms.jpg)
Imagem via Wired
Um determinado algoritmo pode ter tempos de execução relativamente diferentes de acordo com o ambiente no qual ele esteja rodando. Se for num computador Core i7 e 16GB de RAM, é possível assumirmos que ele rodará consideravelmente melhor do que se estivesse operando em um Raspberry Pi, por exemplo. Ainda há um segundo cenário onde, talvez você tenha escrito o algoritmo perfeito em Python ou Ruby, mas ele corre o risco de executar de forma mais lenta que um algoritmo em Assembly ou C.
Partindo da premissa que um bom algoritmo é um conjunto de operações que resolvem um problema em tempo e esforço atrativos, como podemos classificar se um algoritmo é “rápido” ou não?
É aí que entra a análise assintótica.
A Análise Assintótica
Segundo o Wikibooks, a análise assintótica é:
(…) a way of expressing the main component of the cost of an algorithm, using idealized (not comparable) units of computational work.
Em termos mais práticos, é uma forma de julgarmos se o nosso algoritmo é eficiente, independente dos “recursos que o cercam” (como velocidade de processamento, quantidade de memória, latência de rede, etc).
Removendo todas as variáveis que podem influenciar no tempo de execução, focamos nossas atenções em como o algoritmo está escrito, em qual é a sua entrada, e se “ele por si” é a maneira mais eficiente para a resolução de um determinado problema.
Vale reforçar que a entrada é um fator de extrema importância no que tange a análise assintótica. A análise é “input bound”, ou seja, a entrada influenciará diretamente no resultado do estudo. Por exemplo, quando ordenamos um vetor de tamanho N, utilizando o algoritmo Selection Sort, teremos um tempo de execução de N2 (já que o algoritmo pega um número, e compara com os demais números no vetor, repetindo essa operação até chegar ao fim do dado estruturado).
Ao fim da análise, podemos chegar a 2 conclusões diferentes: Melhor cenário e pior cenário.
Big O, Big Omega e Big Theta
Quem trabalha com desenvolvimento (ou até mesmo com computação num geral), já deve ter ouvido falar sobre o famigerado Big O Notation. Ele é uma notação assintótica muito famosa na análise de tempos de execução de algoritmos. O que pode ser uma surpresa é que ele não é a única notação que temos disponível:
- O(n): Expressa o limite superior do tempo de execução de um algoritmo (pior cenário);
- Ω(n): Expressa o limite inferior do tempo de execução de um algoritmo (melhor cenário);
- Θ(n): Expressa limite superior e inferior do tempo de execução de um algoritmo (pior e melhor cenário).
Além da expressão linear, temos outras notações que descrevem diferentes tempos de execução:
- O(1): Constante
- O(log n): Logarítmica
- O(n): Linear
- O(n log n): “Linearithmic” (maior que linear, menor que quadrática)
- O(n2): Quadrática
- O(n3): Cúbica
- nO(1): Polinomial
- 2O(n): Exponencial
De maneira simplista, N pode ser considerado como o número de operações que o algoritmo leva para chegar ao seu final. N está intimamente ligado com a entrada do seu algoritmo, onde quanto maior for o seu número, maior será o seu tempo de execução.
E como fazemos para contar o número de operações realizadas por um algoritmo?
Um pouquinho de prática
Voltando a citar o Selection Sort, que trata-se de um “greedy algorithm” para ordenação de números em um vetor, temos a seguinte sequencia de operações:
for i from 1 to n-1 { Encontre um elemento menor que a i-ésima posição, entre as n entradas. Troque o elemento encontrado com a i-ésima entrada. }
Fazendo um pequeno teste de mesa, com o vetor (9, 2, 5, 7, 4, 8), temos o seguinte conjunto de procedimentos:
- [9, 2, 5, 7, 4, 8]: i=1; Encontre o menor número entre posições 1 e 6; Troque array[i] com array[2]
- [2, 9, 5, 7, 4, 8]: i=2; Encontre o menor número entre posições 2 e 6; Troque array[i] com array[5]
- [2, 4, 5, 7, 9, 8]: i=3; Encontre o menor número entre posições 3 e 6; Troque array[i] com array[3]
- [2, 4, 5, 7, 9, 8]: i=4; Encontre o menor número entre posições 4 e 6; Troque array[i] com array[4]
- [2, 4, 5, 7, 9, 8]: i=5; Encontre o menor número entre posições 5 e 6; Troque array[i] com array[5]
- [2, 4, 5, 7, 8, 9]: i=6; Fim do laço
Podemos separar a análise em 3 grupos:
- Tempo de execução para encontrar o menor elemento
- Tempo de execução para trocar de elemento
- Tempo de execução do laço
Embora seja possível fazer uma análise detalhada, levando em consideração o número de passos dentro de uma operação de swap de valores, e a aritmética envolvendo as N-i-1 chamadas que ocorrem dentro da função “Encontre o menor número entre posições”, para fins didáticos vamos adotar uma abordagem superficial.
Selecionar o menor elemento no array e fazer o swap para a primeira posição requer passar por todos os N-1 elementos. Encontrar o próximo menor elemento requer analisar os N-1 elementos restantes. Com dois for aninhados, executando em ordem N, já podemos esperar uma execução em O(N2). É possível usar a progressão aritmética para comprovar essa hipótese:
(n − 1) + (n − 2) + ... + 2 + 1 = n(n - 1) / 2 ∈ Θ(n2)
Se revisarmos o algoritmo apresentado, é possível reparar que o Selection Sort tem no seu melhor e pior cenário o tempo de execução de N2, logo, podendo ser classificado como Θ(N2).
Nos próximos posts vamos nos aprofundar um pouco mais nos detalhes dessa análise, e passar por alguns algoritmos úteis e muito comuns na nossa rotina.
Até a próxima!
Referências
- Análise do Selection Sort – Khan Academy
- Justin Abrahms – Big-O is easy to calculate, if you know how
- National Technical University of Athens – A gentle introduction to Algorithm Complexity Analysis
- Perl Monks – Big-O Notation: What’s is it good for?
- Tutorials Point – Data Structures Asymptotic Analysis
- Wikibooks – Data Structures/Asymptotic Notation
- Wikipedia – Algoritmo
5 Comentários
Muito bem explicado!
Show! Parabéns!
Muito bom! Aguardando os próximos.
Parabéns!
Muito obrigado, Danilo e Carlos. Espero que o próximo atenda às expectativas 🙂
Excelente! aborda de forma simples algo tão complexo.
Parabéns de mais pela explicação sucinta! Conseguiu transformar algo que é um bicho de 7 cabeças em algo mais simples de se entender. Sucesso!