Até agora nos preocupamos principalmente em fazer os programas funcionarem corretamente. A partir desta aula, começamos a nos preocupar também com o quão eficientes eles são — o que nos leva ao estudo da complexidade de algoritmos, um dos temas centrais do restante da disciplina.

Motivação: por que estudar complexidade?

Uma pergunta natural: como decidir qual algoritmo é melhor? Suponha dois algoritmos que resolvem o mesmo problema. Em um computador, o algoritmo A leva 2 ms e o algoritmo B leva 5 ms. Podemos concluir que A é sempre melhor?

A resposta é não. O tempo medido depende de diversos fatores alheios ao algoritmo em si:

• o computador utilizado;
• o compilador;
• a linguagem de programação;
• o sistema operacional;
• detalhes da implementação.

Além disso, o desempenho pode mudar completamente quando o tamanho da entrada aumenta: um algoritmo mais rápido para poucos dados pode se tornar inviável para milhões de elementos.

Por isso, em vez de medir tempo em milissegundos, estudamos como o número de operações cresce em função do tamanho da entrada.

O que é complexidade?

A complexidade de um algoritmo é uma estimativa dos recursos necessários para executá-lo à medida que o tamanho da entrada aumenta. Os dois recursos mais estudados são:

Nesta disciplina, o foco será principalmente a complexidade de tempo.

O tamanho da entrada

A análise de complexidade é feita em função do tamanho da entrada, normalmente representado por n. O significado de n depende do problema:

Ao longo da disciplina, à medida que estudarmos novas estruturas de dados (listas encadeadas, árvores, grafos, etc.), o significado de n será adaptado para cada uma delas — a ideia geral, porém, é sempre a mesma: n representa a quantidade de dados que o algoritmo precisa processar.

Contando operações

Antes de introduzir a notação assintótica, é útil praticar a estimativa do número de operações executadas por um trecho de código.

Percorrer um vetor

for (i = 0; i < n; i++)
    printf("%d\n", vetor[i]);

O laço executa aproximadamente n iterações.

Percorrer todos os pares de elementos

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        // ...

Agora são aproximadamente n² iterações — para cada uma das n voltas do laço externo, o laço interno executa outras n voltas.

Reduzir um valor pela metade repetidamente

while (n > 1)
    n /= 2;

O número de iterações cresce aproximadamente como log n, já que n é dividido pela metade a cada passo.

O objetivo dessa contagem é entender como o custo cresce quando aumentamos o tamanho da entrada — e não obter um número exato de operações.

Exemplo mais completo: contando as operações de uma função em C

Considere a função abaixo, que processa um vetor de inteiros:

int processarVetor(int vetor[], int n) {
    int soma = 0;                              // operação 1
    int i;
    printf("Processando vetor...\n");            // operação 2
    printf("Tamanho do vetor: %d\n", n);         // operação 3
                                                    // 3 operações fixas, antes do laço

    for (i = 0; i < n; i++) {
        soma += vetor[i];                       // operação
        printf("Elemento %d: %d\n", i, vetor[i]); // operação
        printf("Soma parcial: %d\n", soma);       // operação
    }                                            // 3 operações a cada iteração, repetidas n vezes = 3n

    printf("Soma final: %d\n", soma);             // operação 4
    printf("Media: %.2f\n", (float) soma / n); // operação 5
    printf("Elementos processados: %d\n", n);     // operação 6
    printf("Processamento concluido\n");          // operação 7
                                                    // 7 operações fixas, depois do laço

    return soma;
}

Somando cada parte: 3 operações fixas antes do laço, 3n operações dentro do laço (3 por iteração, repetidas n vezes) e 7 operações fixas depois do laço. O total é 3 + 3n + 7 = 3n + 10.

Notação Big-O

A notação Big-O descreve o crescimento assintótico do custo de um algoritmo, ou seja, como esse custo se comporta quando n tende a ficar arbitrariamente grande. "Assintótico" aqui quer dizer que não estamos interessados no comportamento exato para um n pequeno específico, mas sim na tendência de crescimento à medida que n aumenta cada vez mais.

Por isso, a notação Big-O ignora constantes multiplicativas e termos de menor ordem. Por exemplo, o resultado 3n + 10 que obtivemos para processarVetor é dito O(n): para valores grandes de n, o que domina o crescimento do custo é o termo n, e não a constante 3 nem o +10. Da mesma forma, um algoritmo com n² + 100n operações é O(n²), pois o termo n² cresce muito mais rápido que 100n conforme n aumenta. Comparar dois algoritmos dessa forma — pela sua taxa de crescimento, e não pelo número exato de operações — é o que torna a análise independente de computador, linguagem ou compilador.

As classes de complexidade mais comuns, da mais rápida para a mais lenta, são:

Alguns exemplos, incluindo casos já vistos na disciplina:

Melhor, pior e caso médio

O custo de um algoritmo pode variar dependendo da entrada, e não apenas do seu tamanho. Costumamos analisar três cenários:

Nesta disciplina, normalmente utilizaremos a análise de pior caso, por fornecer um limite superior garantido para o tempo de execução do algoritmo, independentemente da entrada recebida.

Resumo

Exercícios

1. Por que não é confiável comparar dois algoritmos apenas medindo o tempo de execução (em milissegundos) de suas implementações?
2. Explique por que a notação Big-O ignora constantes multiplicativas e termos de menor ordem. Isso significa que essas constantes nunca importam na prática?
3. Um algoritmo executa exatamente 5n² + 20n + 100 operações. Qual é a sua complexidade em notação Big-O? Justifique olhando para o termo dominante.
4. Considerando o vetor turma (visto no laboratório de revisão de linguagem C — Material Extra —, na Aula 1b e na Aula 3), classifique a complexidade, em função de n (o número de alunos), de: (a) acessar turma[3]; (b) imprimir todos os alunos da turma; (c) comparar a média de cada aluno com a de todos os outros alunos da turma.
5. Por que, nesta disciplina, normalmente analisamos o pior caso de um algoritmo, em vez do melhor caso ou do caso médio?
6. Escreva uma função em C, int contarOperacoes(int n), que retorne o número de vezes que uma instrução seria executada por um laço equivalente a for (i = 0; i < n; i++) for (j = 0; j < n; j++) contador++;, sem de fato usar dois laços aninhados — ou seja, calcule o valor diretamente a partir de n. Qual é a complexidade dessa nova função, e por que ela é mais rápida do que a versão com os dois laços, apesar de "contarem a mesma coisa"?
7. Escreva uma função em C, int contarIteracoes(int n), que simule o laço while (n > 1) n /= 2; e retorne quantas iterações ele executou. Teste mentalmente (ou no papel) para n = 16 e confirme que o resultado é compatível com uma complexidade O(log n).

Sugestões de Respostas dos Exercícios

int contarOperacoes(int n) {
    return n * n; // equivalente ao total de "contador++" nos dois laços aninhados
}

int contarIteracoes(int n) {
    int iteracoes = 0;

    while (n > 1) {
        n /= 2;
        iteracoes++;
    }

    return iteracoes;
}