Quando começamos a construir um programa queremos avaliar eventualmente sua performance, ou seja, dado um determinado algoritmo que recebe uma entrada, como o tempo de processamento varia com o tamanho da entrada $n$? Como é o uso de memória? É possível encontrar relações matemáticas que predigam o comportamento da função com base em $n$?

Podemos automatizar os testes para obter uma amostra dos tempos de execução. Teremos então uma função do tipo $t=f(n)$, ou, mais frequente, $T(n)$, onde, novamente, $n$ é o tamanho da entrada. Queremos descobrir que tipo de curva essa função gera e reduzir a complexidade do nosso algoritmo para que seja mais eficiente. Porém, não podemos esquecer que o tempo vai depender do hardware utilizado.
No caso de uma complexidade linear de tempo, temos a relação entre $t$ e $n$ dada por uma reta. Quando o tempo é constante, $t$ independe de $n$. Também podemos obter polinômios com graus maiores do que 1, ou seja, quadrático, $n^2$, cúbico, $n^3$, etc….

No caso de memória, utilizamos a análise de complexidade espacial para julgar como o uso de espaço varia com $n$. Temos que lidar com o espaço de instruções, a pilha de execução e o espaço das variáveis. Assim como para o tempo, podemos ter uma relação constante, linear, exponencial, etc…

Separamos, com base no número de operações, os casos pior, melhor e médio.
A notação assintótica é a representação matemática da complexidade de um algoritmo. Avaliamos o limite da função quando $n\rightarrow\infty$ ($n$ tende ao infinito), nisso descartamos as constantes multiplicativas e termos inferiores.

Uma cota superior é a complexidade de um algoritmo já conhecido para resolver um problema, por exemplo, em uma multiplicação de matrizes podemos ter um algoritmo $O(n^3)$. Essa cota pode mudar se um novo algoritmo for descoberto: $O(n^{log7}), O(n^{2,376})$, etc…

Quando o problema requer ao menos um certo número de operações, é dito que a complexidade é de cota inferior. Novamente, em matrizes quadradas, somente para ler e multiplicar os elementos podemos ter $O(n^2)$ o que nos leva a escrever que o algoritmo é $\Omega(n^2)$. Se o algoritmo tem a complexidade igual à sua cota inferior, então é dito assintoticamente ótimo.

Limitante Superior

O limitante superior de um algoritmo é uma função que define um teto para o tempo de execução do algoritmo, independentemente dos valores específicos de entrada. Ele descreve o pior caso de desempenho de um algoritmo, fornecendo uma garantia de que o tempo de execução não excederá esse limite. Isso é útil para garantir que, mesmo nas condições mais adversas, o desempenho do algoritmo será aceitável.

Limitante Superior Assintótico

O limitante superior assintótico é uma forma de descrever o comportamento de crescimento do tempo de execução de um algoritmo para entradas suficientemente grandes, ignorando constantes e termos de ordem inferior. É representado pela notação $O$ (Grande O), que caracteriza a complexidade de tempo de um algoritmo em seu comportamento assintótico. Por exemplo, se dizemos que um algoritmo tem uma complexidade de tempo $O(n^2)$, estamos indicando que, para entradas grandes, o tempo de execução crescerá proporcionalmente ao quadrado do tamanho da entrada.

Classe de Complexidade de Tempo

Classes de complexidade de tempo são categorias que agrupam algoritmos com base em sua complexidade de tempo assintótico. Essas classes ajudam a entender rapidamente a eficiência de diferentes algoritmos. Alguns exemplos de classes de complexidade incluem P (Polinomial), NP (Não Polinomial), e EXP (Exponencial).

Complexidade e Modelos

A complexidade de tempo de um algoritmo pode variar dependendo do modelo computacional utilizado. Os modelos de máquina de Turing são amplamente usados para formalizar a noção de computação e complexidade.

• Máquina de Turing de Única Fita: Este é o modelo mais básico, onde a máquina opera com uma única fita infinita como memória. A complexidade de tempo é medida pelo número de movimentos da cabeça de leitura/escrita sobre a fita.

