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

10

Byłem studiowania Współczynnik korelacji rang Spearmana

ρ=i(xix¯)(yiy¯)i(xix¯)2i(yiy¯)2 .

dla dwóch list i . Jaka jest złożoność algorytmu?x1,,xny1,,yn

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

DavideChicco.it
źródło

Odpowiedzi:

8

Musisz obliczyć

  • dwie średnie,
  • 2nRóż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(logM)M6n
  • Przechowuj średnią i różnice, czyli liczby ( ). Oszczędza to odejmowanie .2n+2O(nlogM)4n

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

Raphael
źródło
6

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.

Derek McCrae Norton
źródło