Qual é a complexidade do cálculo do coeficiente de correlação de Spearman?

Estive estudando o coeficiente de correlação de Spearman

.$\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$

para duas listas e y 1 , … , y n . Qual é a complexidade do algoritmo?$x_1, \dots, x_n$$y_1, \dots, y_n$

Como o algoritmo deve apenas computar subtrações, é possível ser O ( n ) ?$n$$O(n)$

Você tem que calcular

• duas médias,
• diferenças,$2n$
• três somas com somas - que podem ser calculadas em tempo constante - cada uma e$n$
• uma divisão, uma multiplicação e uma raiz quadrada.

$O(n)$

Em relação ao espaço, você tem várias opções:

• $O(\log M)$$M$$6n$
• $2n+2$$O(n \cdot \log M)$$4n$

O que é preferível depende do seu contexto.

Você deixou de fora um passo importante ... A fórmula que você tem é a correlação de pearson. O que o torna lanceiro é que xey são as fileiras das duas variáveis ​​originais. Essa etapa de classificação deve ser levada em consideração para a complexidade do coeficiente de correlação de spearman. Essencialmente, você deve classificar cada uma das duas variáveis, que dependerão do algoritmo de classificação escolhido, seguido pelo cálculo mencionado acima.