Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

PD>A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

PD>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?

Можно.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

PD>A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

PD>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?
Последовательно применить nth_element для k1 и k2 (линейная сложность от O(N)),
и затем отсортировать диапазон за O(Klog(K)).

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

PD>A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

PD>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?

Можно. метод медиан.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

PD>A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

PD>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?

Можно получить за O(n)+O(KlogK).
Сначала найти k1 и k2 порядковые статистики. Это делается за O(n) алгоритмом, который уже тут многократно обсуждался. Если он покажется слишком сложным, можно использовать модификацию quicksort, но сложность ее выполнения будет линейной лишь в среднем, а в худшем тот же O(n^2).
После нахождения A[k1] и A[k2] выбираем все элементы, находящиеся в интервале между между ними (еще надо отдельно рассмотреть случай с одинаковыми числами) за O(n).
Ну а потом сортировка найденного интервала за O(KlogK)

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

PD>>A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

PD>>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?
B>Последовательно применить nth_element для k1 и k2 (линейная сложность от O(N)),
у nth_element сложность O(n) в среднем
B>и затем отсортировать диапазон за O(Klog(K)).

> Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?

То есть, получить k1..k2'е порядковые статистики, за указанное время?

Ответ: нет, нельзя.
Очевидно, что хотя бы по одному разу мы должны прочесть каждый элемент массива.
Возьмём массив длиной N, так, что O(N) > O(K*log(K))...

Или же подразумевается, что для заданного N нужно найти алгоритм, не более чем линейно-логарифмический относительно K?
Тогда будем считать, что N*log(N) — это такой жирный коэффициент при O(K).

Здравствуйте, _DAle_, Вы писали:

B>>Последовательно применить nth_element для k1 и k2 (линейная сложность от O(N)),
_DA>у nth_element сложность O(n) в среднем
Почему в среднем?

Здравствуйте, Tan4ik, Вы писали:

T>Здравствуйте, _DAle_, Вы писали:

B>>>Последовательно применить nth_element для k1 и k2 (линейная сложность от O(N)),
_DA>>у nth_element сложность O(n) в среднем
T>Почему в среднем?

По требованиям стандарта с++

25.3.2 Nth element
...
1 After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for any iterator i in the range [first, nth) and any iterator j in the range [nth, last) it holds that: !(*i > *j) or comp(*j, *i) == false.
2 Complexity: Linear on average.

Кстати, не видел реализации stl, где сложность nth_element в худшем случае O(n).

Здравствуйте, _DAle_, Вы писали:

_DA>После нахождения A[k1] и A[k2] выбираем все элементы, находящиеся в интервале между между ними (еще надо отдельно рассмотреть случай с одинаковыми числами) за O(n).

Вот это не совсем понятно. Куда выбираем ? Никакой дополнительной памяти нет. Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве упорядоченные, а остальные — как бог даст. Т.е в том же самом массиве должен появиться упорядоченный кусок.

Здравствуйте, Кодт, Вы писали:

>> Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?

К>То есть, получить k1..k2'е порядковые статистики, за указанное время?

К>Ответ: нет, нельзя.
К>Очевидно, что хотя бы по одному разу мы должны прочесть каждый элемент массива.
К>Возьмём массив длиной N, так, что O(N) > O(K*log(K))...

К>Или же подразумевается, что для заданного N нужно найти алгоритм, не более чем линейно-логарифмический относительно K?
К>Тогда будем считать, что N*log(N) — это такой жирный коэффициент при O(K).

Ok, меняю условие

Время C1*N + C2*(K*log(K)), но при этом про C1 — ничего не скажу, а вот C2 = C3, где C3*(N*log(N)) — время полной сортировки.

Иными словами, линейные проходы не учитываем, а вот упорядочивание должно делаться не хуже, чем в quicksort.

Дополнительные массивы — не разрешаются. Даже размера K.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, _DAle_, Вы писали:

_DA>>После нахождения A[k1] и A[k2] выбираем все элементы, находящиеся в интервале между между ними (еще надо отдельно рассмотреть случай с одинаковыми числами) за O(n).

PD>Вот это не совсем понятно. Куда выбираем ? Никакой дополнительной памяти нет. Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве упорядоченные, а остальные — как бог даст. Т.е в том же самом массиве должен появиться упорядоченный кусок.

Для простоты рассмотрим случай, когда все числа различны.
После поиска k1 и k2 порядковых статистик они находятся на своих местах.
1. Заводим два указателя, один пробегается по всему массиву, второй пробегается только по интервалу [k1,k2].

2. Затем передвигаем первый указатель пока не найдем элемент, который пронадлежит нащему интервалу [A[k1], A[k2]], но не содержится еще в этом интервале.
3. Второй указатель передвигаем пока не найдем элемент, не принадлежащий этому интервалу, но содержащийся в нем.
4. Производим обмен, переходим на шаг 2.

Если же в массиве есть одинаковые элементы, тогда надо посчитать, сколько элементов строго меньше A[k1], сколько строго больше A[k2], и на основании этой информации получить количество элементов равных A[k1] и A[k2], принадлежащих нашему интервалу. Потом надо будет использовать эту информацию для алгоритма, описанного выше.

