Análise de Complexidade

Antes de começarmos a discutir complexidade assintótica de algoritmos, é interessante responder a uma pergunta fundamental: O que é um algoritmo? Em Ciência da Computação, um algoritmo é uma sequência de passos para se completar uma tarefa, descritos de forma precisa o bastante para que um computador seja capaz de executá-los.

Outra questão importante é: O que desejamos em um algoritmo? Basicamente, desejamos duas coisas. Primeiro, que ele produza uma solução correta para o problema. Segundo, que ele use os recursos computacionais de forma eficiente. Em poucas palavras, desejamos corretude e eficiência.

Neste capítulo, nos concentraremos em como medir a eficiência de algoritmos. A ferramenta usada para isso é a análise de complexidade assintótica de algoritmos (ou simplesmente análise de complexidade).

Uma dúvida frequente que as pessoas têm sobre análise de complexidade é: Para que serve isso? O objetivo da análise de algoritmos é predizer o comportamento de um dado algoritmo. Quando se trata de análise de complexidade, o objetivo é predizer o tempo de execução do algoritmo ou seu consumo de memória, sem ter que implementá-lo e executá-lo em um computador específico.

Análise de complexidade é uma ferramenta poderosa quando temos dois algoritmos e precisamos decidir qual dos dois é o melhor. Na maioria dos casos, o melhor algoritmo é aquele que executa mais rápido. A análise de complexidade assintótica de um algoritmo nos permite decidir, grosso modo, quão rápido ele é.

Vejamos um exemplo. Gostaríamos de comparar dois algoritmos que calculam a soma $s$ dos $n$ primeiros números inteiros, ou seja: $s = 1 + 2 + 3 + \dots + n - 1 + n$.

Dados os dois algoritmos abaixo para calcular essa soma, pergunta-se: Qual deles é mais rápido?

def algoritmo_a(n):
    s = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            s = s + 1
    return s

resultado = algoritmo_a(10)
print("A soma dos 10 primeiros números inteiros é ", resultado)
A soma dos 10 primeiros números inteiros é  55
def algoritmo_b(n):
    s = 0
    for i in range(1, n + 1):
        s = s + i
    return s

resultado = algoritmo_b(10)
print("A soma dos 10 primeiros números inteiros é ", resultado)
A soma dos 10 primeiros números inteiros é  55

Para responder a pergunta acima, precisamos determinar (cerca de) quantas operações cada um dos algoritmos mostrados executa, e qual o custo computacional dessas operações. Para facilitar os cálculos, convém fazer algumas simplificações:

  • Operações matemáticas (soma, multiplicação, raíz quadrada, etc.) possuem custo computacional constante, ou seja, podemos considerá-las como tendo custo igual a 1.

  • Funções como print() e outras que lidam com entrada/saída de dados possuem custo constante.

Operações como as descritas acima são chamadas de operações primitivas. Elas são operações consideradas como tendo custo computacional desprezível.

O livro "Algorithms Illuminated", do professor Tim Roughgarden, traz uma explicação importante sobre operações primitivas. Intuitivamente, uma operação primitiva é um comando ou sentença que realiza uma tarefa simples (adição, multiplicação, comparação, etc.) em variáveis simples (números ou caracteres, por exemplo). Entretanto, em algumas linguagens de programação, uma única linha de código, que a princípio poderia parecer uma operação primitiva, pode realizar um número elevado de operações. Por exemplo, uma linha de código que soma todos os elementos de um arranjo não é uma operaão primitiva. Essa soma possui, na verdade, complexidade linear no tamanho do arranjo, ou seja, é O(n). É importante ficar atento a esses detalhes ao analisar a complexidade de um algoritmo implementado em uma linguagem de programação.

