Soit $Q_n = C_n.\{|X_i-X_j|;i < j\}_{(k)}$ donc pour un échantillon très court comme $\{1,3,6,2,7,5\}$ il peut être calculé en trouvant la statique du $k$ ème des différences par paires:

    7 6 5 3 2 1
1   6 5 4 2 1
2   5 4 3 1
3   4 3 2
5   2 1
6   1
7

h = [n / 2] + 1 = 4

k = h (h-1) / 2 = 8

Ainsi $Q_n=C_n. 2$

De toute évidence, pour les échantillons de grande taille, soit 80 000 enregistrements, nous avons besoin d'une très grande mémoire.

Est-il possible de calculer dans l'espace 1D au lieu de 2D?$Q_n$

Un lien vers la réponse ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf bien que je ne puisse pas le comprendre complètement.

Mise à jour: Le nœud du problème est que pour atteindre la complexité temporelle $O(n\log(n))$ , il faut dans l'ordre de stockage $O(n)$ .

Non, $O(n\log(n))$ est la limite théorique inférieure de la complexité temporelle de (voir (1)) la sélection de l' élément $k^{th}$ parmi tous les $\frac{n(n-1)}{2}$ possible$|x_i - x_j|: 1 \leq i \lt j \leq n$.

Vous pouvez obtenir de l' espace $O(1)$ , mais uniquement en vérifiant naïvement toutes les combinaisons de $x_i-x_j$ dans le temps $O(n^2)$ .

La bonne nouvelle est que vous pouvez utiliser l' estimateur d'échelle $\tau$ (voir (2) et (3) pour une version améliorée et quelques comparaisons temporelles), implémenté dans la fonction scaleTau2()du Rpackage robustbase. L' estimateur univarié $\tau$ est un estimateur d'échelle en deux étapes (c'est-à-dire repondéré). Il a une efficacité gaussienne de 95%, un point de rupture de 50% et la complexité du temps $O(n)$ et de l' espace $O(1)$ (en plus, il peut facilement être mis en ligne, ce qui réduit de moitié les coûts de calcul lors d'une utilisation répétée - bien que vous devra fouiller dans le Rcode pour implémenter cette option, c'est assez simple à faire).

1. La complexité de la sélection et du classement dans X + Y et les matrices à colonnes triées GN Frederickson et DB Johnson, Journal of Computer and System Sciences Volume 24, Numéro 2, avril 1982, Pages 197-208.
2. Yohai, V. et Zamar, R. (1988). Estimations de points de rupture élevées de la régression au moyen de la minimisation d'une échelle efficace. Journal de l'American Statistical Association 83 406–413.
3. Maronna, R. et Zamar, R. (2002). Estimations robustes de l'emplacement et de la dispersion pour les ensembles de données de grande dimension. Technométrie 44 307–317

Modifier Pour utiliser ceci

1. Allumez R(c'est gratuit et peut être téléchargé à partir d' ici )
2. Installez le package en tapant:

install.packages("robustbase")

3. Chargez le package en tapant:

library("robustbase")

4. Chargez votre fichier de données et exécutez la fonction:

mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)

(Very short answer) The text for commenting says

avoid answering questions in comments.

so here it goes: There is a paper about an online algorithm which seemingly runs quite well: Applying the $Q_n$ Estimator Online.

EDIT

(by user user603). The algorithm linked to in this article is a moving window version version of the $Q_n$.

Given a large sample $\{x_i\}_{i=1}^N$ divided into time windows of width $n<N$, $\{x_i\}_{i=t-n+1}^t$ we can apply the $Q_n$ to each time window yielding $N-n+1$ values of the $Q_n$. Denote these values $\{Q_n^i\}_{i=1}^{N-n+1}$

The algorithm cited here allows to obtain $Q_n^i|Q_n^{i-1}$ at an average cost less than the worst case $O(n\log(n))$ needed to compute $Q_n^i$ from scratch.

This algorithm can however not be used to compute the $Q_n$ of the full original sample $\{x_i\}_{i=1}^N$. It also needs to maintain an buffer whose size can be as large as $O(n^2)$ (though it is often much smaller).

this is my implement of Qn...

I was programming this in C and the result is this:

void bubbleSort(double *datos, int N)
{
 for (int j=0; j<N-1 ;j++)     
  for (int i=j+1; i<N; i++)    
   if (datos[i]<datos[j])      
   {
    double tmp=datos[i];
    datos[i]=datos[j];
    datos[j]=tmp;
   }
}

double  fFactorial(long N)    
{
 double factorial=1.0;

 for (long i=1; i<=N; ++i)
  factorial*=(double)i;

 return factorial;  
}

double fQ_n(double *datos, int N)  // Rousseeuw's and Croux (1993) Qn scale estimator
{
 bubbleSort(datos, N);

 int m=(int)((fFactorial((long)N))/(fFactorial(2)*fFactorial((long)N-2)));

 double D[m];
 //double Cn=2.2219;      //not used now :) constant value https://www.itl.nist.gov/div898/software/dataplot/refman2/auxillar/qn_scale.htm

 int k=(int)((fFactorial((long)N/2+1))/(fFactorial(2)*fFactorial((long)N/2+1-2)));

 int y=0;

 for (int i=0; i<N; i++)
  for (int j=N-1; j>=0; j--)
   if (i<j)
   {
    D[y]=abs(datos[i]-datos[j]);
    y++;
   }

 bubbleSort(D, m);

 return D[k-1];
}

int main(int argc, char **argv)    
{
 double datos[6]={1,2,3,5,6,7};
 int N=6;

 // Priting in terminal the final solution
 printf("\n==[Results] ========================================\n\n");

 printf(" Q_n=%0.3f\n",fQ_n(datos,N));

 return 0;
}