• Máquina de Turing Multifita: Uma extensão do modelo básico que permite múltiplas fitas. Este modelo pode reduzir significativamente a complexidade de tempo de certos algoritmos, pois permite operações paralelas nas fitas.

• Máquina de Turing Não Determinística: Neste modelo, a máquina pode seguir múltiplos caminhos de computação simultaneamente, escolhendo o caminho "correto" de maneira não determinística. Isso é mais uma abstração teórica do que um modelo prático, mas é fundamental para a definição da classe de complexidade NP.

A análise da complexidade de tempo e a compreensão dos diferentes modelos de máquina de Turing são cruciais para a ciência da computação teórica e prática. Eles fornecem as ferramentas necessárias para projetar algoritmos eficientes e entender os limites fundamentais da computação.

O conjunto NL (Logarithmic Space) refere-se à classe de problemas de decisão que podem ser resolvidos em espaço logarítmico por uma máquina de Turing não determinística. Isso significa que a quantidade de memória necessária para resolver o problema cresce de forma logarítmica com o tamanho da entrada, o que é consideravelmente eficiente do ponto de vista do uso de espaço.

Para entender melhor, podemos comparar NL com outras classes de complexidade:

• P: Classe de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística.
• NP: Classe de problemas para os quais uma solução pode ser verificada em tempo polinomial por uma máquina de Turing determinística.
• L (Log Space): Classe de problemas solucionáveis em espaço logarítmico por uma máquina de Turing determinística.
• NL: É uma extensão de L, permitindo não determinismo. Isso significa que a máquina de Turing pode "adivinhar" parte da solução e verificar essa adivinhação em espaço logarítmico.

Exemplos de problemas dentro da classe NL incluem:

1. Problema do caminho em grafos direcionados (ST-CONNECTIVITY): Dado um grafo direcionado e dois vértices específicos, determinar se existe um caminho do primeiro vértice (origem) ao segundo vértice (destino). Este problema é um exemplo clássico de problema NL-completo, o que significa que é um dos problemas mais "difíceis" dentro da classe NL.

2. Problema da acessibilidade em grafos: Uma variação do problema do caminho, que pergunta se um dado nó é acessível a partir de outro em um grafo direcionado. Este problema é também um exemplo típico de problema dentro de NL.

3. Problema da satisfação de fórmulas booleanas restritas (2-SAT): Dada uma fórmula booleana em forma normal conjuntiva onde cada cláusula tem no máximo dois literais, determinar se existe uma atribuição de valores verdade para as variáveis que torna a fórmula verdadeira. Apesar de problemas mais gerais de satisfação de fórmulas booleanas (como 3-SAT) serem NP-completos, o 2-SAT pode ser resolvido em espaço logarítmico.

Esses exemplos mostram a diversidade de problemas que podem ser tratados eficientemente em termos de espaço, destacando a importância da classe NL na teoria da complexidade.

A completude de espaço exponencial (EXPSPACE) refere-se a uma classe de problemas de decisão que são solucionáveis por uma máquina de Turing determinística utilizando uma quantidade de espaço que é exponencial em relação ao tamanho da entrada. A classe EXPSPACE contém problemas para os quais o espaço necessário para encontrar uma solução pode crescer exponencialmente com o aumento do tamanho da entrada, mas ainda assim, é possível resolver tais problemas com essa quantidade de espaço.

Formalmente, um problema está em EXPSPACE se existe uma função exponencial $f(n)=2p(n)$, onde $p(n)$ é um polinômio, tal que o problema pode ser resolvido utilizando $O(2p(n))$ unidades de espaço para uma entrada de tamanho n.

A completude em EXPSPACE (EXPSPACE-completo) refere-se a problemas que são os mais "difíceis" dentro da classe EXPSPACE, no sentido de que qualquer outro problema em EXPSPACE pode ser reduzido a um problema EXPSPACE-completo em espaço polinomial. Isso significa que, se pudermos encontrar uma solução eficiente em termos de espaço para um problema EXPSPACE-completo, então poderíamos resolver todos os problemas em EXPSPACE eficientemente.

