Algoritmo é a descrição de passos lógicos e finitos para se resolver algum dado proplema. Essa é a definição mais importante para todo programador, pois é a partir dela que toda a mágica que conhecemos acontece. Como programadores, devemos ser especialistas em desenvolver algoritmos para os mais variados fins que, com o tempo, nos tornamos melhores e mais eficientes no seu desenvolvimento.

Por conta disso, é extremamente eficiente que saibamos quando o algoritmo que desenvolvemos realmente é bom e eficiente, principalmente quando somos iniciantes. Esse processo com o tempo vai se tornando automático e até dispensável, contudo no início é importantíssimo.

Uma coisa que sempre percebi na internet foi a falta de conteúdos mais técnicos tradados de forma simples, por isso nesse texto vou abordar o assunto de complexidade de algoritmos focado em pessoas iniciantes. Vale ressaltar que se você já é um desenvolvedor experiente, fique a vontade para participar no campo de comentários, seja corrigindo algum eventual erro ou complementando o conteúdo.

Todos os algoritmos serão expressos em pseudocódigo

Inspeção de código

Inspeção é apenas um termo técnico para análise do código. Constantemente esse termo será utilizado durante o texto. Por exemplo, no seguinte código:

func soma(n)
    resultado := 0
    para i := 0 até n faça
        resultado := resultado + i
    fim
    
    retorna resultado

Com uma simples inspeção podemos perceber que essa função faz a soma de todos os números naturais até n e que tem um laço de repetição que faz n repetições. Muito simples :)

Análise de comportamento

É a análise feita com a motivação de comparar algoritmos que, em geral, resolvem o mesmo problema. Deve-se determinar uma expressão matemática que represente a quantidade de operações realizadas. Essa expressão é escrita com base na quantidade de dados tratados e de uma ou mais operações de interesse.

Portanto, a análise de comportamento é uma forma de contar a quantidade de operações feita por um algoritmo.

Por exemplo, no exemplo anterior fazemos 1 operação n vezes. Quantas operações esse algoritmo faz no total?

1 operação n vezes, pelo princípio fundamental da contagem:

T(n)=1*n=n

Ou seja, no código acima temos n operações.

Perceba que na verdade, o algoritmo faz 2 operações, 1 de atribuição e outra de soma. Contudo, a operação de interesse nesse caso é apenas a soma, mas e como seria se considerarmos ambas?

T(n)=2*n=2n

Veremos a seguir que isso não faz tanta diferença na hora de analizar algoritmos.

Notação de Somatório

A ferramenta mais importante para fazermos a análise de comportamento é a notação de somatório.

\sum_{i=a}^{b}x

i é a variável de controle do somatório, que inicia com o valor a e vai até b (inclusive), que é o limite superior do somatório. x é a expressão que será somada b - a vezes, podendo ou não depender de i. No caso do exemplo acima:

\sum_{i=1}^{n}1=n

O somatório possui algumas propriedades:

Constante: $\sum_{i=1}^{n}c=cn$
Múltiplo de constante: $\sum_{i=1}^{n}cf(i)=c\sum_{i=0}^{n}f(i)$
Aditividade: $\sum_{i=1}^{n}f(i)+g(i)=\sum_{i=0}^{n}f(i)+\sum_{i=0}^{n}g(i)$
Linearidade: $\sum_{i=1}^{n}af(i)+bg(i)=a\sum_{i=0}^{n}f(i)+b\sum_{i=0}^{n}g(i)$
Soma de limites: $\sum_{i=a}^{b}f(i)+\sum_{i=b}^{c}f(i)=\sum_{i=a}^{c}f(i)$
Monocidade: $\text{se }f(i) \leq g(i) \forall i \to \sum_{i=0}^{n}f(i) \leq \sum_{i=0}^{n}f(i)$

Além disso, existem alguns casos especiais:

$\sum_{i=1}^{n}i=\frac{n(n-1)}{2}$

$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$

$\sum_{i=1}^{n}i^3=\frac{n^2(n+1)^2}{4}$

Outro ponto importante é acerca de laços aninhados:

\sum_{i=1}^{n}\sum_{i=1}^{n}1=\sum_{i=1}^{n}i=\frac{n(n-1)}{2}

Ou seja, primeiro se soluciona o somatório mais interno, multiplicando o resultado para os mais externos, isso para qualquer quantidade de somatórios.

Vamos ver um outro exemplo, agora uma função que soluciona um sistema triangular inferior:

func sistema_inferior(A, b)
    n := tamanho(x)
    x = [ 0 para i = 0 até n ]
    
    para i := 0 até n faça
        s := 0.0
        para j := 0 até i - 1 faça
            s := s + A[i, j] * x [j]
        fim
        
        se A[i, i] != 0.0 então
            x[i] := (b[i] - s) / A[i, i]
        senão
            pare
        fim
    fim
    
    retorne x

Por inspeção, sabemos que existem dois laços de repetição, onde é feita apenas uma operação de multiplicação no laço mais interno (que é a operação que nos interessa, por isso vamos desconsiderar a outra), assim:

