m
e
n
com um algoritmo que tem tempo de execução proporcional a
mn
. Lembremos que n
é o número de pessoas e que
executamos cada m
-ésima pessoa ainda viva.
O desafio, valendo meia-dúzia de Toblerones, é encontrar um algoritmo
com tempo de execução proporcional a n log n
(em particular, isto
é independente de m
). Note que, por exemplo, se m
é
algo como raiz quadrada do número de pessoas, este algoritmo é muito mais
rápido que aquele visto em sala, pelo menos para um número grande de
pessoas.
Last modified: Mon Mar 1 02:45:48 EST 1999