Byłem studiowania Współczynnik korelacji rang Spearmana
.
dla dwóch list i . Jaka jest złożoność algorytmu?
Skoro algorytm powinien po prostu obliczać odejmowań, to czy można być ?
źródło
Byłem studiowania Współczynnik korelacji rang Spearmana
.
dla dwóch list i . Jaka jest złożoność algorytmu?
Skoro algorytm powinien po prostu obliczać odejmowań, to czy można być ?
Musisz obliczyć
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.
Jeśli chodzi o miejsce, masz kilka opcji:
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.