Comments 40
Не так уж просто доказать, почему это равно 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), но формальное доказательство, что случайная стратегия – наилучшая, наверное в его книге надо искать.
Это я всё к чему — оптимальной стратегии нет. Есть размен ухудшения константы в среднем на отсутствие детерминированного худшего случая. А дальше зависит от данных и требований.
Пожалуй, про "оптимальную стратегию" – это громко сказано, запомнилось просто, как акцентировано это Рафгарден отмечал. В книге Сэджвика "Algorithms" про quicksort нашел только утверждение (с. 295, Proposition L), что в худшем случае quicksort делает ~ N^2/2 сравнений (очевидно), но случайное перемешивание на каждом шаге снижает число сравнений обратно до ~ n log n. Но да, это далеко не то же самое, о чем я говорил в начале.
Можно даже посчитать вероятность того, что алгоритм будет выполняться например в 5 раз медленнее, чем в среднем. Эта вероятность получается весьма малой, особенно при больших n — поэтому на практике имея адекватный генератор случайных чисел нет смысла что-то оптимизировать по сравнению со случайным выбором элемента.
Есть размен ухудшения константы в среднем на отсутствие детерминированного худшего случая.
«детерминированного худшего случая» нет ни в алгоритме со случайным выбором pivot, ни в описанном в статье.
В данном случае такой размен.
Случайный выбор можно сделать быстрее O(1)
Алгоритмов быстрее О(1) не бывает.
Для первого в каждом конкретном случае есть плохой вариант.
Поясните, что имеете в виду под случаем и что под вариантом?
можно сделать быстрее O(1)
Прошу прощения, пропущена запятая:
Случайный выбор можно сделать быстрее, за O(1), данный алгоритм(из статьи) O(n).
В данном контексте случай — реализация генератора псевдослучайных чисел. Вариант — набор данных, который нужно подать на вход quicksort (зная состояние ГПСЧ), чтобы свалиться в O(n^2).
Насколько я помню, quicksort используется исключительно из-за низкой константы, а при использовании "безопасного" поиска медианы он работает медленнее других алгоритмов сортировки.
Соответственно случайный выбор элемента можно абсолютно так же использовать и в поиске медианы, если не ограничиваться детерминированными алгоритмами.
Вывод по графику в статье
Детерминированный опорный элемент почти всегда рассматривает при quickselect меньшее количество элементов, чем случайный
Мой вопрос (или мысли вслух): работает ли то же самое для quicksort. Будет ли детерминированный quicksort with median pivots рассматривать меньше элементов, чем недетерминированный quicksort with random pivot.
(Хотя, чтобы корректно выйти из этой ситуации, исходный алгоритм должен делить вход не на две части, а на три, или же пополамить набор элементов, равных опорному. Для quicksort некоторые методы деления отрезка специально заточены на оптимизацию такого варианта. Это можно перенести и на quickselect, но явно.)
В статье это никак не раскрыто.
Обратите внимание что один шаг алгоритма: он заключается в том, что мы отбрасываем либо 30% «слишком больших» чисел, либо 30% слишком маленьких, после чего ищем… медиану? Фиг вам: так как «перекосили» массив, то нам теперь нужна не медиана, нам нужен элемент с другим (впрочем легко высчитываемым) номером.
Куда вы это обобщать собрались?
Что-то мне не везло. Это все на списке из 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)
В 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. Правда, это легко исправляется дописыванием единичек спереди к последним числам в подсписках, но всё равно странно приводить заведомо неправильную картинку в качестве визуализации алгоритма.
# Затем мы сортируем каждый фрагмент. Каждая группа имеет фиксированную длину, поэтому каждая сортировка
# занимает постоянное время. Поскольку у нас есть n/5 фрагментов, эта операция
# тоже O(n)
Мне не понятно почему это время линейное. Ну, да — у нас n/5 фрагментов, как из этого следует что сортировка n/5 фрагментов по 5 элементов это O(n)?
Мы выбрали индекс 2, значение в котором равно l[2]=6
Мой любимый алгоритм: нахождение медианы за линейное время