Executando verificação de segurança...
6
gabrielTapes
6 min de leitura ·

Complexidade de algoritmos recursivos

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)
Algoritmo intercala 
proc intercala(A, B, C):
    a := tamanho(A); b := tamanho(B)
    i := 0; j := 0
    D := copia(C)
    enquanto i + j != a + b faça
        se i == a então
            D[i+j] := A[i]
            i++
        senão se j == b então
            D[i+j] := B[j]
            j++
        senão se A[i] <= B[j] então
            D[i+j] := A[i]
            i++
        senão
            D[i+j] := B[j]
            j++
        fim
   fim
   C := copia(D)

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)

Carregando publicação patrocinada...
3
clacerda

Sendo (os algortimos recursivos) 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

Vamos expandir esse tema, focando na travessia de árvores, especialmente em árvores balanceados, utilizando a biblioteca GNU libavl como referência. Vamos contrastar a 'simplicidade' da recursividade com a complexidade da itereação.

  1. O que é Travessia de Árvore e por que usar Recursividade?
    Travessia de árvore é o processo de visitar todos os nós de uma árvore de maneira sistemática. Isso é frequentemente feito recursivamente. A recursividade é intuitiva aqui, pois cada subárvore de uma árvore binária, é também uma árvore binária.

  2. A Simplicidade da Recursividade em Travessia
    Usando a recursividade, a travessia pode ser realizada com uma clareza impressionante. Por exemplo, em uma traversão in-order, visitamos primeiro a subárvore esquerda, depois o nó atual, e finalmente a subárvore direita. Cada um desses passos pode ser naturalmente 'convertidos' para uma chamada recursiva.

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);
    }
}
  1. Desafios da Implementação Iterativa
    Por outro lado, replicar este processo de maneira iterativa exige uma abordagem mais sofisticada. Sem a pilha de chamadas natural da recursividade, precisamos gerenciar manualmente uma pilha para rastrear os nós a serem visitados. Além disso, o controle de estado para cada nó visitado torna-se um desafio.
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];
    }
}
  1. Por que Considerar Iteração em Vez de Recursão?
    Embora a recursão seja mais direta, a implementação iterativa pode ser preferida em ambientes de produção, especialmente em rucurssões que podem ser longas e que poderiam causar um stackoverflow. Além disso, a recursão implica na cópia dos parâmetros para cada chamada da função o que adiciona custo computacional extra.