T(n)=\sum_{i=1}^{n}\sum_{j=1}^{i-1}1\\ T(n)=\sum_{i=1}^{n}i-1\\ T(n)=\sum_{i=1}^{n}i-\sum_{i=1}^{n}1\\ T(n)=\frac{n(n-1)}{2}-n\\ T(n)=\frac{1}{2}(n^2 - n)

Ou seja, para cada n elementos em x, temos $\frac{1}{2}(n² - n)$ operações de multiplicação.

Comportamento assintótico de funções

Comportamento assintótico é o comportamento de funções conforme o valor de x aumenta. No exemplo anterior, podemos ver uma soma entre duas funções $n^2$ e $n$ , mas como essas duas funções se comportam assintóticamente?

comparação entre o comportamento das funções n^2 e n

Perceba como a função $n^2$ (verde) domina a função $n$ (azul) conforme o valor de n aumenta assintóticamente, isso significa que para falores suficientemente grandes, podemos desprezar o termo $n$ na função (algo que no cálculo chamamos de regra do desprezo), fazendo com que o comportamento assintótico do algoritmo acima seja próximo de $n^2$ , pois as constantes também não fazem diferença em casos de n suficientemente grandes.

Assim, podemos dizer que a complexidade do nosso algoritmo é algo próximo de $n^2$ assintóticamente.

Classes de funções

Quando temos a situação descrita acima dizemos que:

T(n) = \frac{1}{2}(n^2 - n) \in O(n^2)

Isso é, a complexidade do algorítimo pertence a classe $O(n^2). Mas o que isso significa?

A função $n^2$ é a função que representa o comportamento assintótico do algoritmo e $O$ é uma notação utilizada para denotar a complexidade de algoritmos (famoso Big O), mas o que essa notação significa?

Notações de complexidade

Existem basicamente três notações para classes de complexidade $O$ , $\Theta$ e $\Omega$

$O(g(x))$ :
Significa que existe um k qualquer maior que zero, onde
$f(x) \in O(g(x)) \Leftrightarrow 0 \leq f(n) \leq kg(n)$
kg(x) limita superiormente f(x)

$\Theta(g(x))$ :
Significa que existem $k_{1}$ $k_{2}$ quaisquer maiores que zero, onde
$f(x) \in \Theta(g(x)) \Leftrightarrow k_{1}g(x) \leq f(x) \leq k_{2}g(x)$
$k_{1}g(x) limita f(x) inferiormente e$ k_{2}$ limita f(x) superiormente

$\Omega(g(x)$ :
Significa que existe um k qualquer maior que zero, onde
$f(x) \in O(g(x)) \Leftrightarrow 0 \leq kg(n) \leq f(n)$
kg(x) limita inferiormente f(x)

Ou seja, o Big O é mais utilizado justamente por nos garantir que a complexidade do algoritmo em questão é menor do que a sua classe g(x), isso é útil para comparar diferentes algoritmos, contudo em algumas situações ou não é possível expressar a complexidade em termos de Big O ou apenas não é tão vantajoso, para isso também existem Big $\Theta$ e Big $\Omega$ .

Conclusão

Nesse artigo aprendemos sobre como fazer análise de comportamento de algoritmos, tal como prever o seu comportamento assintótico, com o auxílio da notação de somatório. Esse método se mostra muito eficiente para se obter a complexidade de um dado algoritmo iterativo, mas não é tão eficiente para algoritmos recursivos.
Vimos também como podemos classificar a complexidade do algoritmo expressando apenas uma função dominante, utilizando-se das notações de Big O, Big $\Theta$ e Big $\Omega$ .

Obviamente o conteúdo exposto aqui é muito simplista e incompleto, não há como resumir todo o assunto aqui da melhor forma, contudo foi possível expor os principais resultados e conceitos da análise de complexidade de algoritmos.

Muito bom artigo, didático e extremamente descritivo. Parabens!!

Sobre algoritmos recursivos e arquitetura de código:
Os algorítmos recursivos podem ser analisado com uma cadeia a mais de parâmetros não tão matemáticos. Algoritmos recursivos muitas vezes proporcionam uma representação mais clara e concisa do problema, facilitando a compreensão do código. No entanto, em algumas arquiteturas, chamadas recursivas podem introduzir sobrecarga significativa devido à pilha de chamadas, o que pode afetar a eficiência.

Para produzir arquiteturas que suportam otimização de cauda (tail call optimization), a recursão pode ser tão eficiente quanto a iteração em termos de uso de pilha. Isso depende da capacidade do compilador/interpretador em otimizar chamadas recursivas de cauda. Uma chamada de cauda ocorre quando a última operação executada em uma função é uma chamada recursiva. A otimização de cauda é uma forma de otimização de chamadas recursivas que evita o acúmulo desnecessário de frames de pilha.

Contudo, uma boa arquitetura de software deve ser portátil entre diferentes plataformas e arquiteturas, permitindo que o mesmo código seja executado eficientemente em vários ambientes ao desenvolver algoritmos iterativos e recursivos. É essencial considerar a arquitetura subjacente para garantir eficiência, clareza e portabilidade. Adaptar a implementação para tirar vantagem das características específicas da arquitetura pode resultar em um software mais otimizado e responsivo.

Como saber se meu algoritmo é ruim?