Exemplos de problemas EXPSPACE-completos são relativamente raros em comparação com problemas em classes como NP-completos, devido à grande quantidade de espaço requerida para sua solução. No entanto, aqui estão alguns exemplos para ilustrar a ideia:

1. Problema de Correspondência de Post (PCP): Uma versão indecidível do PCP é conhecida por ser EXPSPACE-completa. O problema envolve determinar se uma série de cartões, cada um com uma string de caracteres em cada lado, pode ser disposta em uma sequência tal que as strings no lado esquerdo, quando concatenadas, sejam iguais às strings no lado direito, quando concatenadas.

2. Determinar a igualdade de duas expressões regulares com exponentes: Dadas duas expressões regulares que incluem operações de exponenciação (indicando repetições de uma subexpressão), determinar se elas geram o mesmo conjunto de strings. Este problema é conhecido por ser EXPSPACE-completo devido à complexidade envolvida na manipulação e comparação de tais expressões.

3. Jogos com informação perfeita em espaços de estados exponenciais: Alguns jogos teóricos ou puzzles que têm regras simples, mas um espaço de estados exponencialmente grande, podem levar a problemas EXPSPACE-completos quando o objetivo é determinar a existência de uma estratégia vencedora.

A relevância de problemas EXPSPACE-completos reside principalmente no campo teórico, destacando limites superiores para a complexidade de espaço de algoritmos. Na prática, resolver problemas que requerem espaço exponencial é frequentemente inviável, destacando a importância de identificar e compreender a complexidade inerente aos problemas computacionais.

A notação Big O, escrita $O(n)$, é uma forma de escrever a complexidade do algoritmo para a entrada de tamanho $n$. Podemos analisar a quantidade de operações e laços para compor a equação que descreverá como o tempo varia com a entrada. Por exemplo:

var array = [1,2,3,4,5];
var operacao = 0;
for(var elemento in array)
{
    int contador = 0;
    while(contador < array.length)
    {
        operacao = (elemento + array[contador])/elemento;
        contador++;
    }
}

Nesse caso temos um laço dentro de outro, restrito ao tamanho do vetor de entrada, mas com dois laços aninhados, ou seja, quando tivermos um vetor com $n$ elementos, teremos $n^2$ iterações, cada um com duas operações matemáticas. Para esse caso, escrevemos que $O(n^2)$: o tempo cresce com o quadrado da entrada.

Se tivéssemos um algoritmo de tempo constante, escreveríamos $O(1)$. Analisando do melhor para o pior temos: $O(1), O(log(n)), O(n), O(nlog(n)), O(n^2),O(n^3),O(2^n)$.

Formalmente, $O(n)$, representa um limite superior para $t$ comparando com a taxa de crescimento de $f(n)$.

A notação $\Omega(f(n))$ representa o limite inferior do algoritmo em análise, ou seja, para qualquer entrada de tamanho $n$, o tempo $t$ vai ser maior do que a taxa de crescimento de $f(n).$

Utilizamos $\Theta(f(n))$ para expressar a igualdade do tempo $t$ com a taxa de crescimento da função $f(n)$.

E, finalmente, $o(f(n))$ designa quando o tempo $t$ é estritamente menor do que a taxa de crescimento de $f(n)$.

Sem analisar diretamente o algoritmo, podemos executar experimentos com o código e obter os tempos de execução para determinar a relação entre o tempo $t$ e o tamanho da entrada $n$. Com os pares $(n,t)$ podemos determinar a curva que melhor se adapta aos pontos e isso vai prover a complexidade do algoritmo. O comportamento do algoritmo e a performance podem ser avaliados por esse método, normalmente utilizando estatística, machine learning e/ou otimização.

