O custo de um algoritmo

Contar operações

A segunda pergunta

As aulas Projetar laços corretos e Recursão ensinaram a provar que um algoritmo é correto: que termina e que o seu resultado cumpre a pós-condição. Ora, a aula Algoritmos numéricos mostrou dois testes de primalidade igualmente corretos, um com cerca de $n$ divisões e outro com cerca de $\sqrt{n}$, e a aula Recursão, duas maneiras corretas de calcular $F_{30}$, uma com $2\,692\,537$ chamadas e outra com 29 somas. Se isso é assim, a correção não basta para escolher: entre dois algoritmos corretos, um pode responder num instante e o outro não terminar antes que a resposta deixe de importar. A segunda pergunta que se faz a um algoritmo é, portanto, quanto custa.

O custo poderia medir-se com um relógio, e a quarta seção o fará. Mas o tempo de uma execução depende da máquina, do compilador, das suas opções e do que o computador estiver fazendo ao mesmo tempo; dele não se segue nada sobre o algoritmo em outra máquina. O que não depende de nada disso é o número de passos que o algoritmo dá. Daí se segue a primeira decisão desta aula: medir o custo contando, e deixar o relógio para conferir a conta.

O tamanho e a operação dominante

Contar todos os passos (cada soma, cada comparação, cada incremento do índice, cada acesso à memória) seria tedioso e inútil, porque quase todos acompanham um principal em proporção fixa. Escolhe-se, portanto, a operação dominante: a que se executa pelo menos tantas vezes quanto qualquer outra, salvo um fator constante, e que por isso representa todas. Numa soma dos elementos de um vetor é a soma; na busca de um máximo, a comparação; num teste de primalidade, a divisão. O número de vezes que se executa expressa-se em função do tamanho da entrada, que se chama $n$: o número de elementos do vetor, o número que se testa, o número de algarismos.

Um laço simples que percorre um vetor de $n$ elementos e faz com cada um uma quantidade fixa de trabalho executa a sua operação dominante $n$ vezes. O máximo de um vetor não vazio, por outro lado, começa com o primeiro elemento como candidato e compara cada um dos demais: $n - 1$ comparações. A diferença entre $n$ e $n - 1$ é real, mas, como se verá na terceira seção, não muda nada do que importa.

O pior caso

Alguns algoritmos não executam sempre o mesmo número de operações com dados do mesmo tamanho. A busca de um valor num vetor, percorrendo-o até encontrá-lo, faz uma só comparação se o valor está na primeira posição e $n$ se não está. Para falar do seu custo escolhe-se uma das duas situações, e a escolha habitual é o pior caso: o número máximo de operações entre todas as entradas de tamanho $n$. A razão é a mesma pela qual um contrato se escreve para todas as entradas que cumprem a pré-condição: o pior caso é uma garantia, e o melhor caso, uma esperança. De modo que a busca linear custa $n$ comparações no pior caso, e quando esta aula diz “o custo” sem mais, diz o do pior caso.

Laços aninhados

A aula Laços ensinou a contar as iterações de dois laços aninhados. Se o interno faz sempre $m$ iterações para cada uma das $n$ do externo, o corpo interno executa-se $n \cdot m$ vezes. Se o interno depende do externo, soma-se linha por linha. O caso que mais aparece ao trabalhar com coleções é o de todos os pares: comparar cada elemento com cada um dos que o seguem, como quando se busca saber se um vetor tem repetidos.

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} comparações; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10:         45 comparações; n(n - 1)/2 = 45n =    100:       4950 comparações; n(n - 1)/2 = 4950n =   1000:     499500 comparações; n(n - 1)/2 = 499500n =  10000:   49995000 comparações; n(n - 1)/2 = 49995000

O contador ocupa o lugar da comparação que o algoritmo real faria. Na iteração $i$ do externo, o interno vai de $i + 1$ a $n - 1$ e faz $n - 1 - i$ iterações; de modo que o total é $(n - 1) + (n - 2) + \cdots + 1 + 0$, a soma da aula Laços:

A saída confirma a fórmula para cada tamanho. O contador é long long porque, a partir de $n$ de uns sessenta e cinco mil, o número de pares supera o máximo de int (de 32 bits nesta plataforma), e a fórmula multiplica depois de converter pela mesma razão: o contador de um algoritmo quadrático estoura muito antes que os dados.

Observe-se já o que a terceira seção generalizará: ao multiplicar $n$ por 10, as comparações multiplicam-se por cerca de 100. Com dez dados, 45 comparações; com dez mil, quase cinquenta milhões.