Jaka jest złożoność obliczania współczynnika korelacji rang Spearmana?

Byłem studiowania Współczynnik korelacji rang Spearmana

$\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}}$ .

dla dwóch list i . Jaka jest złożoność algorytmu?$x_1, \dots, x_n$$y_1, \dots, y_n$

Skoro algorytm powinien po prostu obliczać odejmowań, to czy można być ?$n$$O(n)$

Musisz obliczyć

• dwie średnie,
• $2n$Różnice 2n ,
• trzy sumy z n sumami $n$- które można obliczyć w stałym czasie - każdy i
• jeden podział, jedno mnożenie i jeden pierwiastek kwadratowy.

Wszystko to można wykonać w czasie liniowym, jeśli założymy, że elementarne operacje arytmetyczne przebiegają w stałym czasie, dlatego całkowity czas w jest z pewnością możliwy. Pamiętaj, że obliczenie katalogu głównego może zepsuć wszystko.$O(n)$

Jeśli chodzi o miejsce, masz kilka opcji:

• Przechowuj tylko średnie, czyli dwie liczby ( z maksymalną liczbą). Musisz ponownie obliczyć wszystkie różnice, czyli wykonać łącznie odejmowań.$O(\log M)$$M$$6n$
• Przechowuj średnią i różnice, czyli liczby ( ). Oszczędza to odejmowanie .$2n+2$$O(n \cdot \log M)$$4n$

To, co jest lepsze, zależy od kontekstu.

Pominąłeś ważny krok ... Masz wzór na korelację Pearsona. Co sprawia, że ​​spearman jest taki, że xiy są szeregami dwóch oryginalnych zmiennych. Ten etap rankingu należy wziąć pod uwagę przy złożoności współczynnika korelacji włóczni. Zasadniczo musisz posortować każdą z dwóch zmiennych, które będą zależeć od wybranego algorytmu sortowania, a następnie wykonać powyższe obliczenia.