Ricbit Jam #2 - Resultado

Este Ricbit Jam convergiu bem rápido, logo nos primeiros dias várias pessoas mandaram a melhor resposta. Pelo critério de desempate, ganha quem mandou primeiro. Por uma vantagem de apenas dez minutos, o vencedor foi o Henrique Pereira (@ikkebr), parabéns!

Algumas pessoas mandaram respostas implementando o Quicksort com ZenoReduce, mas esse algoritmo não é bom na máquina de Zeno. As pessoas que conseguiram chegar no O(1) mandaram variações do Bubblesort e do Insertsort. A solução vencedora, com 76 bytes, foi a abaixo:

import zeno;zenosort=lambda x:zeno.zenoreduce(lambda r,e:sorted(r+[e]),x,[])

Não é óbvio que essa solução é O(1), afinal, ela usa o sorted() do python, que sabemos ser O(n log n). O truque é essa complexidade acaba sendo mascarada. A cada iteração ele adiciona um elemento usando o O(n log n), mas o n começa pequeno, e vai crescendo amortizado pela máquina de Zeno. No final, o tempo utilizado pelo algoritmo é o abaixo, para uma lista de tamanho n:

$\displaystyle\sum_{k=1}^n\frac{k\log k}{2^{k-1}}$

Uma condição suficiente para que o algoritmo seja O(1) é que essa série seja convergente. Para verificar a convergência, podemos usar o teste das razões, ou seja, o limite do módulo da razão de dois termos consecutivos tem que ser menor que um.

$\lim_{k\rightarrow\infty}{\left| \frac{a_{k+1}}{a_{k}} \right| }\lt{1}$

$\lim_{k\rightarrow\infty}{\left| \frac{ \frac{(k+1)\log(k+1)}{2^k} }{ \frac{k\log{k}}{2^{k-1}} } \right| }=$ $\lim_{k\rightarrow\infty}{\left| \frac{k+1}{k}.\frac{\log(k+1)}{\log{k}}.\frac{2^{k-1}}{2^k} \right| }$

Como todo mundo é positivo, dá pra tirar o módulo. Também podemos jogar um 2 para fora, e a base do logaritmo cancela:

$\lim_{k\rightarrow\infty}{\left| \frac{k+1}{k}.\frac{\log(k+1)}{\log{k}}.\frac{2^{k-1}}{2^k} \right| }=$ $\frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{k+1}{k}.\frac{\ln(k+1)}{\ln{k}} }$

Esse limite é indeterminado da forma infinito/infinito, então dá pra usar o teorema de L'Hospital, ou seja, o limite da razão é igual ao limite da razão das derivadas:

$\frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{(k+1).\ln(k+1)}{k.\ln{k}} }=$ $\frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{\frac{k+1}{k+1}+1.\ln(k+1)}{\frac{k}{k}+1.\ln{k}} }=$ $\frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{1+\ln(k+1)}{1+\ln{k}} }$

Opa, esse limite também é da forma infinito/infinito, então dá pra usar o L'Hospital de novo:

$\frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{1+\ln(k+1)}{1+\ln{k}} }=$ $\frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{\frac{1}{k+1}}{\frac{1}{k}}}= \frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{k}{k+1}}= \frac{1}{2}\lim_{k\rightarrow\infty}{ \frac{k+1-1}{k+1}}=$ $\frac{1}{2}\lim_{k\rightarrow\infty}{ 1 - \frac{1}{k+1}}= \frac{1}{2}(1-\lim_{k\rightarrow\infty}{ \frac{1}{k+1}})= \frac{1}{2}(1-0)= \frac{1}{2}$

Concluímos que o limite vale meio, logo ele é menor que um, portanto a série é convergente, e por isso o algoritmo é O(1), QED.

Ricbit Jam #2

O objetivo deste Ricbit Jam é escrever a melhor função de ordenação de listas usando ZenoReduce.

A solução precisa ser um arquivo zenosort.py, que contém uma função zenosort(x). A função deve retornar a lista x ordenada.
A lista x pode conter qualquer tipo de objetos comparáveis, como inteiros, strings, etc.
Mande sua solução como um arquivo anexado para ricbitjam@ricbit.com
O ganhador será aquele que mandar o algoritmo com a menor complexidade.
Caso a complexidade empate, ganha quem enviar a menor solução (em número de bytes do arquivo).
Caso o tamanho empate, ganha quem enviar primeiro.
Caso duas pessoas enviem ao mesmo tempo, ganha quem enviar uma foto fantasiado de Chewbacca.
O ganhador irá receber pelo correio um Cubo de Rubik oficial do Google.
Para calcular a complexidade, você pode assumir que a comparação de dois elementos é O(1).
O prazo de envio é até 30 de abril de 2010, às 23:59 na hora de Brasília.

Esse é um exemplo de solução válida:

Solução válida para o Ricbit Jam #2

As soluções serão rodadas da seguinte maneira:

>>> import zeno
>>> import zenosort
>>> zeno.run(lambda:zenosort.zenosort([3,1,4,-2]))
([-2, 1, 3, 4], 0.0, 0.0)

O placar abaixo será atualizado diariamente, conforme as soluções chegarem:

Posição	Nome	Complexidade	Tamanho
1	Henr"Ikke" Pereira	O(1)	76
2	girino	O(1)	76
3	Renato Cunha	O(1)	76
4	Leonardo Fischer	O(1)	150
5	Ricardo Bittencourt	O(N log N)	95
6	Not RMS	O(N log N)	312
7	Raoni Florentino da Silva Teixeira	O(N log N)	382