domingo, 25 de julho de 2010

O algoritmo mais lento do oeste

Por que as pessoas aprendem complexidade computacional? Para achar os algoritmos mais rápidos, é claro. Dada uma lista de algoritmos equivalentes, você pode ordená-los pela complexidade, e o primeiro da lista é o mais eficiente.

Uma brincadeira divertida é fazer isso ao contrário: dada uma especificação, qual o algoritmo determinístico mais lento que a resolve? Por exemplo, qual o algoritmo mais lento para decompor um número em fatores primos?


O algoritmo mais rápido que resolve esse problema é o algoritmo de Shor, que roda em O((log n)3) e requer um computador quântico. Meu candidato a algoritmo mais lento é o abaixo, que na falta de nome melhor eu chamei de Fatoração Bozo:

import itertools

def factor(n):
 solutions = []
 for f in itertools.product(range(1,1+n),repeat=n):
   if reduce(lambda x,y: x*y, f) == n:
     solutions.append(filter(lambda x:x>1, list(f)))
 solutions.sort(key=len, reverse=True)
 return solutions[0]

Parece complexo, mas o funcionamento é bem simples. Vamos pensar no nosso objetivo: queremos achar uma lista de fatores primos, que multiplicados resultam no número desejado (vamos chamá-lo de N).

Nós sabemos que os primos dessa lista são menores ou iguais a N, e sabemos também que essa lista nunca vai ter mais que N elementos. A primeira coisa que fazemos no algoritmo é gerar todas as possíveis listas candidatas, que são o produto cartesiano do intervalo de 1 a N com N repetições. Por exemplo, para N=3, teríamos 27 combinações:

111 112 113 121 122 123 131 132 133
211 212 213 221 222 223 231 232 233
311 312 313 321 322 323 331 332 333

Em python o jeito mais fácil de gerar essa lista é usando itertools.product(), que faz o serviço sozinho. Mas, dessas listas, só interessam aquelas cujo produto seja igual a N. Por exemplo, se N=4, então as listas interessantes são:

1114 1122 1141 1212 1221
1411 2112 2121 2211 4111

Python não tem um operador para multiplicação de listas como tem o sum() para adições, mas pra isso que serve o reduce() né. As listas selecionadas até agora estão boas, mas elas têm um monte de elementos 1 que não contribuem em nada. Usando o filter() podemos jogar fora os uns. Para N=4:

4 22 4 22 22 4 22 22 22 4

Várias listas repetidas, mas tudo bem. O truque agora é notar que, de todas essas listas, a fatoração em primos é a lista de comprimento máximo. É fácil provar isso: se a lista máxima tivesse um elemento composto, então você poderia fatorá-lo, e trocar o número composto pela sua fatoração. Logo, você estaria gerando uma lista maior que a lista máxima, o que é uma contradição.

Pedindo para que o Python ordene as listas por tamanho, basta pegar a primeira lista da seqüência e temos então a nossa fatoração!

E qual a complexidade dessa solução? Ela é dominada pelo número de listas que geramos no primeiro passo, então a complexidade da Fatoração Bozo é maior que O(nn). Se você não tem noção de como isso é lento, veja o tempo que esse código leva para fatorar alguns números:

N=6 - 0.2 segundos
N=7 - 2.1 segundos
N=8 - 45.8 segundos
N=9 - 20 minutos

A função cresce tão rapidamente que, para fatorar N=18, você levaria mais tempo que a idade do universo até agora! Como exercício para o leitor, tente calcular quanto tempo levaria para fatorar o RSA-704, que em decimal tem 212 dígitos :)

6 comentários:

  1. Um concorrente duro para o lendário "Random Sort".

    ResponderExcluir
  2. Código em Haskell numa linha só porque não consigo formatar nada aqui nos comentários =/. Note que eu poderia comparar e depois pegar o maior, mas preferi usar maximumBy.

    import Control.Monad (replicateM)
    import Data.Ord (comparing)
    import Data.List (maximumBy)

    factor n = maximumBy (comparing length) . map (filter (> 1)) . filter ((== n) . product) $ replicateM n [1..n]

    ResponderExcluir
  3. Podemos ainda piorar um pouco o seu algoritmo, simplesmente filtrando as tuplas depois de ordená-las. Algo assim: http://pastebin.org/421412.

    Agora nós estamos ordenando uma lista de n^n elementos, então teremos tempo:
    O(n^n*log(n^n)) = O(n^(n+1)*log(n))

    Será que alguém consegue fazer pior? (todos os passos tem que servir para a fatoração, e deve ser determinístico)

    ResponderExcluir
  4. Duh. Li errado a análise de complexidade e sim, falei besteira no meu comentário anterior (e já apaguei).

    BTW, eu tinha mencionado que o "list(f)" no reduce era desnecessário, e acho que é mesmo :)

    ResponderExcluir
  5. @rbp: Não precisa mesmo, é só porque eu queria uma lista no final :)

    ResponderExcluir
  6. Ricardo, sou um grande fã do seu blog e sempreou aki saber sobre as novidades, em geral.

    Hoje, gostaria de saber (se não, te indicar) se vc conhece um blog de algoritmos, que já está alguim tempo nos meus bookmarks. É este aki:

    http://algoritmos.tiagomadeira.net

    Bem, espero ter lhe dado uma boa recomendação.

    Vlw e até a próxima ...

    Adeus ^^ !!!!!!!!!!!!!!!!!

    ResponderExcluir