[eside-ghost] Quereis currar en google? Haced algoritmos!

[Borja Sotomayor]

Jelou!

> [...un monton de cosas que no entiendo...]

xDDD


> Evidentemente estoy dando palos de ciego, asi que lo que diga 
> igual^H^H^H^H^Hseguramente no tiene sentido...
> Segun la wikipedia, un kd-tree es un caso particular de arboles bsp. 
> Segun tengo entendido, para casos genericos 3d (en vez del caso tipico 
> de mapa de doom "3d-pero-casi-2d"), suele ser mejor usar octrees que 
> bsp; igual eso mejoraría la velocidad?

No conozco los octress, pero en general hay que tener cuidado al 
distinguir entre "complejidad" y "velocidad". Cuando hablamos de 
complejidad, generalmente hablamos de cuanto crece el tiempo de 
ejecución de un algoritmo en función de la cantidad de datos que entran 
al algoritmo.

Por poner el ejemplo clásico de toda la vida, supongamos que estoy 
haciendo algo con una lista de N elementos, y que tardo k segundos (una 
cantidad constante) en procesar cada elemento. Entonces:

    Numero de elementos     Tiempo de ejecución
    -------------------     -------------------
              1                      1*k
              2                      2*k
              3                      3*k
             ...                     ...
              N                      N*k

Mi algoritmo, en este caso, tendría tiempo lineal, porque el tiempo de 
ejecución depende linealmente de N (que es la unica variable; recordemos 
que k es una constante). Y esto lo denotamos como O(N)

Sin embargo, si al procesar cada elemento tengo que realizar N 
operaciones (p.ej, porque tengo un bucle anidado), cada una con k 
instrucciones, entonces tengo lo siguiente:

    Numero de elementos     Tiempo de ejecución
    -------------------     -------------------
              1                      1*N*k
              2                      2*N*k
              3                      3*N*k
             ...                      ...
              N                 N*N*k = (N^2)*k

Esto es tiempo cuadratico, O(N^2). Fijaos como lo que realmente nos 
interesa es cuanto crece el tiempo de ejecución en función de "N", y que 
"k" no resulta muy importante.

Claro, alguien puede encontrar un nuevo algoritmo en el que "k" (el 
numero de operaciones constantes que realizamos en cada iteración) se 
reduce bastante. Por ejemplo, si optimizo mi codigo para reducir "k" 
hasta la mitad, mi programa ejecutará el doble de rápido. Sin embargo, 
la *complejidad* del algoritmo seguirá siendo la misma, y en cuanto N 
empiece a crecer, pues seguiré encontrandome con que un algoritmo 
cuadratico resulta bastante lamentable comparado con uno lineal.

En fin, con todo esto quiero decir que igual podemos encontrarnos con 
otras estructuras de datos que, efectivamente, ejecutan más rapidamente 
porque reducen "k" mucho, pero que mantienen la misma complejidad (y lo 
que les importa en el problema de los globos y las balas es la complejidad)

P.D.- Mirando por Wikipedia y otras webs, parece que los Octrees y los 
Quadtrees, al buscar el punto más cercano a otro dado, tienen una 
complejidad de O(n) (aunque en algunos casos particulares tienen una 
complejidad media de O(log n). Aunque O(n) es una complejidad más que 
aceptable para muchas aplicaciones, es peor que lo que piden en el 
problema (en el que una complejidad de O(log n), en el kd-tree, sería mejor)

Un saludo,
-- 
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Borja Sotomayor, University of Chicago
  Ph.D. Student, Department of Computer Science
  Ryerson 257-C, 1100 East 58th Street, Chicago, IL
GT4 Tutorial: http://gdp.globus.org/gt4-tutorial/
BorjaNet:  http://www.borjanet.com/   borja en borjanet.com
·····························································
          "Dis maschine vill run und run!"
                -- Kurt Gödel (on the Turing Machine)
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::