Introdução à análise de algoritmos

A análise de algoritmos é geralmente vista como algo enfadonho e sem utilidade real, até porque as linguagens modernas poupam grande parte do trabalho e trazem bibliotecas que implementam algoritmos de ordenação, busca etc., sem que o programador precise se preocupar com isso. Claro, se quiser ser mais um na multidão, não precisa se preocupar mesmo. Bons programadores pensam um pouquinho diferente, e com sorte o leitor entenderá a importância de estudar análise de algoritmos.

O que é análise de algoritmos?

Trata-se de um estudo fundamental em teoria da computação, que aborda os algoritmos sob 2 aspectos:

• Eficiência: O quão rápido o algoritmo pode ser executado? Isso nos permite verificar qual é o algoritmo mais vantajoso para realizar determinada tarefa. Por exemplo, há inúmeros algoritmos de ordenação, então qual usarei?

• Exatidão: O negócio pode até ser mais rápido que a luz, mas está correto? Na prática, temos inúmeros programas que parecem funcionar muito bem, até o infeliz do usuário entrar com um valor estranho e destruir a lógica do programa — isso no melhor dos casos, quando não forem descobertas falhas de segurança. A análise de algoritmos nos permite ter certeza de que o algoritmo produzirá uma saída adequada a qualquer entrada.

A análise de algoritmos e o desenvolvimento de software

A pergunta aqui não é nem se a análise de algoritmos é importante, mas como. A computação é toda sobre resolver problemas computacionais, problemas estes que geralmente apresentam semelhanças e podem ser reduzidas a um único caso comum, como na matemática. Quer ordenar um conjunto de clientes por nome? Ora, trata-se de um problema de ordenação de vetor, para o qual dispomos de inúmeros algoritmos.

Então ao invés de reinventar a roda, por que não estudar esse único problema, o de ordenação de um vetor, e selecionar a melhor resposta para usar em qualquer programa? Ou seja, podemos dizer que a análise de algoritmos nos ajuda a identificar estruturas comuns em situações diferentes, o que nos permite um estudo generalizado de algoritmos. Aí também se enquadram os paradigmas de projeto e análise, como programação dinâmica e algoritmos gulosos, mas não veremos neste post.

Análise assintótica e análise de casos

Dito isso, precisamos abstrair um pouco e recorrer à matemática. Aguenta aí um pouco que não é nada do outro mundo, e também não é necessário aprofundar tanto assim agora. Considere as funções

f(x) = x²
g(x) = 2x²
h(x) = 20x²
i(x) = 20x² + 20

E imagine o gráfico de cada uma delas. Ou melhor, veja abaixo:

Wolfram Alpha LLC. 2011. Wolfram|Alpha. http://tinyurl.com/4ysjtk2 (4 de outubro, 2011).

Bem, você provavelmente não precisaria do gráfico para "adivinhar" que as funções posteriores teriam valores iniciais maiores do que as primeiras. Mas precisamos de um método de comparar funções que considere a velocidade de crescimento delas. Quando tomamos valores de x suficientemente grandes, vemos que todas as funções acima crescem com a mesma velocidade — dizemos que pertencem à mesma ordem.

Quando fazemos esse tipo de comparação, estamos utilizando a análise assintótica. Para isso dispomos de 3 notações: notação de grande-O, notação de grande-Ômega e notação de grande-Teta. Por quê? Já veremos.

Notação de grande-O

Considere duas funções f e g, um valor n0 e um valor positivo qualquer c. Se f está na ordem O de g, ou seja, f = O(g) (mais rigorosamente, f está contido em O(g)), então

f(n) ≤ c * g(n)

Para todo n ≥ n0. Isso significa que c * g(n) é o limite máximo de f(n), que nunca excederá tal valor. Em termos mais cotidianos, dizemos que estamos diante do pior caso. Trata-se de uma noção importante, pois se conseguirmos garantir um processamento eficiente do pior caso, o processamento de qualquer outro caso também será eficiente. Em uma ordenação de vetor, geralmente o pior caso é quando o vetor está totalmente desordenado (em ordem decrescente ao invés de crescente, por exemplo).

Não precisa se preocupar muito com a matemática aqui. O fundamental é ter a seguinte noção: se uma função é definida na ordem O(n), podemos ter certeza que a função terá uma velocidade de crescimento equivalente à da função g(n) = n, e sempre inferior a h(n) = 2^n, por exemplo. Estamos estabelecendo o limite superior, portanto.

PS: Donald Knuth originalmente queria que o "O" fosse a letra grega ômicron, então esta seria a notação de grande-Ômicron, mas hoje em dia o mais comum é usar a letra latina "O".

Notação de grande-Ômega

Aqui é o contrário. Considerando o mesmo blablablá que disse na seção anterior, se f está na ordem ômega de g, ou f = Ω(g) (entenda-se f está contido em Ω(g)), então

f(n) ≥ c * g(n)

Para todo n ≥ n0. E se a notação de grande-O denota o pior caso, a notação de grande-Ômega lida com o melhor caso. Ou seja, a eficiência do algoritmo atinge seu ponto máximo em c * g(n), com a menor velocidade de crescimento. É o limite inferior.

Notação de grande-Teta

Já lidamos com o pior caso, com o melhor caso... Ora, falta o caso médio. Dessa forma, f está na ordem teta de g, ou f está contido em Θ(g), quando

c * g(n) ≤ f(n) ≤ c' * g(n)

Para valores suficientemente grandes de n e valores positivos c e c' quaisquer. De forma equivalente, se f = O(g) e f = Ω(g), então f = Θ(g). Se ficou perdido com as letras e desigualdades, explico melhor: f não é nem o pior caso nem o melhor caso; é algo entre os dois limites, o caso médio.

