Barrapunto

he acabado leyendo el artículo sobre el algoritmo de grover en la wikipedia, interesado en el concepto ese de encontrar una pelota en una de 500.000 cajas mirando solo en 1000 y me he dado cuenta que no voy más allá del gato de schrödinger en lo que a fisica cuantica se refiere.

En realidad la pelota la buscas en 1000.000 cajas.
Si las cajas no estan ordenadas tienes que buscar en todas para encontrar la pelota, como la pelota puede estar en cualquiera de ellas (puedes encontrarla en la primera o puedes encontrarla en el medio o al final) el promedio de busquedas es 500.000 intentos.
Así pues el algoritmo es de orden O(n).

El algoritmo de glover en cambio es O(raiz(n)) porque puede buscar en varias cajas a la vez, por lo que en 1000.000 cajas solo necesita buscar en 1000 y si fuesen 4000.000 cajas solo necesitaria buscar en 2000, porque 2000 es la raiz cuadrada de 4000.000.