Esse post é uma continuação do meu último post - Como saber se meu algoritmo é ruim?

No último post aprendemos (ou relembramos) o assunto de analise de complexidade de algoritmos, utilizando-se de inspeção de código e da notação de somatórios. Contudo, como também já vimos no último post, não podemos utilizar a notação de somatório para calcular a complexidade de algoritmos recursivos, então nesse post veremos como fazer isso.

O que é um algoritmo recursivo?

Considere o seguinte algoritmo:

1. proc T(n):
2.     se n < 1 então
3.         pare
4.     fim
5.     executa f(n) operações
6.     chama a vezes T(n / b)

Em termos mais simples, algoritmo recursivo é aquele algoritmo que chama a ele mesmo em algum momento da execução.

Geralmente esses algoritmos são utilizados para expressar uma forma de divisão e conquista, sendo normalmente mais simples de se entender que algoritmos iterativos. Isso não significa que são melhores, pois na maioria das vezes eles são piores que algoritmos iterativos, mas em alguns casos eles tem as suas vantagens. Eles tem a seguinte estrutura:

• Caso Base: É o caso mais básico em que o algoritmo pode ser executado, é nessa região do código que temos a condição de parada do algoritmo. No exemplo acima o caso base se encontra nas linhas 2 e 3, onde quando n < 1 o algoritmo para. Nessa parte podemos também realizar operações, a única regra na verdade é que exista uma condição de parada nessa parte do código, além de que um algoritmo recursivo pode ter mais de um caso base, embora não seja usual.

• Processamento local: São as operações realizadas dentro do algoritmo. No nosso exemplo se encontra na linha 5. O processamento local pode também estar no caso base, dependendo do algoritmo. É essa parte do algoritmo que efetivamente resolve o problema.

• Chamadas recursivas: É o local onde o algoritmo chama a si mesmo a vezes, dividindo o problema em um fator b, como podemos ver na linha 6 do nosso exemplo.

Podemos ver as chamadas recursivas como uma fase de divisão e o processamento local como a fase de conquista que levam até um caso base, quando o problema se torna mais simples. Perceba assim, que um algoritmo recursivo que não reduz o problema a cada chamada recursiva não faz muito sentido (como por exemplo o cálculo de fibonacci recursivo).

Para entendermos isso, considere o seguinte algoritmo de ordenamento, conhecido como merge sort:

1. proc merge_sort(A):
2.     n := tamanho(A)
3.     se n == 2 então
4.         se A[1] > A[2] então
5.             A[1] <-> A[2]
6.         fim
7.     senão se n > 2 então
8.         m = n // 2
9.         merge_sort(A[1:m])
10.        merge_sort(A[m+1, n])
11.        
12.        intercala(A[1:m], A[m+1:n], A)

Nesse algoritmo, temos 3 casos base:

• n = 0: não faz nada
• n = 1: não faz nada
• n = 2: executa a linha 3 até a linha 6

Os dois primeiros casos são implicitos e servem apenas como condição de parada, já o terceiro caso executa também algum processamento interno, onde caso A[1] seja maior que A[2] então é feita uma troca de valor entre as duas variáveis (são sempre três operações de atribuição).

Desconsiderando o processamento interno feito no caso base, o único processamento interno é o de intercala (que podemos facilmente perceber que a sua complexidade é O(n)) e temos 2 chamadas recursivas, dividindo o problema pela metade.

Fórmula de recorrência de algoritmos recursivos

A quantidade total de operações realizadas por um algoritmo recursivo é dada pela seguinte equação:

$$ T(n) = aT(\frac{n}{b}) + f(n), a \geq 1, b \gt 1 $$

• a é o número de chamadas recursivas feitas pelo algoritmo
• b é o fator de redução a cada chamada recursiva
• f(n) é a complexidade do procedimento interno do algoritmo

Por exemplo, para o merge_sort:

• Temos 2 chamadas recursivas: a = 2
• A cada instância recursiva dividimos o arranjo por 2: b = 2
• intercala tem complexidade O(n): f(n) = n

Assim, a equação de recorrência do algoritmo merge sort:

** T(n) = 2T(\frac{n}{2} + n **

Calculando a complexidade do algoritmo merge sort (com a equação de recorrência)

Podemos calcular a complexidade diretamente a partir das equações de recorrência, vamos fazer isso para o algoritmo merge sort:

$T(1) = 1$

$T(2) = 2T(1) + 2 = 2 \cdot 1 + 2 \cdot 1 = 4$ $T(4) = 2T(2) + 4 = 4 \cdot 1 + 4 \cdot 2 = 12$

$T(16) = 2T(2(2(2T(1) + 2) + 4) + 8) + 16$ $T(16) = 2T(2(4T(1) + 4 + 4) + 8) + 16)$ $T(16) = 2T(8T(1) + 8 + 8 + 8) + 16$ $T(16) = 16T(1) + 16 + 16 + 16 + 16$ $T(16) = 16 \cdot 1 + 16 \cdot 4 = 80$

Perceba que $T(16) = 16 + 16 \cdot 4$, generalizando para n e algum k:

$$ T(n) = n + n \cdot k $$

Estratégicamente tomando $n = 2^k$ assim teremos $k = \log_{2}{n}$, portanto: $$ T(n) = n \log_{2}{n} + n \in \Theta(n \log_{2}{n}) $$

E assim temos que a complexidade do algorítmo merge sort é O(nlog n)

