|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Subbotin 2:5035/53.6 13 Jul 2003 02:57:59
To : Evgenij Masherov
Subject : Re: 90%
--------------------------------------------------------------------------------
12 июля 2003 в 13:21 Evgenij Masherov ругался с Sergey Subbotin:
SK>>>> Есть выбоpка из N pезyльтатов экспеpимента, значения измеpяемой
SK>>>> величины лежат в диапазоне [a,b]. Распpеделение неизвестно. Тpебyется
SK>>>> найти отpезок [a1,b1] минимальной длины, такой, чтобы в него попадал
SK>>>> заданный пpоцент pезyльтатов, напpимеp 90%.
SS>> Кроме того, при совпадении результатов различных опытов (ведь возможно)
SS>> данный алгоритм может выдать некорректный результат. К примеру: 1; 1; 1;
SS>> 2; 4; 5; 7; 8; 9; 9. Грубо, но наглядно. А уж о том, что те же 90% мы
SS>> редко получим, и надо бы уточнить, нужен "максимум, но не более" либо
SS>> "минимум, но не менее", я молчу -- и так ясно...
EM> 1. 90% - в смысле "не менее 90%"
В моем примере получается 100%. Это слишком большое отклонение.
EM> 2. При повторении можно, как это часто принимается, считать повторяющиеся
EM> отсчеты разными, хотя и отличающимися на пренебрежимо малую величину.
Как раз чаще наоборот -- результаты, отличающиеся на пренебрежимо малую
величину, принимают совпадающими. Иначе "1 не равно 1".
EM> 3. Если в качестве [a,b] взяты точки, не принадлежащие множеству
EM> имеющихся значений, то всегда можно уменьшить длину интервала. Поэтому
EM> этот случай не рассматривается.
a и b -- максимальное и минимальное значения, не принадлежать множеству [a,b] не
могут.
EM> Предложенный алгоритм имеет время решения O(N) без учета сортировки и
EM> O(NlogN) с учетом (или менее, в зависимости от входных данных). Изложу
EM> его повторно:
EM> 0. Упорядочиваем выборку и находим число оставленных в подвыборке точек
EM> M=ceil(N*p/100)
EM> 1. Определяем L=X[M-1]-X[0].
EM> 2. Полагая i=1..N-M, вычисляем Lt=X[M-1+i]-X[i] Если Lt<L то L=Lt, j=i
EM> Отрезок минимальной длины L, содержащий не менее р процентов выборки,
EM> имеет границами {X[j];X[M-1+j]}
Согласно этому, в моем примере отрезок L имеет границами {X[0];X[8]}, или же
{1;9}. Однако в интервал {1;9} попадают 100% результатов (что, однако,
удовлетворяет условию "не менее 90%"). Точность весьма страдает...
Более сложно и не так быстро:
0. Разбиваем диапазон значений на k интервалов;
где k=7*log(N).
1. Определяем частоты h_i попадания в каждый интервал.
Всем спасибо, все свободны Л. В. Змей.
О, это сладкое слово _тишина_...
--- Ой, а у вас молоко убежало!
* Origin: Игра на раздевание. В шахматы. По переписке... (2:5035/53.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
