Suponiendo que $k$ es fija (como lo hacen las dos conferencias enlazadas), entonces sus elecciones algorítmicas determinarán si su cálculo toma $O(nd+kn)$ en tiempo de ejecución o $O(ndk)$ tiempo de ejecución.
En primer lugar, consideremos un $O(nd+kn)$ algoritmo en tiempo de ejecución:
- Inicializar $selected_i = 0$ para todas las observaciones $i$ en el conjunto de entrenamiento
- Para cada observación del conjunto de entrenamiento $i$ , computa $dist_i$ la distancia entre la nueva observación y la observación del conjunto de entrenamiento $i$
- Para $j=1$ a $k$ : Recorre todas las observaciones del conjunto de entrenamiento, seleccionando el índice $i$ con el más pequeño $dist_i$ y para el que $selected_i=0$ . Seleccione esta observación ajustando $selected_i=1$ .
- Devuelve el $k$ índices seleccionados
Cada cálculo de distancia requiere $O(d)$ tiempo de ejecución, por lo que el segundo paso requiere $O(nd)$ tiempo de ejecución. Para cada iteración en el tercer paso, realizamos $O(n)$ funcionan mediante un bucle a través de las observaciones del conjunto de entrenamiento, por lo que el paso en general requiere $O(nk)$ trabajo. El primer y el cuarto paso sólo requieren $O(n)$ trabajo, por lo que obtenemos un $O(nd+kn)$ tiempo de ejecución.
Ahora, consideremos un $O(ndk)$ algoritmo en tiempo de ejecución:
- Inicializar $selected_i = 0$ para todas las observaciones $i$ en el conjunto de entrenamiento
- Para $j=1$ a $k$ : Recorre todas las observaciones del conjunto de entrenamiento y calcula la distancia $d$ entre la observación del conjunto de entrenamiento seleccionado y la nueva observación. Seleccione el índice $i$ con el más pequeño $d$ valor para el que $selected_i=0$ . Seleccione esta observación ajustando $selected_i=1$ .
- Devuelve el $k$ índices seleccionados
Para cada iteración en el segundo paso, calculamos la distancia entre la nueva observación y cada observación del conjunto de entrenamiento, lo que requiere $O(nd)$ trabajo para una iteración y por lo tanto $O(ndk)$ trabajo en general.
La diferencia entre los dos algoritmos es que el primero precalcula y almacena las distancias (requiriendo $O(n)$ memoria extra), mientras que el segundo no. Sin embargo, dado que ya almacenamos todo el conjunto de entrenamiento, se requiere $O(nd)$ memoria, así como la $selected$ vector, que requiere $O(n)$ el almacenamiento de los dos algoritmos es asintóticamente el mismo. Como resultado, el mejor tiempo de ejecución asintótico para $k > 1$ hace más atractivo el primer algoritmo.
Cabe destacar que es posible obtener un $O(nd)$ tiempo de ejecución mediante una mejora algorítmica:
- Para cada observación del conjunto de entrenamiento $i$ , computa $dist_i$ la distancia entre la nueva observación y la observación del conjunto de entrenamiento $i$
- Ejecutar el algoritmo quickselect para calcular el $k^{th}$ la menor distancia en $O(n)$ tiempo de ejecución
- Devuelve todos los índices no mayores que el calculado $k^{th}$ la menor distancia
Este enfoque aprovecha el hecho de que existen enfoques eficientes para encontrar el $k^{th}$ valor más pequeño de una matriz no ordenada.