Travelling Salesman Problem, por Randall Munroe (CC BY-NC 2.5). Veja o artigo na Wikipédia sobre o problema do caixeiro viajante.

Algoritmo de ordenação - insertion sort

Muito bem, agora vamos ao lado mais prático da coisa. Usaremos o que vimos até aqui para estudar um algoritmo que resolve o problema de ordenação: dada uma sequência de elementos (a1, a2, ..., an), o algoritmo deve retornar uma sequência (a1', a2', ..., an') com os mesmos elementos, de tal forma que a1' ≤ a2' ≤ ... ≤ an'. O insertion sort é um algoritmo prático e eficiente para pequenas sequências.

Descrição do insertion sort

Imagine uma pilha de cartas na mesa e que você pegue uma por uma, de modo que fiquem ordenadas em sua mão. Como o faria? A estratégia mais natural seria selecionar uma carta, comparar com as cartas que já estão na sua mão e posicioná-la adequadamente, correto? Pois bem, essa é a exata mesma estratégia do insertion sort — ordenação por inserção.

Dado um vetor A[0..r], podemos montar um sub-vetor contendo os elementos já em nossas mãos. No início, esse vetor é A'[0], depois A'[0, 1], depois A'[0, 1, 2]... de forma que A' sempre esteja ordenado. Sempre que pegamos um novo elemento de A, precisamos comparar com todos os elementos de A' para posicioná-lo adequadamente. Confira o vídeo abaixo se quiser:

Ok, agora já podemos defini-lo em termos de pseudocódigo, dado um vetor de inteiros A com uma quantidade n de elementos:

Insertion-sort(A, n)


  inteiro x, j, i;

  para j de 2 até n faça
    x ← A[j];
    i ← j - 1;
    enquanto i > 0 e A[i] > x faça
      A[i + 1] ← A[i];
      i ← i - 1;
    A[i + 1] ← x;

O insertion sort está correto?

Para verificar a exatidão do algoritmo, precisamos recorrer a um invariante, isto é, algo que vale no início de cada iteração e se mantém de uma iteração para a outra. No insertion sort, o invariante é este: em cada iteração, o sub-vetor A'[0..j-1] está ordenado. Precisamos demonstrar 3 aspectos básicos sobre este invariante. Se os 3 forem cumpridos, com certeza ele é correto:

• Inicialização: Na primeira iteração, o invariante é verdadeiro? No caso do insertion sort sim, pois quando j = 2, nosso sub-vetor A' consiste de apenas um elemento. E, claro, ele está trivialmente ordenado.

• Manutenção: O invariante se mantém verdadeiro antes da próxima iteração? Informalmente, vemos que o algoritmo vai "empurrando" os elementos do vetor, A[j - 1], A[j - 2]... uma posição à direita, até que seja encontrada a posição adequada para A[j]. Assim, antes da próxima iteração, o sub-vetor A' está definitivamente ordenado.

• Término: Ao final do processamento, o invariante nos garante que o algoritmo é correto? Note que o loop externo termina quando j excede n, ou seja, j = n + 1. O invariante diz que, em cada iteração, o sub-vetor A'[0...j-1] está ordenado. Substituindo j por n + 1, temos o sub-vetor A'[0..n], que não apenas está ordenado como é o vetor original. Ora, isso quer dizer que A está ordenado.

O insertion sort é eficiente?

Chamemos T(n) ao tempo que o algoritmo consome. Vamos assumir que cada operação básica consome 1 unidade de tempo qualquer. Ignorando a declaração das variáveis e considerando o pior caso, isto é, quando o vetor está totalmente desordenado, vamos marcar quantas vezes cada instrução é executada:

Insertion-sort(A, n)


  inteiro x, j, i;

  para j de 2 até n faça       // n vezes
    x ← A[j];                  // n - 1 vezes
    i ← j - 1;                 // n - 1 vezes
    enquanto i > 0 e A[i] > x faça   // 2 + 3 + ... + n vezes
      A[i + 1] ← A[i];               // 2 + 3 + ... + n vezes
      i ← i - 1;                     // 2 + 3 + ... + n vezes
    A[i + 1] ← x;              // n - 1 vezes

Somando tudo, obtemos

T(n) = n + 3(n - 1) + 3[(1 + 2 + ... + n) - 1]
T(n) = 4n - 3 + 3[n(n + 1)/2 - 1]
T(n) = 4n - 3 + 3(n² + n)/2 - 3
T(n) = (3/2)n² + (3/2)n + 4n - 6
T(n) = (3/2)n² + (11/2)n - 6

Pouco importam os coeficientes aqui, pois sabemos que se trata de uma expressão do tipo an² + bn + c. E como tal, ela se encontra na ordem de grande-O de n². Portanto, T(n) = O(n²). Trata-se de um algoritmo que cresce em velocidade polinomial, conforme aumenta a entrada n. Se n dobra, o tempo de execução quadruplica. Se quadruplica, aumenta 16 vezes. Parece ruim? Fica tranquilo, há algoritmos muito piores =D

Todo algoritmo que consome tempo O(n^k) no pior caso, para algum inteiro k, são ditos polinomiais. São polinomiais os algoritmos lineares, O(n), quadráticos, O(n²) e logarítmicos, O(log n). Já os algoritmos exponenciais consomem tempo O(k^n) no pior caso, para algum inteiro k, e crescem com uma velocidade muito maior.

Fontes

Aulas de Análise de Algoritmos
Minicurso de Análise de Algoritmos
Introduction to Algorithms