|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 12 Jul 2003 13:21:00
To : Sergey Subbotin
Subject : Re: 90%
--------------------------------------------------------------------------------
Sat Jul 12 2003 00:06, Sergey Subbotin wrote to Evgenij Masherov:
SK>>> Есть выбоpка из N pезyльтатов экспеpимента, значения измеpяемой
SK>>> величины лежат в диапазоне [a,b]. Распpеделение неизвестно. Тpебyется
SK>>> найти отpезок [a1,b1] минимальной длины, такой, чтобы в него попадал
SK>>> заданный пpоцент pезyльтатов, напpимеp 90%.
EM>> 1. Упорядочиваем отсчеты по возрастанию (впрочем, можно и по убыванию.).
SS> [skip]
SS> Мне думается, прежде надо определиться, являются ли a1 и b1 какими-либо
SS> из _результатов эксперимента_, или же просто принадлежат диапазону [a,b].
SS> Кроме того, при совпадении результатов различных опытов (ведь возможно)
SS> данный алгоритм может выдать некорректный результат. К примеру: 1; 1; 1;
SS> 2; 4; 5; 7; 8; 9; 9. Грубо, но наглядно. А уж о том, что те же 90% мы
SS> редко получим, и надо бы уточнить, нужен "максимум, но не более" либо
SS> "минимум, но не менее", я молчу -- и так ясно...
SS> В качестве решения ничего конкретного предложить пока не могу, но,
SS> возможно, разумнее будет сначала определять закон распределения (тяжко,
SS> но выполнимо) -- после этого найти требуемый интервал будет гораздо
SS> легче.
При разработке алгоритма было принято:
1. 90% - в смысле "не менее 90%"
2. При повторении можно, как это часто принимается, считать повторяющиеся
отсчеты разными, хотя и отличающимися на пренебрежимо малую величину.
3. Если в качестве [a,b] взяты точки, не принадлежащие множеству имеющихся
значений, то всегда можно уменьшить длину интервала. Поэтому этот случай не
рассматривается.
Предложенный алгоритм имеет время решения O(N) без учета сортировки и O(NlogN)
с учетом (или менее, в зависимости от входных данных).
Изложу его повторно:
0. Упорядочиваем выборку и находим число оставленных в подвыборке точек
M=ceil(N*p/100)
1. Определяем L=X[M-1]-X[0].
2. Полагая i=1..N-M, вычисляем Lt=X[M-1+i]-X[i]
Если Lt<L то L=Lt, j=i
Отрезок минимальной длины L, содержащий не менее р процентов выборки, имеет
границами {X[j];X[M-1+j]}
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
