Поиск k максимальных элементов в столбце матрицы

[KSergP]

Кто-нибудь занимался решением такой задачи?
Как лучше реализовать на С/С++-?
Размер матрицы может быть большой а эти самые k максимальные элементы могут быть в небольшом количестве, поэтому команды типа Sort(последовательности) несовсем, по моему, подходят.....

[PAV]

Можно завести массив (или даже лучше список) длины $k$. Первые $k$ элементов столбца класть в него с сортировкой. Пройти по столбцу, каждый новый элемент сравнивать с минимальным из имеющихся. Если он меньше, то пропускать, иначе докладывать в массив, выкидывая из него наименьший.

[KSergP]

значит все таки список....
я думал немного по другому....
брать столбец копировать в список...потом после нахождения максимального его вырезать из списка....

[PAV]

KSergP писал(а):

значит все таки список....
я думал немного по другому....
брать столбец копировать в список...потом после нахождения максимального его вырезать из списка....

Ну это явно не оптимально, практически то же, что сортировка всего столбца.

[esperanto]

задача легко решается за линейное время.


Находим за линейное время Н-к порядковую статистику, где Н количество элементов в строке


Дальше тривиально находим за линейное время все элементы большие найденной статистики

[незваный гость]

esperanto писал(а):

Находим за линейное время Н-к порядковую статистику, где Н количество элементов в строке

Не поясните, а как Вы это делаете? (задача о голандском флаге?)

[esperanto]

незваный гость писал(а):

:evil:

esperanto писал(а):

Находим за линейное время Н-к порядковую статистику, где Н количество элементов в строке

Не поясните, а как Вы это делаете? (задача о голандском флаге?)

Да, пожалуйста.

Найти статистику порядка х, можно или детерминистическим - невероятностным способом или используя вероятностный метод быстрого поика статистик( вероятностный метод - концептуальный аналог метода быстрой сортировки, т.е плохих случаев у него нет с вероятностью стремящейся экспоненциально быстро к единице.)


Первый метод, не прост(относительно) И описывается в книги Риверста.

Вероятностный метод изящен. И его идею я приведу тут. Пусть надо найти медиану.
Выбираем случайный элемент. И считаем сколько элементов массива меньше его. Если количество таких элементов больше половины то медиану, будем искать среди меньших элементов(причем придеться искать не медиану а иную статистку). Инача медиану будем искать среди больших элементов

