Lista 1 de Exercı́cios de Avaliação de Desempenho
Bolas e Urnas e Bucket-Sort
Professores: Paulo Aguiar e Daniel S. Menasché
1
Bolas e Urnas
Considere m bolas e n urnas. As bolas são jogadas aleatoriamente nas urnas, sem reposição.
1. qual a probabilidade de a urna 1 conter r bolas?
2. qual a probabilidade de a urna 1 não conter nenhuma bola?
3. (aproximação Poisson) assuma que m r. Em particular m − r ≈ m e m(m −
1) . . . (m − r + 1) ≈ mr . Usando o resultado do item 1, qual a probabilidade da urna 1
conter r bolas?
4. desafio: qual a probabilidade de alguma urna não conter nenhuma bola?
2
Bucket-Sort
Considere uma lista com n = 2m elementos, e assuma que cada elemento seja um número
inteiro escolhido de forma uniforme e aleatória na faixa [0, 2k ), k ≥ m. A complexidade de
pior caso para ordenar uma lista de n números é O(n log n). E a complexidade de tempo
médio? Nesta questão, vamos derivar a complexidade de tempo médio de ordenação, usando
o algoritmo bucket-sort. O bucket-sort é um algoritmo determinı́stico, e a complexidade de
caso médio é calculada considerando-se a média sobre todas as possı́veis entradas.
1
1. considere n urnas. Na primeira etapa do bucket-sort, cada elemento é colocado em
uma urna. Na urna j são colocados os elementos cujos m dı́gitos mais significativos
são iguais a j. Por exemplo, se n = 210 , a urna 3 contém os elementos que começam
por 0000000011. Seja Xj o número de elementos na urna j. Caracterize Xj , ou seja,
calcule P (Xj = r), 0 ≤ r ≤ n.
2. assuma que alocar um elemento a uma urna leve tempo constante O(1). Logo, a
complexidade da primeira fase do algoritmo é O(n). Na segunda fase do algoritmo,
os elementos em cada urna precisam ser ordenados. Ordenar Xj elementos usando
bubble-sort consome tempo O((Xj )2 ) = cXj2 , 1 ≤ j ≤ n, onde c é uma constante.
• Qual a média de cXj2 ? Derive a expressão em função da pmf de Xj .
• Usando a pmf de Xj obtida no item 2.1, quanto tempo leva-se, em média, para
ordenar todos os elementos em uma urna?
3. na segunda etapa, quanto tempo leva-se para ordenar todos os elementos em todas as
urnas?
4. qual a complexidade média do bucket-sort?
2