Quando utilizamos algoritmos recursivos nem sempre podemos usar alguns dos recursos anteriores para avaliar a sua complexidade. Um algoritmo recursivo chama a si mesmo até que uma determinada condição seja verdade, alocando em algumas linguagens, muito mais memória comparativamente que um tipo iterado (com for ou while, por exemplo). A complexidade pode ser analisada através de uma relação de recorrência, uma equação ou inequação que descreva uma função em termos dela mesma, mas com entradas menores em cada passo.
Por exemplo, no cálculo do fatorial podemos escrever: $$ T(n)=T(n-1)+\Theta(1) $$ de forma que o custo do cálculo do fatorial de $n$ é o cálculo do fatorial de $n-1$ mais as outras operações menores.

Uma relação de recorrência $\{a_n\}$ é uma equação que expressa $a_n$ em termos de um mais termos anteriores da sequência:

$$ a_0,a_1,...,a_{n-1} $$

De forma que uma sequência é uma solução para uma relação de recorrência se seus termos satisfazem a relação de recorrência.

Para o problema de calcular os números de Fibonacci, temos a seguinte recorrência:

$$ F(n)=F(n-1)+F(n-2) \\ F(1) = 1 \\ F(0) = 1 $$

Onde a solução é dada por:

$$ f_n=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n $$

De forma geral, recorrências tem a seguinte forma:

$$ T(n)=\alpha T(n-\beta)+f(n), T(\delta)=c $$

ou

$$ T(n)=\alpha T(\frac{n}{\beta})+f(n), T(\delta)=c $$

Onde $T(\delta)=c$ é uma condição inicial do problema.

Algumas formas de resolver relações de recorrência são:

• Equações características
• Substituição para frente (Forward Substitution)
• Substituição para trás (Backward Substitution)
• Árvores de recorrência (Recurrence Trees)
• Sistemas algébricos computacionais (Maple, Mathematica, Wolfram, etc...)

As equações características são equações algébricas que descrevem as relações de recorrência. Elas são obtidas substituindo todas as ocorrências da função recursiva pelo seu índice na sequência. Por exemplo, consideremos a seguinte relação de recorrência para a sequência de Fibonacci: $$ F(n) = F(n-1) + F(n-2) $$

Para obter a equação característica correspondente, substituímos $F(n)$ por $x^n$:

$$ x^n = x^{(n-1)} + x^{(n-2)} $$

Simplificando a equação, chegamos a uma equação de grau 2, que neste caso é $x^2 - x - 1 = 0$. As raízes dessa equação característica nos fornecem informações importantes sobre a solução da relação de recorrência.

A substituição para frente é um método para resolver relações de recorrência usando uma abordagem iterativa. Começamos substituindo os termos iniciais da sequência na relação de recorrência e, em seguida, usamos esses valores para calcular os próximos termos. Esse processo é repetido até que o termo desejado seja alcançado. A substituição para frente é adequada para relações de recorrência com uma pequena quantidade de termos.

A substituição para trás é uma técnica alternativa para resolver relações de recorrência. Nesse método, começamos substituindo o termo desejado (n) na relação de recorrência e, em seguida, usamos essa informação para calcular os termos anteriores até chegarmos aos termos iniciais da sequência. A substituição para trás é especialmente útil quando o termo desejado é um dos primeiros termos da sequência.

As árvores de recorrência são uma representação gráfica das chamadas recursivas e seus respectivos valores em um algoritmo. Cada nó da árvore representa uma chamada recursiva e seus filhos representam as chamadas recursivas subsequentes. As árvores de recorrência nos permitem visualizar a estrutura do algoritmo recursivo e entender melhor como as chamadas recursivas se relacionam entre si.

Os sistemas algébricos computacionais, como Maple, Mathematica e Wolfram, são softwares que fornecem recursos poderosos para resolver equações, realizar manipulações simbólicas e resolver problemas matemáticos complexos, incluindo relações de recorrência. Essas ferramentas são especialmente úteis para simplificar equações características, encontrar soluções fechadas para relações de recorrência e realizar cálculos simbólicos envolvendo essas equações.