> Вот это не совсем понятно. Куда выбираем ? Никакой дополнительной памяти нет. Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве упорядоченные, а остальные — как бог даст. Т.е в том же самом массиве должен появиться упорядоченный кусок.

Элементарно! Пусть нам известны значения s1, s2 — соответствующие порядковые статистики.
Определим предикат s(x) = s1<=x && x<=s2 и его отрицание p(x) = !s(x)
Выполним уплотнение массива за один проход и тут же отсортируем

std::sort(
  a.begin(),
  std::remove_if(
    a.begin(),
    a.end(),
    p(s1,s2)
) );

Здравствуйте, Кодт, Вы писали:

>> Вот это не совсем понятно. Куда выбираем ? Никакой дополнительной памяти нет. Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве упорядоченные, а остальные — как бог даст. Т.е в том же самом массиве должен появиться упорядоченный кусок.

К>Элементарно! Пусть нам известны значения s1, s2 — соответствующие порядковые статистики.
К>Определим предикат s(x) = s1<=x && x<=s2 и его отрицание p(x) = !s(x)
К>Выполним уплотнение массива за один проход и тут же отсортируем
К>

К>std::sort(
К>  a.begin(),
К>  std::remove_if(
К>    a.begin(),
К>    a.end(),
К>    p(s1,s2)
К>) );
К>

"For every complex problem, there is a solution that is simple, neat, and wrong."

Во-первых, это не то, что просили

Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве

Во-вторых, с одинаковыми числами это работать не будет.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Вот это не совсем понятно. Куда выбираем ? Никакой дополнительной памяти нет. Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве упорядоченные, а остальные — как бог даст. Т.е в том же самом массиве должен появиться упорядоченный кусок.

Вот тут мне не совсем понятно. Пусть у нас есть массив

1 4 5 6 3 2

Массив индексируется с нуля, k1 = 2, k2 = 3. Что мы в итоге должны получить: это

1 3 5 6 4 2

или это

1 5 3 4 6 2

?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Есть массив A из целых значений, N элементов. Его можно отсортировать и тогда

PD>A[k1] .. A [k2] есть некий отрезок этого отсортированного массива длиной K = k2-k1+1 (0<=k1<=k2<= N-1)

PD>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?


если есть рекурсивная реализация двоичной сортировки, то при рекурсивном вызове если начало подмассива больше k2 или конец меньше k1, отбрасываешь
в наихудшем случае O(NlogN), наилучшем — O(N)+O(KlogK)

> К>Элементарно! Пусть нам известны значения s1, s2 — соответствующие порядковые статистики.
> К>Определим предикат s(x) = s1<=x && x<=s2 и его отрицание p(x) = !s(x)
> К>Выполним уплотнение массива за один проход и тут же отсортируем
> К>

> К>std::sort(
> К>  a.begin(),
> К>  std::remove_if(
> К>    a.begin(),
> К>    a.end(),
> К>    p(s1,s2)
> К>) );
> К>

>
> "For every complex problem, there is a solution that is simple, neat, and wrong."
>
> Во-первых, это не то, что просили

Надо чтобы элементы от k1 до k2 оказались на своих местах в том же самом массиве

С чего это?
s1,s2 — запомненные значения, а не ссылки.
После remove_if все числа, удовлетворяющие предикату s(x) окажутся в голове массива.
Осталось только отсортировать... Ах да, потом нужно его ещё передвинуть на k1.
Действительно, упустил. Но это всё равно O(K) < O(N).

> Во-вторых, с одинаковыми числами это работать не будет.

Пусть отфильтрованный массив имеет длину M. А должен — K<=M. То есть, сколько-то нужно отбросить...

За один проход по ещё необработанному массиву выясняем, сколько чисел
— строго меньше s1: A <- вот это нам пригодится.
— равно s1: B <- а вот это и далее — нет. Пишу только для иллюстрации.
— между s1 и s2: C
— равно s2: D
— строго больше s2: E

N = A+B+C+D+E
M = B+C+D
Нужно из всего массива отбросить (K1-1) первых элементов.
Соответственно, из отфильтрованного массива — взять подмассив [K1-A..K2-K1-A).
И передвинуть.

Кажется, ответ. На С++.

nth_element(a.begin(), a.begin()+k1,               a.end()); // O(N)
nth_element(           a.begin()+k1, a.begin()+k2, a.end()); // O(N-k1)
sort       (           a.begin()+k1, a.begin()+k2         ); // O(K*log(K))

Здравствуйте, Oyster, Вы писали:

O>Здравствуйте, Pavel Dvorkin, Вы писали:

O>

O>1 5 3 4 6 2
O>

O>?

Именно это. Элементы со 2 по 3 содержат то, что они бы содержали, если бы массив сортировался полностью. Именно этого я и хочу.

Впрочем, годится и

6 1 3 4 5 2

или

1 5 3 4 2 6

и т.д.

Здравствуйте, Кодт, Вы писали:

Да, это все верно, я просто хотел подметить, что совсем элементарного и красивого решения с предикатом не получится.