Apa kompleksitas perhitungan koefisien korelasi peringkat Spearman?

Saya telah mempelajari koefisien korelasi peringkat 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}}$ .

untuk dua daftar dan . Apa kompleksitas dari algoritma tersebut?$x_1, \dots, x_n$$y_1, \dots, y_n$

Karena algoritma seharusnya menghitung pengurangan, apakah mungkin menjadi ?$n$$O(n)$

Anda harus menghitung

• dua rata-rata,
• $2n$ perbedaan,
• tiga penjumlahan dengan $n$ penjumlahan - yang dapat dihitung dalam waktu konstan - masing-masing dan
• satu divisi, satu multiplikasi dan satu root kuadrat.

Semua ini dapat dilakukan dalam waktu linier jika kita mengasumsikan operasi aritmatika dasar berjalan dalam waktu konstan, oleh karena itu total waktu dalam tentu saja mungkin. Perhatikan bahwa menghitung root mungkin mengacaukan segalanya.$O(n)$

Mengenai ruang, Anda memiliki beberapa opsi:

• Simpan hanya rata-rata, yaitu dua angka ( dengan jumlah maksimum). Anda harus menghitung ulang semua perbedaan, yaitu melakukan total pengurangan .$O(\log M)$$M$$6n$
• Menyimpan rata-rata dan perbedaannya, yaitu angka ( ). Ini menghemat pengurangan Anda.$2n+2$$O(n \cdot \log M)$$4n$

Yang lebih disukai tergantung pada konteks Anda.

Anda telah meninggalkan langkah penting ... Formula yang Anda miliki adalah untuk korelasi pearson. Apa yang membuatnya spearman adalah bahwa x dan y adalah peringkat untuk dua variabel asli. Langkah peringkat ini harus diperhitungkan untuk kompleksitas koefisien korelasi spearman. Pada dasarnya Anda harus mengurutkan masing-masing dari dua variabel, yang akan tergantung pada algoritma pengurutan yang Anda pilih, diikuti oleh perhitungan yang disebutkan di atas.