f(n,arr)
y=random element of arr.
s=sum of elemenits of arr wich<y
if s=n return s
if s<n then return f(n-s,element of arr wich great then y)
if s>n then retutn f(n,elements of arr wivh less then y
end f

[Yuri Gendelman]

2 esperanto
В худшем случае, когда на первом (вероятностном) шаге всегда выбирается максимальный или минимальный элемент, количество сравнений в вероятностном алгоритме будет равно $\frac{n(n-1)}{2}$. Вполне возможно, что в среднем сложность алгоритма - порядка n^{1+\delta}$, где $\delta < 1$. Но скорее всего все равно $\delta > 0$, т.е. алгоритм - не линейный по сложности.

Относительно основного вопроса: IMHО алгоритм, который предложил PAV, - наилучший и простейший при $k \ll n$. А вот если $k \backsim n$, то этот алгоритм по порядку сложности будет примерно эквивалентен сортировке.

[esperanto]

Yuri Gendelman писал(а):

2 esperanto
В худшем случае, когда на первом (вероятностном) шаге всегда выбирается максимальный или минимальный элемент, количество сравнений в вероятностном алгоритме будет равно $\frac{n(n-1)}{2}$. Вполне возможно, что в среднем сложность алгоритма - порядка n^{1+\delta}$, где $\delta < 1$. Но скорее всего все равно $\delta > 0$, т.е. алгоритм - не линейный по сложности.

Относительно основного вопроса: IMHО алгоритм, который предложил PAV, - наилучший и простейший при $k \ll n$. А вот если $k \backsim n$, то этот алгоритм по порядку сложности будет примерно эквивалентен сортировке.

ЕЩе раз. Вероятность того что алгоритм, не будет линейным порядка 2^(-n), когда п - размер массива.

Уже для массива размера 100, эта вероятность незначима.

Есть разнича между алгоритмами ошибающимися на 10% входных данных и ошибающимися с вероятностью 10% на любой вход.

Вообщем алгоритм линейный с вероятностью 1-2^(-n)

Добавлено спустя 54 секунды:

А на практике алгоритм часто работает быстрей невероятностого алгоритма.

[Yuri Gendelman]

esperanto писал(а):

ЕЩе раз. Вероятность того что алгоритм, не будет линейным порядка 2^(-n), когда п - размер массива.

Алгоритм, время работы которого линейно почти всегда, принято так и называть: "алгоритмом с линейной почти всегда сложностью".
Происхождение Вашей оценки ($2^{-n}$) мне не понятно. Вы хотите сказать, что время работы этого алгоритма линейно по времени для всех возможных последовательностей, кроме одной? Но это не так. На каждом из n-1 шагов возможны как минимум ДВА разных и одинаково неудачных выбора (максимум и минимум).

esperanto писал(а):

Есть разнича между алгоритмами ошибающимися на 10% входных данных и ошибающимися с вероятностью 10% на любой вход.

Для пользователя, если все входы равновероятны, разницы нет: вероятность ошибки равна 10%. Если возможные входы НЕ равновероятны, то 1-й алгоритм может быть как лучше, так и хуже 2-го.

[esperanto]

Yuri Gendelman писал(а):

esperanto писал(а):

ЕЩе раз. Вероятность того что алгоритм, не будет линейным порядка 2^(-n), когда п - размер массива.

Алгоритм, время работы которого линейно почти всегда, принято так и называть: "алгоритмом с линейной почти всегда сложностью".
Происхождение Вашей оценки ($2^{-n}$) мне не понятно. Вы хотите сказать, что время работы этого алгоритма линейно по времени для всех возможных последовательностей, кроме одной? Но это не так. На каждом из n-1 шагов возможны как минимум ДВА разных и одинаково неудачных выбора (максимум и минимум).

esperanto писал(а):

Есть разнича между алгоритмами ошибающимися на 10% входных данных и ошибающимися с вероятностью 10% на любой вход.

Для пользователя, если все входы равновероятны, разницы нет: вероятность ошибки равна 10%. Если возможные входы НЕ равновероятны, то 1-й алгоритм может быть как лучше, так и хуже 2-го.

По-поводу первого вашего вопроса, разумеется я имел ввиду вероятность ошибки, в о-нотации.
2^(-tetta(n))
По-поводу последнего замечания вы не правы. Вот представте себе вы староста и заказываете врача в деревню.

Врач, первого типа не вылечит 10% больных и они умрут.

Врач второго типа, сможет оказать повторную помощь тем больным которых он не вылечил и уже в среднем 1\100 людей останется не вылечеными.

[незваный гость]

Оценка метода PAV, по-моему, ${\rm O}(k \log k + (n-k) (\log k + k/2) )$. При малых $k$ может считаться линейной, при больших — (доля $n$) — уже нет. Впричем, алгоритм PAV можно слегка реорганизовать, заменив сортированную часть массива (длиной $k$) пирамидой (кучей, heap). Тогда оценка меняется до ${\rm O}(n \log k)$.

Впрочем, в STL входит алгоритм построения кучи за линейное время. (Я не уверен, что авторы текста имеют в виду, не разбирался.) Если так, то строим кучу за ${\rm O}(n)$ и вынимаем из нее $k$ элементов за ${\rm O}(k \log n)$.

[esperanto]

незваный гость писал(а):

:evil:
Оценка метода PAV, по-моему, ${\rm O}(k \log k + (n-k) (\log k + k/2) )$. При малых $k$ может считаться линейной, при больших — (доля $n$) — уже нет. Впричем, алгоритм PAV можно слегка реорганизовать, заменив сортированную часть массива (длиной $k$) пирамидой (кучей, heap). Тогда оценка меняется до ${\rm O}(n \log k)$.

Впрочем, в STL входит алгоритм построения кучи за линейное время. (Я не уверен, что авторы текста имеют в виду, не разбирался.) Если так, то строим кучу за ${\rm O}(n)$ и вынимаем из нее $k$ элементов за ${\rm O}(k \log n)$.

Авторы имеют в виду алгоритм сложности tetta(n)

[незваный гость]

esperanto писал(а):

Авторы имеют в виду алгоритм сложности tetta(n)

А что это за зверь — tetta? Если это $\Theta$, то в чем разница между ${\rm O}(n)$ и $\Theta(n)$ (мне казалось, они взаимозаменяемы)?

[esperanto]

незваный гость писал(а):

:evil:

esperanto писал(а):

Авторы имеют в виду алгоритм сложности tetta(n)

А что это за зверь — tetta? Если это $\Theta$, то в чем разница между ${\rm O}(n)$ и $\Theta(n)$ (мне казалось, они взаимозаменяемы)?

Как раз завтра это рассказываю студентам.

${\rm f(x)=O}(g(x))$ если существует с -постоянная большая ноля такая что :
f(x)<cg(X) для любого целого положительного х.

${\rm f(x)=$\Theta}(g(x))$ если существуют с,м -постоянные большая ноля такия что :
mg(x)<f(x)<cg(X) для любого целого положительного х.