Tendo estabelecido as regras acima, podemos concluir que o algoritmo_b executa cerca de $n$ operações (uma operação para cada elemento $i$ no intervalo $[1,n]$ gerado pela função range(). Matematicamente, dizemos que ele executa $\sim n$ operações. Note que usamos o sinal $\sim$ para indicar aproximadamente (ou cerca de). Expressamos o tempo de execução do algoritmo como uma função de $n$, o tamanho da entrada, porque desejamos predizer o comportamento do algoritmo à medida em que o tamanho da entrada cresce.

A análise do algoritmo_a é um pouco mais complicada, mas nos permitirá concluir que ele executa $\sim n^2$ operações. Isso fica mais claro se analisarmos quantas operações são executadas para cada valor de i. Vejamos:

Tabela 1. Quantidade de operações
Valor de i Valores de j Número de operações

1

[1, n]

n

2

[2, n]

n - 1

3

[3, n]

n - 2

…​

[…​]

…​

n - 1

[n - 1, n]

1

Se analisarmos atentamente os valores da tabela acima, veremos que são executadas $1 + 2 + 3 + \dots + n - 1 + n$ operações. Pode parecer difícil determinar o resultado dessa soma, mas felizmente existe uma fórmula para calcular o resultado. Essa fórmula nos diz que:

$1 + 2 + 3 + \dots + n - 1 + n = \frac{n \times (n - 1)}{2} = \frac{n^2 - n}{2}$

Se simplificarmos a fórmula acima, veremos que o algoritmo_a executa $\sim n^2$ operações.

Perceba que para chegar no valor acima nós ignoramos as constantes e termos menores que $n^2$ na fórmula. Essa é outra simplificação importante feita quando estamos analisando a complexidade de um algoritmo: não consideramos constantes (o 2 da fórmula, por exemplo) ou termos menores (como o $n - 1$) no cálculo do número de operações.

Essa simplificação só é permitida porque, ao analisar a complexidade assintótica de um algoritmo, estamos preocupados com o tempo de execução desse algoritmo para entradas muito grandes, ou seja, quando o tamanho da entrada tende a infinito. Quando isso acontece, o termo de maior ordem na função de complexidade do algoritmo irá dominar, isto é, os valores dos termos de menor ordem e das constantes serão insignificantes se comparados ao valor do termo de maior ordem.

Assim, se descobrirmos que um dado algoritmo executa $2n^2 + 50n$ operações, podemos ignorar as constantes e termos de menor ordem e dizer que ele executa $\sim n^2$ operações. Da mesma forma, se um algoritmo realiza $100n$ operações, dizemos simplesmente que ele executa $\sim n$ operações.

Agora conseguimos dizer que o algoritmo_a executa mais operações que o algoritmo_b. Portanto, o algoritmo_b é mais rápido, mais eficiente.

Você pode estar se perguntando: "Ora, se temos a fórmula para o cálculo da soma dos $n$ primeiros números inteiros, não podemos simplesmente transformar essa soma em um algoritmo mais eficiente que os dois mostrados anteriormente?" A resposta é: sim, podemos. O algoritmo, que chamaremos de algoritmo_c, possui complexidade constante. Ele pode ser implementado assim:

def algoritmo_c(n):
    return n * (n - 1) // 2

resultado = algoritmo_c(11)
print("A soma dos 10 primeiros números inteiros é ", resultado)
A soma dos 10 primeiros números inteiros é  55

Você deve ter percebido que invocamos a função algoritmo_c() passando o númeor 11 como parâmetro, embora nosso desejo é calcular a soma dos 10 primeiros números inteiros, ou seja, dos números de 1 a 10 (inclusive). Tivemos que passar 11 como parâmetro porque a fórmula, do modo como a usamos, começa a contar os números a partir de zero, totalizando 11 números, portanto. Outra alternativa seria usarmos a fórmula $\frac{n \times (n + 1)}{2}$, passando 10 como parâmetro.

Em suma, quando estiver analisando a complexidade assintótica de um algoritmo, descarte fatores contantes e termos de menor ordem, pois fatores constantes dependem muito do sistema (hardware ou arquitetura) e termos de menor ordem são irrelevantes para entradas grandes.

Tipos de Análise de Complexidade

Esperamos que o exemplo acima tenha ilustrado em que situações é útil fazermos análise de complexidade assintótica de algoritmos.

Quando realizamos análise de complexidade, é possível analisar o cenário de três formas distintas:

  • Melhor caso: O melhor caso da execução de um algoritmo é aquele em que o algoritmo retorna a resposta certa realizando a menor quantidade de trabalho possível. Por exemplo, se estamos procurando por um elemento em uma estrutura de dados e o elemento é o primeiro que encontramos na estrutura, a pesquisa caiu no melhor caso. Em análises de algoritmos, o melhor caso quase nunca é considerado. Os outros dois casos (caso médio e pior caso) fornecem informações mais úteis sobre o desempenho de um dado algoritmo.

  • Caso médio: O caso médio, como o próprio nome sugere, nos diz qual o desempenho do algoritmo na média, ou seja, ele nos diz qual o desempenho do algoritmo para uma entrada típica do algoritmo. O caso médio é útil em análise de algoritmos, mas em alguns casos a análise do caso médio é mais complexa e exige uma matemática mais avançada. Porém, em muitas situações, a complexidade no caso médio é a mesma do pior caso, logo concentraremos nossos esforços nas análises de pior caso.

  • Pior caso: O pior caso de um algoritmo nos informa seu desempenho na pior entrada possível, ou seja, na entrada que faz com que o algoritmo demore a maior quantidade de tempo para retornar a resposta correta. Ele nos fornece uma visão pessimista sobre o desempenho do algoritmo, mas é muito útil porque, grosso modo, a função de complexidade para o pior caso de um algoritmo nos diz que esse algoritmo terá um desempenho pelo menos tão bom quanto o indicado por sua função de complexidade.

Nas análises de complexidade que realizaremos ao longo deste curso, estaremos preocupados com o pior caso dos algoritmos, a menos que mencionemos o contrário.

A análise dos exemplos nesta seção foi útil para entendermos o assunto de modo geral, mas ela foi um tanto quanto trabalhosa. A seguir, aprenderemos ferramentas para simplificar (e muito) essas análises e para nos ajudar a raciocinar em termos de qual algoritmo é melhor para uma determinada tarefa.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo