Wie komplex ist die Berechnung des Rangkorrelationskoeffizienten nach Spearman?

Ich habe den Rangkorrelationskoeffizienten des Spearman untersucht

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

für zwei Listen und . Was ist die Komplexität des Algorithmus?y 1 , … , y $x_1, \dots, x_n$$y_1, \dots, y_n$

Ist es möglich, zu sein, da der Algorithmus nur Subtraktionen berechnen sollte ?O ( n $n$$O(n)$

Du musst rechnen

• zwei Durchschnittswerte,
• $2n$ Unterschiede,
• drei Summen mit Summanden - die in konstanter Zeit berechnet werden können - jeweils und$n$
• eine Division, eine Multiplikation und eine Quadratwurzel.

All dies kann in linearer Zeit erfolgen, wenn wir annehmen, dass elementare arithmetische Operationen in konstanter Zeit ablaufen, daher ist die Gesamtzeit in sicherlich möglich. Beachten Sie, dass die Berechnung der Wurzel möglicherweise Fehler verursacht.$O(n)$

In Bezug auf den Platz haben Sie mehrere Möglichkeiten:

• Speichern Sie nur die Durchschnittswerte, dh zwei Zahlen ( mit die maximale Zahl). Sie müssen alle Differenzen neu berechnen, dh insgesamt Subtraktionen durchführen.M 6 $O(\log M)$$M$$6n$
• Speichern Sie den Durchschnitt und die Unterschiede, dh Zahlen ( ). Dies erspart Ihnen Subtraktionen.O ( n ≤ log M ) 4 $2n+2$$O(n \cdot \log M)$$4n$

Was vorzuziehen ist, hängt von Ihrem Kontext ab.

Sie haben einen wichtigen Schritt ausgelassen ... Die Formel, die Sie haben, ist für die Pearson-Korrelation. Was es zu Spearman macht, ist, dass x und y die Ränge für die beiden ursprünglichen Variablen sind. Dieser Rangschritt muss für die Komplexität des Spearman-Korrelationskoeffizienten berücksichtigt werden. Im Wesentlichen müssen Sie jede der beiden Variablen sortieren, was von Ihrem gewählten Sortieralgorithmus abhängt, gefolgt von der oben genannten Berechnung.