Complexidade de algoritmos recursivos

5.1 Análise da complexidade de algoritmos recursivos.

Algoritmos recursivos são uma ferramenta poderosa para resolver problemas complexos, permitindo dividi-los em subtarefas mais simples. No entanto, a análise da complexidade dos algoritmos recursivos pode ser mais complicada em comparação com algoritmos iterativos. Principais aspectos a serem considerados na análise de algoritmos recursivos incluem complexidade temporal e espacial.

Essas avaliações mostram quanto tempo e memória são necessários para executar o algoritmo com base no tamanho dos dados de entrada. A análise da complexidade de algoritmos recursivos muitas vezes envolve a construção e resolução de equações recursivas que descrevem o comportamento do algoritmo.

Complexidade temporal de algoritmos recursivos:

A complexidade temporal de algoritmos recursivos é frequentemente analisada usando relações de recorrência, que descrevem o tempo de execução do algoritmo pelo tempo de execução de suas chamadas recursivas.

Equação recursiva:

Equação recursiva — é uma equação que expressa a complexidade temporal do algoritmo através de sua complexidade temporal para tamanhos menores de dados de entrada. Ajuda a descrever os custos temporais da execução de um algoritmo recursivo.

Exemplos:

• T(n) = T(n − 1) + O(1)
• T(n) = 2T(2n) + O(n)

5.2 Exemplos de problemas com algoritmos recursivos.

Exemplo 1: Fatorial de um número

Vamos considerar um algoritmo para calcular o fatorial de um número n:

def factorial(n):
    if n == 0:

        return 1

    else:

        return n * factorial(n - 1)
        

A relação recursiva para este algoritmo pode ser escrita como:

T(n) = T(n − 1) + O(1)

A solução desta equação dá:

T(n) = O(n)

Assim, a complexidade temporal do algoritmo fatorial é O(n).

Exemplo 2: Quicksort

Vamos considerar o algoritmo de quicksort:

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]

    left = [x for x in arr if x < pivot]

    middle = [x for x in arr if x == pivot]

    right = [x for x in arr if x > pivot]

    return quicksort(left) + middle + quicksort(right)
        

A relação recursiva para este algoritmo no caso médio:

• T(n) = 2 * T(n / 2) + O(n)

A solução desta equação usando o método mestre dá

• T(n) = O(n * log(n))

5.3 Complexidade espacial de algoritmos recursivos

A complexidade espacial dos algoritmos recursivos é determinada como a soma da memória usada para armazenar variáveis e a memória usada para a pilha de chamadas. Em algoritmos recursivos profundos, uma quantidade significativa de memória pode ser usada para armazenar o contexto das chamadas.

Exemplo: Fibonacci

Vamos considerar um algoritmo para calcular números de Fibonacci:

def fibonacci(n):
    if n <= 1:

        return n

    else:

        return fibonacci(n - 1) + fibonacci(n - 2)
        

A relação recursiva para a complexidade temporal:

• T(n) = T(n − 1) + T(n − 2) + O(1)

A solução desta equação dá:

• T(n) = O(2n)

A complexidade espacial é determinada pela profundidade máxima das chamadas recursivas, que neste caso é O(n).

5.4 Métodos de análise da complexidade de algoritmos recursivos

Métodos de análise da complexidade de algoritmos recursivos

1. Método da substituição:
• Usado para presumir a forma da solução e prova por indução.
• Exemplo: Substituição para resolver equações recursivas.
2. 2. Método da árvore de recursão:
   • Visualização das chamadas recursivas na forma de uma árvore, onde cada nó representa uma chamada de função.
   • Exemplo: Quicksort com chamadas recursivas.
3. Método mestre:
   • Padrão para análise de equações recursivas do tipo: T(n) = a * T(n / b) + f(n)
   • Exemplo: Quicksort.

A análise da complexidade de algoritmos recursivos requer a consideração tanto da complexidade temporal quanto espacial. Entender as relações de recorrência e aplicar métodos de análise, como substituição, método da árvore de recursão e método mestre, ajuda a avaliar com precisão o desempenho dos algoritmos recursivos.