[Cascavel-pm] algoritmo (ou deveria dizer "EP"?)

[Luis Campos de Carvalho]

Luís Fernando wrote:
> Digamos que a diferença entre o que eu desejo e o que o que você citou
> é exatamente a "aleatoriedade".
> 
> Para simplificar:
> Se cabe 10 elementos e eu mando inserir 10 (1..10), é para ficar:
> 1 2 3 4 5 6 7 8 9 10
> 
> Se cabe 10 elementos e eu mando inserir 20 (1..20):
> 1 3 5 7 9 11 13 15 17 19
> 
> Se cabe 10 elementos e eu mando inserir 40 (1..40):
> 1 5 9 13 17 21 25 29 33 37
> 
> Entendeu?
> 

   Hum. Na verdade, você não está sendo claro o suficiente para alguém 
entender.

   Seu algorítmo calcula um slice de árvore binária, não-balanceada, 
destrutivamente, como forma de classificar (ou priorizar) os elementos e 
condensar o espaço utilizado para a amostra de uma maneira racional.

   Eu acredito que seus algorítmos não poderão ter O(1), já que toda 
inserção não-balanceada em árvore binária é maior que isso (D. Knuth, 
"The Art of Computer Programming", v1, se eu me lembro bem).

   Você poderia assumir o custo de construção, e olhar seus dados como 
uma árvore binária não-balanceada, pagando o custo de alocação de 
memória necessário para a construção da estrutura toda. Depois que a 
coleta de informações terminar, você poderia balancear a árvore e 
finalmente escolher o "slice" que mais se adequa ao espaço disponível.

   IMHO, esta solução produzirá resultados mais balanceados, e a 
inferência para a população será aproximadamente normal, com erro 
quadrático...

   Claro, se isso não violar nenhuma regra do Exercício Programa que 
você está tentando resolver... ;-)

   Ah! Alex Falcão, acho que isso é a "utilidade prática" que você está 
procurando para o programa... :-)

   Que tal você postar o problema inteiro para a gente dar uma espiada?

   Pode ser que apareça alguma idéia interessante para você implementar 
esta coisa mais rapidamente... :-) Sinceramente, eu recomendo que você 
vá atrás dos livros do Mestre Knuth, você não vai se arrepender...

   Putamplexos.
-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
   Luis Campos de Carvalho is BSc in Comp Science,
   PerlMonk [SiteDocClan], Cascavel-pm Moderator,
   Unix Sys Admin && Certified Oracle DBA
   http://br.geocities.com/monsieur_champs/
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=