Un algoritmo de ordenación de complejidad computacional no exponencial
Nuestro universo es analógico. Los ordenadores digitales discretizan (limitan) el tiempo y la información a una serie de valores predeterminados. Sin embargo, los computadores digitales son también máquinas analógicas. Su peculiaridad consiste en que interpretamos su comportamiento de forma digital.
Esto ocurre hasta llegar al nivel cuántico, donde espacio (posición), tiempo (momento) y materia / energía / información podrían ser fenómenos discretos / digitales.
En definitiva, tenemos:
- Máquinas Analógicas: Utilizan variables físicas como voltaje, longitud o posición para representar datos con tanta precisión como permita el dispositivo físico. Ejemplos: reglas de cálculo, termómetros de mercurio, termostatos.
- Máquinas Digitales: son máquinas analógicas cuyo comportamiento lo interpretamos de forma digital, discreta. Representan datos en forma de números discretos, de manera que cada variable solo puede tomar un valor de un conjunto predefinido y limitado de valores posibles.
Se nos puede olvidar que lo digital no es lo único que existe. ¿Cómo ordenar una serie de números con un computador analógico?
Resulta que existe un algoritmo de clasificación analógico con complejidad computacional lineal.
El algoritmo es el siguiente: basta con cortar palitos de longitud proporcional a cada número que queremos ordenar. Después los colocamos en forma de haz vertical. Damos con ellos un buen golpe en la mesa. Bajamos la mano y el primero que sobresale será el mayor. Lo retiramos y así sucesivamente.
¿Por que funciona este algoritmo? Porque usa propiedades del mundo físico que los computadores digitales ignoran.
***
Tuvimos esta fascinante conversación en el Immune Technology Institute.
1 Comment