Comments 36
Рекуррентное соотношение должно быть T(n) <= T(0.2 * n) + T(0.7 * n) + O(n), нам важно, что (0.2 * n + 0.7 * n) / n = 0.9 < 1. Использовать то, что T(n) = O(n) при доказательстве этого же факта — это facepalm.
Не так уж просто доказать, почему это равно O(n)
На самом деле очень просто — подберём константу c такую, что для всех n выполняется T(n) <= T(0.2 * n) + T(0.7 * n) + c * n или T(n) <= 10 * c * n , тогда T(n) <= 10 * c * n по индукции.

Кажется, что такой выбор опорного элемента (медиана из медиан) должен помогать и quicksort-у, поскольку при каждом разделении получаются более равные по длине 2 списка. Однако для quicksort доказано, что оптимальная стратегия выбора опорного элемента – случайная.

Я это помню по курсу Тима Рафгардена. В видео "Choosing a good pivot" лектор про это говорит и доказывает, что так получится среднее время O(n logn), но формальное доказательство, что случайная стратегия – наилучшая, наверное в его книге надо искать.

Обычно везде говорится, что этастратегия, не имеет детерминированной «kill sequence» (данные при которых сваливаемся в O(n^2)). На разных данных оптимальный выбор будет отличаться. Если сортировать последовательность равномерно распределённых случайных величин(или близкую к ней), то вообще можно брать первый попавшийся pivot: среднее не пострадает, а константа лучше.

Это я всё к чему — оптимальной стратегии нет. Есть размен ухудшения константы в среднем на отсутствие детерминированного худшего случая. А дальше зависит от данных и требований.

Пожалуй, про "оптимальную стратегию" – это громко сказано, запомнилось просто, как акцентировано это Рафгарден отмечал. В книге Сэджвика "Algorithms" про quicksort нашел только утверждение (с. 295, Proposition L), что в худшем случае quicksort делает ~ N^2/2 сравнений (очевидно), но случайное перемешивание на каждом шаге снижает число сравнений обратно до ~ n log n. Но да, это далеко не то же самое, о чем я говорил в начале.

Нужно как минимум понимать, что при рассмотрении quicksort со случайным выбором элемента среднее берётся не по входным данным, а по реализациям случайных решений в ходе алгоритма. Это и значит, что не существует набора данных, дающих n^2 — среднее количество операций для любого массива будет O(n log n).

Можно даже посчитать вероятность того, что алгоритм будет выполняться например в 5 раз медленнее, чем в среднем. Эта вероятность получается весьма малой, особенно при больших n — поэтому на практике имея адекватный генератор случайных чисел нет смысла что-то оптимизировать по сравнению со случайным выбором элемента.
Например:
Есть размен ухудшения константы в среднем на отсутствие детерминированного худшего случая.

«детерминированного худшего случая» нет ни в алгоритме со случайным выбором pivot, ни в описанном в статье.
Ну так я и не говорю, что в этих вариантах есть худший случай. Случайный выбор можно сделать быстрее O(1), данный алгоритм O(n). Первый не влияет на константу по идее, второй влияет. Для первого в каждом конкретном случае есть плохой вариант. Для второго, исключая массив повторяющихся величин, нет.
В данном случае такой размен.
Что-то я вас вообще не понял.
Случайный выбор можно сделать быстрее O(1)

Алгоритмов быстрее О(1) не бывает.
Для первого в каждом конкретном случае есть плохой вариант.

Поясните, что имеете в виду под случаем и что под вариантом?
можно сделать быстрее O(1)

Прошу прощения, пропущена запятая:
Случайный выбор можно сделать быстрее, за O(1), данный алгоритм(из статьи) O(n).

В данном контексте случай — реализация генератора псевдослучайных чисел. Вариант — набор данных, который нужно подать на вход quicksort (зная состояние ГПСЧ), чтобы свалиться в O(n^2).

Насколько я помню, quicksort используется исключительно из-за низкой константы, а при использовании "безопасного" поиска медианы он работает медленнее других алгоритмов сортировки.

Причём тут случайная стратегия, если речь о детерминированных алгоритмах? Детерминированный quicksort стандартно пишется как раз с таким же выбором опорного элемента, как и в алгоритме поиска медианы. Единственное отличие quicksort от quickselect — то, что он обрабатывает обе части массива, а не только одну из них.

Соответственно случайный выбор элемента можно абсолютно так же использовать и в поиске медианы, если не ограничиваться детерминированными алгоритмами.

Вывод по графику в статье


Детерминированный опорный элемент почти всегда рассматривает при quickselect меньшее количество элементов, чем случайный

