Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Стоит сказать, что в C++ этот алгоритм реализован в виде функции nth_element(A.begin(), A.begin() + n, A.end()), которая ставит на n-ое место, собственно, n-ое по величине число, пользуясь описанным алгоритмом.
Достаточно подробно описано, спасибо.
Странно, что вы нигде в статье не использовали название алгоритма — «Порядковая статистика».
Странно, что вы нигде в статье не использовали название алгоритма — «Порядковая статистика».
Да, это называется «K-ая порядковая статистика».
прошу прощения за Pascal, но мои ученики пока знают только его
А причем тут ваши ученики?
Статья — фрагмент лекции.
Обычно жалюутся, что «мои преподаватели знают только его» ;)
k-ый элемент характеризуется тем, что он больше (или равен) k элементов массива...k-ый элемент характеризуется тем, что он больше (или равен) k-1 элементов массива.
А в массиве (3, 2, 1) третий элемент меньше чем все остальные, т.е. ни разу не больше и не равен. Под к-ым элементом имеется ввиду к-ый по величине.
Таким темпом через пару лет надо будет верстать «Алгоритмы. Построение и анализ (в хабрапереводе)».
А такие алгоритмы называются к-оптимальными… Я по ним диплом писал :D
Процедура разделения, используемая в быстрой сортировке, даёт потенциальную возможность находить искомый (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).
Даже более того, если поделить выпадание «хорошего» и «плохого» элементов (для нас «хороший» это если его значение в промежутке 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) — этим же, рекурсивно. Правда, меняться будет только константа.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск k-ого наименьшего элемента