Análise de Algoritmos | Aulas | Dicionário | Índice

Análise probabilística e algoritmos aleatorizados

Esta página é uma introdução à análise probabilística e aos algoritmos aleatorizados (= randomized). Em geral, a análise probabilística é usada para calcular o consumo médio de tempo de um algoritmo. Mas nesta página, para apresentar os conceitos, usaremos análise probabilística para cálcular o número médio de certas operações durante a execução de um algoritmo muito simples.

O texto desta página é baseado em partes do capítulo 5 de CLRS.

O problema da contratação

Para apresentar as ideias básicas da análise probabilística, usaremos o problema da contratação (= hiring problem) como exemplo. Imagine que preciso contratar um assistente pessoal. O assistente deve ser escolhido em um conjunto de n candidatos obedecendo o seguinte protocolo:

Ao longo de n semanas, entrevisto um candidato por semana. Se o candidato da semana for melhor que meu assistente atual, demito o assistente atual e contrato o candidato que acabei de entrevistar. (No início, não tenho assistente algum; portanto, o primeiro candidato será certamente contratado e ficará comigo por pelo menos uma semana.)

Quantas contratações farei até o fim do processo? Se o primeiro candidato for o melhor de todos, farei uma única contratação. Se os candidatos comparecerem em ordem crescente de qualidade, farei n contratações. Isso me preocupa, pois os trâmites de cada contratação são caros. Há como prever o número médio de contratações? Será que número médio de contratações é n/2? Ou que sabe (n+1)/2?

A próxima seção calcula o número médio de contratações depois de modelar o problema como o problema de encontrar o máximo de um vetor.

Número médio de contratações

Suponha dado um vetor A[1 .. n] cujos elementos são inteiros positivos. Em termos do problema da contratação, A[i] representa a qualidade do candidato i. Segue um algoritmo óbvio para o problema de encontrar um elemento máximo do vetor:

Quantas vezes, em média, o algoritmo atualiza o valor da variável max? Em outras palavras, qual o número médio de execuções da atribuição max := A[i] na linha 4 do algoritmo?

Comecemos com uma observação simples mas fundamental: o número de atualizações da variável max não depende dos valores dos elementos do vetor A mas apenas do índice de seu maior elemento, do índice de seu segundo maior elemento, do índice do terceiro maior elemento, etc.  Assim, por exemplo, o vetor [88 55 99 22] é equivalente ao vetor [3 2 4 1]. Nada perdemos, portanto, ao supor que os elementos do vetor pertencem ao conjunto 1 .. n. Para tornar as coisas mais simples, suporemos também que os elementos do vetor são distintos dois a dois, e portanto que A[1 .. n] é uma permutação de 1 .. n. Com isso, temos o seguinte modelo do

Problema da contratação:  Determinar o número médio de execuções da atribuição max := A[i] no algoritmo Máximo supondo que A[1 .. n] é uma permutação de 1 .. n.

No pior caso, a variável max é atualizado n vezes. No melhor caso, é atualizado só 1 vez. Será que o número médio de atualizações é n/2? Ou talvez (n+1)/2?

Para calcular o número médio, basta dividir por n! a soma dos números de atualizações de max provocados pelas n! permutações de 1 .. n.

Solução do problema

Para resolver o problema da contratação, vamos recorrer à linguagem e aos métodos da Teoria das Probabilidades.

Suponha que A[1 .. n] é uma permutação aleatória uniforme de 1 .. n. Em outras palavras, suponha que cada uma das n! permutações é igualmente provável. Seja X a variável aleatória que dá o número de execuções da atribuição max := A[i]. Estamos interessados no valor médio da variável X, ou seja, na esperança de X, que denotaremos por

E[X] .

Essa esperança é a soma ∑_{0 ≤ k ≤ n} k Pr[X = k], sendo Pr[X = k] a probabilidade de que a atribuição seja executada exatamente k vezes. Para facilitar o cálculo dessa probabilidade, convém introduzir as seguintes variáveis aleatórias indicadoras: para cada k de 1 a n,

A soma  X₁ + ⋯ + X_n  é igual a X. Assim, pela linearidade da esperança, E[X] é a soma dos E[X_k]. Cada E[X_k] é igual à probabilidade de que A[k] seja o elemento máximo de A[1 .. k]. Portanto,

E[X_k]  =  1 / k,

já que todos os elementos do vetor são maiores que o valor inicial da variável max. Segue daí, finalmente, que

ou seja, E[X] é um número harmônico. Assim, E[X] fica entre  ln n  e  1 + ln n.  Como ln n = Θ(lg n), temos

E[X]  =  Θ(lg n).

Portanto, a linha 4 do algoritmo Máximo é executada Θ(lg n) vezes em média. Em termos do problema da contratação, a notícia é muito boa: terei que fazer apenas Θ(lg n) contratações, em média, sendo n o número de candidatos.

Algoritmo aleatorizado

A análise na seção anterior supõe que A[1 .. n] é uma permutação aleatória uniforme de 1 .. n. Para garantir que essa hipótese esteja satisfeita, basta permutar os elementos do vetor antes de invocar o algoritmo. Isso produz uma versão aleatorizada (= randomized) do algoritmo Máximo:

A linha 0 permuta os elementos de A[1 .. n] de modo que cada uma das n! permutações tenha a mesma probabilidade.

Decorre da análise que fizemos na seção anterior que o número esperado de execuções da linha 4 de Máximo-Aleatorizado é

Θ(lg n).

Como o algoritmo é aleatorizado, não dizemos número médio mas número esperado. Não existe pior caso nem melhor caso, pois cada execução do algoritmo trabalha sobre uma permutação diferente (e aleatória) do vetor A[1 .. n].

Permutação aleatória.  Resta entender como implementar o algoritmo auxiliar Permuta. Eis uma solução:

O comando Random (i, n) produz um número no intervalo i .. n com probabilidade uniforme, ou seja, com probabilidade 1 / (n−i+1) para cada número do intervalo. Existem implementações de Random que conseguem uma boa aproximação do igualmente prováveis e consomem uma quantidade de tempo constante, ou seja, independente de i e n.

Para provar a correção do algoritmo, convém usar a seguinte definição. Para qualquer k entre 1 e n, uma k-permutação do vetor A[1 .. n] é o vetor cujos elementos são A[p₁], A[p₂], … , A[p_k], nessa ordem, sendo p₁, p₂, … , p_k uma permutação de um subconjunto de 1 .. n que tem exatamente k elementos.

Para verificar que o algoritmo Permuta produz uma permutação aleatória uniforme de A[1 .. n], é preciso observar o seguinte invariante: no início de cada iteração, o subvetor A[1 .. i−1] tem probabilidade (n − i + 1)! / n! de ser qualquer uma das (i − 1)-permutações do vetor original. Portanto, no início da última iteração (quando i = n+1) o vetor A[1 .. n] tem probabilidade 1/n! de ser qualquer uma das permutações do vetor original.