Dessa forma sempre conseguimos calcular, mas é um processo trabalhoso. Felizmente temos um teorema que nos auxilia na maioria dos casos, tornando tudo mais simples.

Teorema Master

Esse teorema é divididos em três casos, onde podemos obter diretamente a complexidade do algoritmo que estamos analisando. Recapitulando a fórmula de recorrência: $$ T(n) = aT(\frac{n}{b}) + f(n), a \geq 1, b \gt 1 $$

• Caso 1 Se $f(n) \in O(n^c)$ e $c \lt \log_{b}{a}$ então $T(n) \in \Theta(n^{\log_{b}{a}})$

• Caso 2 Se $f(n) \in \Theta(n^c (log_{2}{n})^k), k \geq 0$ e $c = \log_{b}{a}$ então $T(n) \in \Theta(n^c (log_{2}{n})^{k+1})$

• caso 3 Se $f(n) \in \Omega(n^c)$ e $c \gt log_{b}{a}$ e $af(\frac{n}{b}) \leq kf(n), k \lt 1$ então $T(n) \in \Theta(f(n))$

Calculando a complexidade do algoritmo merge sort (com o teorema master)

Lembrando, no caso desse algoritmo temos a seguinte equação de recorrência: $$ T(n) = aT(\frac{n}{2}) + n $$

Assim, $a = 2$, $b = 2$, $f(n) \in O(n)$ e, portanto $c = 1$. Veja que esse caso se encaixa no caso 2 do Teorema Master, pois $f(n) \in O(n) = O(n^c (\log_{2}{n}) ^ k$, com $c = 1$ e $k = 0$.

Portanto, de acordo com o teorema: $$ T(n) \in \Theta(n^c (\log_{2}{n}^{k+1}) = O(n \log_{2}{n}) $$

Calculando a complexidade do algoritmo quicksort

Como último exemplo iremos calcular a complexidade de outro algoritmo de busca, o quicksort. Considere a seguinte implementação:

1. proc quicksort(A):
2.     n := tamanho(A)
3.     se n == 2 então
4.         se A[1] > A[2]
5.             A[1] <-> A[2]
6.         fim
7.     senão se n > 2 então
8.         x = A[n // 2]
9.         i = 0; j = n - 1
10.        
11.        enquanto i <= j faça
12.            enquanto A[i] < x faça
13.                i++
14.            fim
15.            enquanto A[j] > x faça
16.                j--
17.            fim
18.            
19.            se i <= j então
20.                A[i] <-> A[j]
21.                i++; j--
22.            fim
23.        fim
24.        
25.        se j > 0 então
26.            quicksort(A[1:j])
27.        fim
28.        se i < n faça
29.            quicksort(A[i:n])
30.        fim
31    fim 

Perceba que temos 3 casos base:

• n = 0: não faz nada
• n = 1: não faz nada
• n = 2: executa as linhas 4 a 6

O processamento interno está nas linhas 8 a 23 e as chamadas recursivas nas linhas 25 a 30.

Vamos calcular a complexidade desse algoritmo em 2 casos:

• melhor caso: todos os dados já estão ordenados
• pior caso: todos os dados estão ordenados na ordem inversa

A fim de não me alongar tanto no artigo, considere que a complexidade do processamento interno do algoritmo como:

$$ T(n) \in O(n) \text{ no melhor caso} \ T(n) \in O(n^2) \text{ no pior caso} $$

Assim:

Melhor caso

$T(n) = 2T(\frac{n}{2} + n$, que é exatamente a mesma equação de recorrência do merge sort, que já calculamos acima, portanto: $$ T(n) \in \Theta(n \log_{2}{n}) $$

Pior caso

$T(n) = 2T(\frac{n}{2}) + n^2$, onde $a = 2$, $b = 2$, $c = 3 \gt \log_{b}{a}$

Como $c \gt \log_{b}{a}$ podemos utilizar o terceiro caso do teorema master, mas antes precisamos satisfazer mais uma condição: $af(\frac{n}{b} \leq kf(n), k \lt 1$

Assim:

$af(\frac{n}{b}) = 2(\frac{n}{2})^2 = 2 \cdot \frac{n^2}{4} = \frac{1}{2}n^2$

Veja que:

$\frac{1}{2}n^2 \leq kn^2, \forall k \lt \frac{1}{2}$

Portanto, podemos aplicar o Caso 3 do Teorema Master: $$ T(n) \in \Theta(f(n)) = O(n^2) $$

Ou seja, no pior caso, a complexidade do algoritmo quicksort é $O(n^2)$

static void 
traverse_recursive (struct bst_node *node, bst_item_func *action, void *param) 
{
  if (node != NULL) 
    {
      traverse_recursive (node->bst_link[0], action, param);
      action (node->bst_data, param);
      traverse_recursive (node->bst_link[1], action, param);
    }
}

static void 
traverse_iterative (struct bst_node *node, bst_item_func *action, void *param) 
{
  struct bst_node *stack[BST_MAX_HEIGHT];
  size_t height = 0;

  for (;;) 
    {
      while (node != NULL) 
        {
          if (height >= BST_MAX_HEIGHT) 
            {
              fprintf (stderr, "tree too deep\n");
              exit (EXIT_FAILURE);
            }
          stack[height++] = node;
          node = node->bst_link[0];
        }

      if (height == 0)
        break;

      node = stack[--height];
      action (node->bst_data, param);
      node = node->bst_link[1];
    }
}