Muitas vezes
precisamos otimizar códigos para aumentar a robustez e velocidade de sistemas.
Podemos ter vários fatores influenciando nesse ponto. O que vou explicar nesse
artigo diz respeito a uma das principais formas de análise da lógica envolvida
nos algoritmos, a análise assintótica.

Esse termo é
bem comum quando estudamos estrutura de dados, visto que é um estudo paralelo,
quando não é um pré-requisito do mesmo.

Sabemos que
dentro da área de informática as disciplinas mais complexas e com maior índice
de reprovação nos cursos superiores são algoritmos e estrutura de dados e, na
maioria das vezes, um bom conhecimento de análise assintótica resolveria o
problema ou facilitaria a compreensão de temas mais avançados.

O que vem a ser
análise assintótica?

Fazer uma análise
assintótica é se preocupar com valores grandes de entrada para o processamento
do algoritmo, com o intuito de calcular o tempo total de processamento e
viabilidade para determinados casos. Muitas vezes com isso podemos ser capazes
de saber se é necessária a utilização de outra metodologia ou ferramenta para a
realização de uma tarefa.

Vale lembrar
que, mesmo sendo uma área de extrema importância na informática, não é comum à
maioria dos ‘profissionais’ do mercado atual praticá-la. Alguns dos motivos
para isso são:

• profissionais com boa capacidade desse tipo de análise são caros
  para a maioria das empresas
• gerentes de projeto não vêem o tempo gasto para
  isso como um tempo útil e preferem ver resultados imediatos
• profissionais
  estudam essa disciplina no ensino superior apenas como uma disciplina
  complementar e também preferem matérias mais práticas ou mais fáceis (visto
  que, no geral, matemática é uma disciplina complexa)

Pensar
assintoticamente requer uma visão mais além do projeto, visualizando até onde o
sistema pode chegar. Isso parece óbvio, mas não é bem assim, já que muitas
vezes é difícil de simular valores grandes no ambiente de teste, então os
testes são feitos com limites pequenos. Por outro lado não podemos simplesmente
fazer o contrário, ou seja, criar sistemas com suporte ao dobro do que
realmente precisaria. Tudo é questão de fazer um bom estudo, e caso a caso.

Junto com o
estudo de análise assintótica, temos o conceito de notação assintótica, que é a
representação matemática criada por Paul Bachmann no século XIX. Nela, temos
três notações comuns para classificar as ordens das funções, essas ordens
determinam a equivalência das funções, ou seja podemos ter uma função que seja
to tipo n²,
essa função é equivalente à função 400n². São equivalentes assintoticamente
falando, lembrando que sempre nos preocupamos com valores de entrada grandes
para n. As três principais classificações de ordem são: Ordem O, Ordem Omega e Ordem
Theta.

A explicação
matemática das ordens é bem complexa, existem muitos livros que explicam seus
conceitos, recomendo: The Art of Computer Programming (de Knuth). Mas
resumidamente, para colocarmos o assunto dentro do contexto de sistemas,
podemos dizer que a ordem O (O) analisa o pior caso, ou seja, pega ele analisa o
limite superior de entrada, esse é o mais comum de todos e o mais amplamente
usado e serve para testar o qual o máximo que será utilizado de processamento. A Ordem Omega é o inverso, analisa a entrada mais baixa e serve para testar
o qual o mínimo que sempre será usado de processamento. Por último temos a Ordem
Theta, que é utilizada para testar os valores médios de entrada, ela é
juntamente usada com bases estatísticas de dados e requer melhor conhecimento
das entradas.

Para
exemplificar isso vou fazer uma simulação simples: um algoritmo para ler n
valores inteiros e, dentre eles, escolhe o maior.

programa escolheMaiorDigito:
         declara i, maior, n, valorNumeros[] : inteiros
         ler: n
         para i de 0 a n-1 faça
                     ler valorNumeros[i]
         fim-para
         maior: 0
         para i de 0 a n-1 faça
                     se valorNumeros[i] > maior entao
                                 maior = valorNumeros[i]
                     fim-se
         fim-para
         mostra maior
fim-programa

Nesse algoritmo
acima, poderíamos já ter o vetor de valores, então não contamos o tempo de
entrada. No algoritmo principal (após a leitura), temos um laço de repetição
que vai de 1 a n, invariavelmente, pois para sabermos se tem algum número maior
que o atual a cada iteração precisamos consultar os outros valores, então tanto
no melhor caso, como no pior e também no caso médio, temos sempre um tempo
constante que é o valor de “N”, podemos dizer que esse algoritmo é O(n).

Agora, se
tivéssemos o seguinte problema: pegar o valor do índice 5 (posição 6) do vetor
do código anterior. Que complexidade esse algoritmo tem? Simples!!! Para pegar
o valor do índice 5 basta uma linha de código que é a seguinte:

mostra
valorNumeros[5]

Logo, para
consultar em uma tabela de valores um índice direto, a complexidade do pior
caso é O(1).

Essas duas
ordens e algumas outras mais comuns normalmente são nomeadas. Seguem abaixo as
principais ordens com suas respectivas nomenclaturas.

• O(1) = ordem
  constante
• O(log n)
  = ordem logarítmica
• O(n) =
  ordem linear
• O(n²) =
  ordem quadrática
• O(n³) =
  ordem cúbica
• O(n^c)
  = ordem polinomial (c é um valor constante qualquer)
• O(cⁿ)
  = ordem exponencial (c é um valor constante qualquer)

Assim, os
algoritmos citados acima tem complexidade linear (O(n)), e complexidade
constante (O(1)).

Essa área de
estudo é muito importante e vale a pena um bom estudo sobre o assunto,
inclusive quando precisa-se utilizar um algoritmo pronto para determinadas
situações, podemos analisar a complexidade assintótica consumida pelo mesmo fim de viabilizar ou não o seu uso, possivelmente pode-se substituí-lo por um
solução mais adequada ao momento.