Мой вопрос (или мысли вслух): работает ли то же самое для quicksort. Будет ли детерминированный quicksort with median pivots рассматривать меньше элементов, чем недетерминированный quicksort with random pivot.

Да, это тоже верно. Однако, как отмечено и в статье, это не говорит о более быстром выполнении алгоритма. Всегда или почти всегда на практике быстрее работает случайный выбор.
А почему pivot выбирается именно как элемент массива с некоторым индексом? В случае quicksort это понятно, но для quickselect можно выбрать любое значение (не обязательно из массива). Например, брать среднее (O(n)), тогда массив будет гарантированно хорошо делиться.
Вот контрпример: массив, состоящий из одного числа 100 и 99 нулей. Среднее значение равно 1. В итоге в одной части окажутся все нули, а во второй всего одно число — наша сотня. Не самой удачное разделение, не так ли?
По приколу спрошу: ваша версия деления такого массива примерно пополам? :)
Это только на один цикл вглубь. На следующем окажется, что все элементы одинаковы.

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

В статье это никак не раскрыто.
Описанный в статье алгоритм это и есть детерминированный quickselect, и он абсолютно так же обобщается.
Вы наверное какую-ту другую статью читали. Потому что то, что описано в статье сначала рассматривает нахождение медианы как нахождение k-й порядковой статистики с номером N/2, а потом, рекурсивно решает задачу нахождения k-й порядковой статистики.

Обратите внимание что один шаг алгоритма: он заключается в том, что мы отбрасываем либо 30% «слишком больших» чисел, либо 30% слишком маленьких, после чего ищем… медиану? Фиг вам: так как «перекосили» массив, то нам теперь нужна не медиана, нам нужен элемент с другим (впрочем легко высчитываемым) номером.

Куда вы это обобщать собрались?
Ваши алгоритмы. Все на Python 3.6.3
Что-то мне не везло. Это все на списке из 10 000 рандомных от 0 до 1000
Причем, 3-я функция работает с ошибкой.
Для 1-ой:
2.47 ms ± 39.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Для 2-ой:
7.92 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Для 3-ей:
11.2 ms ± 73.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Дык список слишком короткий, чтобы найти различие между 1 и 2. А 3 и должна работать дольше, она только сравнений меньше делает (ну и имеет теоретическую гарантию того, что не будет тупить — для варианта 2 можно подобрать контрпример).

В C++ уже всё сделано для вас:


#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main()
{
    std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

    std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    std::cout << "The median is " << v[v.size()/2] << '\n';
}

Output:


The median is 5

Вот здесь же:


# Для простоты мы можем отбросить все группы, которые не являются полными. O(n)
full_chunks = [chunk for chunk in chunks if len(chunk) == 5]

можно упростить до:


last_chunk = chunks[len(chunks) - 1]
full_chunks = chunks
if len(last_chunk) < 5:
    full_chunks.pop()

и будет О(1). Разбивка ведь оригинального списка ведётся так, что меньше 5-ти элементов может быть только в последнем подсписке.


Кроме того, визуализация алгоритма неправильная же. В первом и последнем подсписках выбраны вовсе не медианы! В первом подсписке медиана 41, а не 99, а во втором — 65 вместо 116. Правда, это легко исправляется дописыванием единичек спереди к последним числам в подсписках, но всё равно странно приводить заведомо неправильную картинку в качестве визуализации алгоритма.

можно упростить
и будет О(1)

Хорошее замечание. Стоит уточнить, что хотя асимптотика всего алгоритма от этого не меняется, мы уменьшаем константу.

Привет, я автор. Извините за автоматический перевод. Спасибо, что заметили эту ошибку! Это был ужасный надзор, и я исправил его.
# Затем мы сортируем каждый фрагмент. Каждая группа имеет фиксированную длину, поэтому каждая сортировка
# занимает постоянное время. Поскольку у нас есть n/5 фрагментов, эта операция
# тоже O(n)

Мне не понятно почему это время линейное. Ну, да — у нас n/5 фрагментов, как из этого следует что сортировка n/5 фрагментов по 5 элементов это O(n)?
Потому что время сортировки одного фрагмента ограничено сверху. Ну пусть отсортировать 5 элементов требует до 100500 операций (очень плохая, очень медленная сортировка), тогда отсортировать n/5 фрагментов — это не более 20100 * n операций. 20100 * n — это O(n)
Опечатка в примере, вместо индекса 2 нужен индекс 3 здесь:
Мы выбрали индекс 2, значение в котором равно l[2]=6
Да, там ещё на следующей строчке неверно разделён массив, нужно 8 добавить.
Разбиваем на группы согласно pivot:
[3,4,5,6] [9,8,7,10]
Only those users with full accounts are able to leave comments. Log in, please.