He estado estudiando el coeficiente de correlación de rango de Spearman
.
para dos listas e y 1 , ... , y n . ¿Cuál es la complejidad del algoritmo?
Dado que el algoritmo solo debe calcular sustracciones, ¿es posible ser O ( n ) ?
fuente
He estado estudiando el coeficiente de correlación de rango de Spearman
.
para dos listas e y 1 , ... , y n . ¿Cuál es la complejidad del algoritmo?
Dado que el algoritmo solo debe calcular sustracciones, ¿es posible ser O ( n ) ?
Tienes que calcular
En cuanto al espacio, tienes varias opciones:
Lo que es preferible depende de su contexto.
Has omitido un paso importante ... La fórmula que tienes es para la correlación de Pearson. Lo que lo convierte en lancero es que x e y son los rangos de las dos variables originales. Este paso de clasificación debe tenerse en cuenta para la complejidad del coeficiente de correlación de Spearman. Esencialmente, debe ordenar cada una de las dos variables, que dependerán de su algoritmo de clasificación elegido, seguido del cálculo mencionado anteriormente.