Análisis del algoritmo

Las gráficas presentadas en la sección anterior muestran el comportamiento del algoritmo al variar algunos parámetros, es por eso que se considera necesario analizar cada uno de estos parámetros y la repercusión que tienen sobre el algoritmo. A continuación se en listan estos parámetros y sus efectos de acuerdo a su variación.

• El número de pivotes
  • Si se incrementa el número de pivotes, disminuye el número de cálculos de distancia, al momento de buscar los $K$ vecinos más cercanos
  • Si se incrementa el número de pivotes, aumenta la memoria utilizada en el indexamiento
• La dimensión de los datos
  • Si aumenta la dimensión, aumenta el número de cálculos de distancia, al momento de buscar los $K$ vecinos más cercanos
  • Si aumenta la dimensión, aumenta el tiempo empleado
• El tamaño de la base de datos
  • Si disminuye el tamaño de la base de datos, disminuye el costo del algoritmo, por depender directamente de este valor (si el costo del algoritmo es: , a medida que aumenta $n$ aumenta el costo del algoritmo y viceversa)
• El número de vecinos más cercanos
  • A medida que aumenta $K$, varía insignificativamente los cálculos de distancia a realizar, debido a que la complejidad del algoritmo depende del valor de la , veáse la tabla .

Como una conclusión de este trabajo se puede decir a partir de un análisis empírico, que el algoritmo tiene una complejidad de , donde , la cual depende directamente de la dimensión. Esto se deduce visiblemente de las gráficas presentadas en el capítulo anterior. Para calcular el valor de , se aplicó el método de mínimos cuadrados a la gráfica y se observa que el comportamiento de es el que se presenta en la tabla y la gráfica de estos valores es la .

De la complejidad del algoritmo presentado pueden sacarse algunas conclusiones, entre ellas están, para dimensiones bajas tiende a ser muy pequeña y por lo tanto tiene una complejidad lineal.

Tabla: Valores aproximados para , en diferentes dimensiones

dimensión	valor de (n = 40,000)
6	1.025
8	1.128
10	1.208
12	1.493
14	1.718

Figura: Comportamiento del valor de para diferentes dimensiones