Algoritmos recursivos tem suas chamadas armazenadas na stack do sistema operacional e precisam utilizar normalmente mais memória pois as chamadas e variáveis são empilhadas. A complexidade de espaço é sempre maior em comparação a algoritmo iterativos. Além disso, métodos recursivos adicionam grande overhead (processamento adicional) ao sistema e podem multiplicar os problemas de performance dependendo do tamanho da entrada. Outra preocupação é quando o caso base é identificado incorretamente, o que pode levar a laços infinitos e travar a máquina.

Quando uma função recursiva é chamada, uma nova instância da função é criada e memória é alocada para suas variáveis locais, parâmetros e endereço de retorno. A complexidade de espaço dos algoritmos recursivos pode ser influenciada por dois fatores principais: a profundidade da recursão e a quantidade de memória necessária para cada chamada recursiva.

Cada chamada recursiva adiciona uma nova camada à pilha de chamadas, que é uma região de memória usada para acompanhar as chamadas de função e suas respectivas variáveis. A profundidade da recursão é determinada pelo número de chamadas recursivas feitas antes de atingir o caso base. À medida que a recursão avança, a pilha de chamadas cresce e a memória é consumida para armazenar os resultados intermediários e as variáveis locais de cada chamada recursiva.

A complexidade de espaço em algoritmos recursivos pode ser analisada considerando a profundidade máxima da recursão e a memória necessária em cada nível. Vamos utilizar um exemplo de um algoritmo recursivo para calcular o fatorial de um número para ilustrar isso.

    
        def fatorial(n):
        if n == 0:
            return 1
        else:
            return n * fatorial(n-1)
    
    

Nesta função recursiva para calcular o fatorial, cada chamada recursiva adiciona um novo quadro à pilha de chamadas, armazenando o valor atual de $n$ e outras variáveis locais. A profundidade da recursão corresponde ao valor de $n$ quando o caso base é alcançado.

Por exemplo, se chamarmos $fatorial(5)$, a recursão será executada da seguinte maneira:

    
        fatorial(5)
            fatorial(4)
                fatorial(3)
                    fatorial(2)
                        fatorial(1)
                            fatorial(0)
    

Neste caso, a profundidade máxima da recursão é 5, que é o valor de $n$ na chamada inicial. Em cada nível de recursão, uma quantidade constante de memória é necessária para armazenar as variáveis locais, como $n$. Portanto, a complexidade de espaço deste algoritmo recursivo para o fatorial é proporcional à profundidade da recursão.

Em geral, os algoritmos recursivos podem ter uma complexidade de espaço de $O(N)$, onde $N$ é a profundidade máxima da recursão. Isso significa que o espaço necessário aumenta linearmente com a profundidade da recursão. No entanto, alguns algoritmos recursivos podem ter requisitos adicionais de memória, como armazenar resultados intermediários em estruturas de dados, o que pode afetar a complexidade de espaço.

Para melhorar os algoritmos recursivos e iterativos podemos lançar mão do cache, ou seja, armazenar determinados valores em memória para agilizar o processamento. No caso da função de Fibonacci, quando a chamamos com $n=6$, o algoritmo deve executar contas com todos os valores abaixo de 6, ou seja, $n\times(n-1)\times(n-2)\times(n-3)\times...\times1$, de forma que se tivéssemos alguns casos comuns em memória evitaríamos recalcular o que já sabemos. Esse é o processo de memoization.

Outra alternativa é o método "Bottom-up", onde resolvemos alguns subproblemas primeiro e depois juntamos o resultado. Isso pode diminuir em muito a complexidade do algoritmo, por exemplo, de $O(n)$ para $O(1)$.

Referências:

1. Complexidade de algoritmos - Siang Wun Song
2. Análise de Algoritmos Recursivos
3. Recursion - Christopher M. Bourke - Nebraska-Lincoln School Of Computing

< 7 - Probabilidade e Estatística > 9 - Algoritmos e Estruturas de Dados