Análise de Complexidade


Introdução

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 em geral é 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 dos primeiros números inteiros, ou seja: .

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:

Tendo estabelecido as regras acima, podemos concluir que o algoritmo_b executa cerca de operações (uma operação para cada elemento no intervalo gerado pela função range(). Matematicamente, dizemos que ele executa operações. Note que usamos o sinal para indicar aproximadamente (ou cerca de). Expressamos o tempo de execução do algoritmo como uma função de , 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 operações. Isso fica mais claro se analisarmos quantas operações são executadas para cada valor de i. Vejamos:

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 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 operações.

Perceba que para chegar no valor acima nós ignoramos as constantes e termos menores que 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 ) 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 operações, podemos ignorar as constantes e termos de menor ordem e dizer que ele executa operações. Da mesma forma, se um algoritmo realiza operações, dizemos simplesmente que ele executa 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 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(10)
print("A soma dos 10 primeiros números inteiros é ", resultado)
A soma dos 10 primeiros números inteiros é  55

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:

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.