Seja portanto, para uma amostra muito curta como , pode ser calculada a partir da localização da estática da ésima ordem das diferenças entre pares: k
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
Assim
Obviamente, para amostras grandes dizendo consistir em 80.000 registros, precisamos de uma memória muito grande.
Existe alguma maneira de calcular no espaço 1D em vez de 2D?
Um link para a resposta ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf, embora eu não possa entendê-lo completamente.
Respostas:
Atualização: O ponto crucial do problema é que, para alcançar a complexidade de tempoO(nlog(n)) , é necessário na ordem do armazenamento O(n) .
Não,O(nlog(n)) é o limite teórico mais baixo para a complexidade de tempo de (consulte (1)) selecionar o elemento kth entre todos os n(n−1)2 possíveis|xi−xj|:1≤i<j≤n .
Você pode obter espaçoO(1) , mas apenas verificando ingenuamente todas as combinações de xi−xj no tempo O(n2) .
A boa notícia é que você pode usar o estimadorτ de escala (consulte (2) e (3) para obter uma versão melhorada e algumas comparações de tempo), implementadas na função
τ é um estimador de escala em duas etapas (ou seja, re-ponderado). Possui 95% de eficiência gaussiana, 50% de ponto de interrupção e complexidade de O(n) tempo e O(1) espaço (além de poder ser facilmente on-line), reduzindo metade dos custos computacionais em uso repetido - embora você terá que cavar no
scaleTau2()
noR
pacoterobustbase
. O estimador univariadoR
código para implementar esta opção, é bastante simples de fazer).Editar Para usar isso
R
(é gratuito e pode ser baixado aqui )fonte
(Resposta muito curta) O texto para comentar diz
aqui está: Existe um artigo sobre um algoritmo online que aparentemente funciona muito bem: Aplicando o Estimator OnlineQn .
EDITAR
(pelo usuário user603). O algoritmo vinculado neste artigo é uma versão da janela em movimento do .Qn
fonte
este é o meu implemento de Qn ...
Eu estava programando isso em C e o resultado é este:
fonte