Пусть поэтому для очень короткой выборки, такой как ее можно вычислить от нахождения статики го порядка парных разностей:
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
ч = [п / 2] + 1 = 4
к = ч (ч-1) / 2 = 8
Таким образом,
Очевидно, что для больших выборок, состоящих из 80 000 записей, нам нужна очень большая память.
Есть ли способ вычислить в 1D пространстве вместо 2D?
Ссылка на ответ ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf, хотя я не могу полностью понять это.
Ответы:
Обновление: суть проблемы заключается в том, что для достижения временной сложности требуется порядок хранения .O(nlog(n)) O(n)
Нет,O(nlog(n)) - нижняя теоретическая граница для временной сложности (см. (1)) выбора элемента kth среди всех n(n−1)2 возможных.|xi−xj|:1≤i<j≤n
Вы можете получить пространство , но только наивно проверяя все комбинации за время .O(1) xi−xj O(n2)
Хорошей новостью является то, что вы можете использовать оценщик масштаба (см. (2) и (3) для улучшенной версии и некоторых сравнений по времени), реализованный в функции в пакете . Одномерная оценка является двухступенчатой (т.е. повторно взвешенной) оценкой масштаба. Он имеет эффективность Гаусса 95 процентов, точку разбивки 50 процентов и сложность времени и пространства (плюс его легко можно сделать «онлайн», что позволяет сократить половину вычислительных затрат при повторном использовании - хотя вы для реализации этой опции придется копаться в коде, это довольно просто сделать).τ τ O(n) O(1)
scaleTau2()
R
robustbase
R
Изменить Чтобы использовать это
R
(это бесплатно и может быть загружено здесь )источник
(Очень короткий ответ) Текст для комментирования говорит
Итак, вот оно: Есть статья об онлайн-алгоритме, который, похоже, работает достаточно хорошо: Применение Estimator OnlineQn .
РЕДАКТИРОВАТЬ
(пользователем user603). Алгоритм, связанный с этой статьей, представляет собой версию Q n с движущимся окном .Qn
Для большой выборки разделенной на временные окна шириной n < N , { x i } t i = t - n + 1, мы можем применить Q n к каждому временному окну, получая N - n + 1 значения Q н . Обозначим эти значения { Q i n } N - n + 1 i ={xi}Ni=1 n<N {xi}ti=t−n+1 Qn N−n+1 Qn {Qin}N−n+1i=1
Приведенный здесь алгоритм позволяет получить при средней стоимости меньше, чем наихудший O ( n log ( n ) ), необходимый для вычисления Q i n с нуля.Qin|Qi−1n O(nlog(n)) Qin
Однако этот алгоритм не может использоваться для вычисления полной исходной выборки { x i } N i = 1 . Также необходимо поддерживать буфер, размер которого может достигать O ( n 2 ) (хотя он часто намного меньше).Qn {xi}Ni=1 O(n2)
источник
это мой инструмент Qn ...
Я программировал это на C, и результат таков:
источник