Pull to refresh

Comments 26

Стоит сказать, что в C++ этот алгоритм реализован в виде функции nth_element(A.begin(), A.begin() + n, A.end()), которая ставит на n-ое место, собственно, n-ое по величине число, пользуясь описанным алгоритмом.
Достаточно подробно описано, спасибо.

Странно, что вы нигде в статье не использовали название алгоритма — «Порядковая статистика».
k-я порядковая статистика — это то, что мы ищем, элемент с номером k в вариационном ряду. Вы уверены, что алгоритм называется так же?
Да, это называется «K-ая порядковая статистика».
прошу прощения за Pascal, но мои ученики пока знают только его

А причем тут ваши ученики?
Статья — фрагмент лекции.
Обычно жалюутся, что «мои преподаватели знают только его» ;)
Обычно жалуются только единицы, которые сами пытаются разобраться во всём. Остальные 80% группы знают только паскаль. А 10% из этих 80% и его не знают :) По крайней мере у той группы, в которой я проводил пары примерно так и было. Да и в моей так же было. Суровые реалии :)
Да, наверное, вы правы, 80% просто помалкивают в тряпочку, в результате создаётся ложное впечатление.
k-ый элемент характеризуется тем, что он больше (или равен) k элементов массива...
k-ый элемент характеризуется тем, что он больше (или равен) k-1 элементов массива.
В массиве (2, 3, 1) второй элемент (2) больше или равен двум элементам — 1 и 2.
А в массиве (3, 2, 1) третий элемент меньше чем все остальные, т.е. ни разу не больше и не равен. Под к-ым элементом имеется ввиду к-ый по величине.
Я второй по величине и имел ввиду, посмотрите внимательно.
Третий по величине в (3, 2, 1) элемент (то бишь 3) больше или равен 3 элементам — 1, 2 и 3.
А разве сам k-ый элемент учитывается?
Ну он же больше или равен самому себе, нет? :)
А в массиве (3, 2, 1) третий элемент меньше чем все остальные, т.е. ни разу не больше и не равен. Под к-ым элементом имеется ввиду к-ый по величине.
Таким темпом через пару лет надо будет верстать «Алгоритмы. Построение и анализ (в хабрапереводе)».
А такие алгоритмы называются к-оптимальными… Я по ним диплом писал :D
И да, в любой задаче поиск k-го оптимального элемента имеет тот же класс сложности что и поиска 1го. Вопрос лишь в константе :)
Процедура разделения, используемая в быстрой сортировке, даёт потенциальную возможность находить искомый (k-ый) элемент гораздо быстрее.

гм, интересно… видно как кто изучал алгоритмы.

Я наоборот, думал что алгоритм нахождения k-ого меньшего элемента является базовым для квиксорта: «Quicksort is a sorting algorithm that splits the array in exactly the same way as the mean algorithm; and once the subarrays are sorted, by two recursive calls, there is nothing»

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

Но в целом статья в некоторой мере полезна своей минимальностью :)
Оценка сложности идёт по среднему случаю, а N^2 — наихудший.
В том то и задача — оценить «среднее». Это совсем не простая задача. В данной задаче выходит что при высоком n реализация алгоритма скорее стремится к нижнему порогу — O(N), что можно показать в принципе.

Даже более того, если поделить выпадание «хорошего» и «плохого» элементов (для нас «хороший» это если его значение в промежутке 1/4 до 3/4 от минимального до максимального) после двух операций деления, в худшем случае остаентся 3/4 массива (учитывая что для того, чтоб выпал хороший то надо в среднем 2 раза поделить). Что выходит

T(N) <= T(3*N/4)+O(N).

Что можно применить рекурсивно.

В итоге более справедливо будет сказать что средняя оценка будет не O(2N) как в статье, а O(N).
По-моему, Ваш код не будет работать, когда N=2 в силу условия цикла в строке №7 L<R-1.
Ладно паскаль, но однобуквенные имена переменных — это mauvais tone и антипаттерн как ни крути.
Можно без особого труда заставить этот алгоритм гарантированно работать за линейное время. Если мы поделим массив на пятерки элементов, в каждой пятерке найдем средний элемент (6 сравнений на пятерку), а потом возьмем медиану X из этих средних элементов (рекурсия — R(N/5) операций, где R(N) — сложность исходного алгоритма), то нетрудно доказать, что порядковый номер этой медианы будет лежать между 3/10*N и 7/10*N: мы можем предъявить 3/10*N элементов массива, гарантированно не больших X, и столько же — гарантированно не меньших X. После еще X сравнений задача сводится к поиску какой-то статистики с массиве длиной не больше 7/10*N, т.е. R(N)<=R(N/5)+R(7*N/10)+11/5*N (считается число сравнений), т.е. R(N)<=22*N. Многовато, зато надежно. При больших N можно заменить 5 на большие числа (7,9,...), и искать в них медианы сначала оптимальным алгоритмом, а потом (при очень больших N) — этим же, рекурсивно. Правда, меняться будет только константа.
* должно быть «порядковый номер этой медианы в вариационном ряду исходного массива»
Sign up to leave a comment.

Articles