Деоптимизация алгоритмов сортировки до O (∞)

Эксперименты, проводимые в области информатики, не так уж дороги. Возможно, вы проходили вскрытие на уроке биологии, где каждый набор для вскрытия лягушки может стоить около 20 долларов или более 30 долларов в случае эмбриональной свиньи. Он может стать еще дороже с набором для лаборатории титрования для химии, стоимость которого превышает 50 долларов за единицу. В информатике может потребоваться определенная стоимость оборудования, но это не значит, что компьютерное оборудование используется одноразово. Эксперименты в области информатики можно проводить на том же компьютере, который вы используете для электронных таблиц, просмотра YouTube и игр. Простое выполнение нескольких строк кода представляет собой эксперимент по информатике, не требующий значительных долларовых затрат. В результате самая «дорогая» стоимость компьютерного эксперимента - это не деньги, а время.

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

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

Это принимает форму нотации Big O, которая формирует верхнюю границу времени работы алгоритма с точки зрения n или размера ввода.

Цель оптимизации алгоритма - сделать его как можно ближе к O (1), что является постоянным временем. Алгоритм с постоянным временем даже не меняется по времени выполнения при изменении n и, следовательно, является самым быстрым из возможных алгоритмов. Конечно, не все проблемы могут быть решены с помощью алгоритма O (1), поскольку параметры рассматриваемой задачи накладывают ограничения на то, насколько эффективным может быть алгоритм. Чтобы измерить эффективность алгоритма, мы можем взглянуть на алгоритмы сортировки, которые сортируют данные в определенном порядке (обычно от наименьшего к наибольшему). Например, широко считается, что быстрая сортировка с временем выполнения O (nlogn) является одним из самых быстрых алгоритмов сортировки. При наличии набора неупорядоченных данных фактически невозможно снизить временную сложность до O (n). В конце концов, простой обход всего массива занимает O (n) времени, а это совсем не то же самое, что его сортировка. Существует несколько вариантов быстрой сортировки, например mergesort и Timsort, которые также имеют время выполнения O (nlogn), которые различаются только лучшими сценарии (здесь выигрывает Timsort). Эти алгоритмы O (nlogn) по сути являются лучшими из лучших, когда дело доходит до алгоритмов сортировки. Когда дело доходит до сортировки списка в Python как можно быстрее, нет необходимости реализовывать собственный метод, поскольку Timsort уже настроен на стандартный алгоритм сортировки, начиная с версии 2.3. Это не означает, что нет причин изучать сортировку вставкой или сортировку по выбору, если на то пошло. Понимание менее эффективных методов сортировки, анализ их больших временных сложностей и их самостоятельная реализация дает свои фундаментальные преимущества для информатики.

Кажется, что мир давно придумал наиболее эффективные алгоритмы сортировки (естественно), но как насчет другого конца спектра? Можем ли мы специально разработать алгоритм сортировки, который займет годы или даже столетия? Насколько неэффективными мы можем стать?

Я хотел бы кое-что предупредить: НЕ используйте следующие алгоритмы на практике. Уже используются гораздо более эффективные алгоритмы сортировки, и проявление «творчества» с глупой реализацией обезьяньей сортировки, когда дело доходит до собеседования по кодированию или проекта разработки серверной части, не закончится хорошо.

Богосорт

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

Алгоритмы сортировки состоят из двух этапов, которые повторяются итеративно или рекурсивно: (1) установка массива (или его части) в правильный порядок посредством манипуляции с индексом массива и (2) проверка правильности манипуляции с индексом массива. Если второй шаг вам не знаком, это потому, что стандартные алгоритмы сортировки встроены в первый шаг. Например, сортировка выбора проходит по неотсортированной части массива в поисках наименьшего значения, а затем помещает его в конец отсортированного раздела. Повторяя этот процесс, он эффективно выполняет надлежащие манипуляции с индексом массива без необходимости последующей проверки. Это резко контрастирует с bogosort, который выполняет случайные манипуляции с индексами массива, а затем четко проверяет, привели ли все эти операции (по чистой случайности) к упорядоченному массиву. Чтобы лучше понять, как работает bogosort, давайте рассмотрим реализацию Java. Вы можете найти код на моем GitHub здесь, но я также встроил его, используя приведенную ниже суть:

Я добавил несколько комментариев, которые объясняют большую часть кода, но я также хочу дать более подробное объяснение. Начнем с ядра bogosort, в строке 21:

swap(a, i, (int)(Math.random()* a.length));

Эта строка кода меняет местами два индекса: i, который определяется циклом for, и случайный индекс (который может иметь то же значение, что и i). Поскольку цикл for заставляет i пройти через весь массив, эта строка эффективно рандомизирует массив, заменяя каждый индекс случайным индексом. Использование вспомогательной функции (в данном случае swap) не требуется. Вы можете просто написать код для свопа прямо в цикле for, если хотите. Как вы, возможно, догадались, этот цикл for составляет часть алгоритма сортировки «манипулирование индексом массива», но, как я уже упоминал ранее, проверка правильности порядка отличается в bogosort. Давайте посмотрим на это дальше. Я заменил цикл for комментарием «рандомизировать».

boolean flag = false;
while (!flag){
    // randomize
    flag = inOrder(a);
}

После замены цикла for код становится очень простым. Логическая переменная flag инициализируется значением false и отслеживает отсортированный статус массива. Вот почему условием цикла while является ! Flag, поскольку цикл while будет выполняться только в том случае, если его условие истинно, и мы хотим запускать цикл до тех пор, пока массив НЕ отсортирован (в другими словами, когда flag ложно).

После рандомизации массива flag устанавливается на логическое значение оператора: «Массив в порядке». Это достигается с помощью вспомогательной функции inOrder, которая, как и swap, не нужна. Таким образом, если массив не отсортирован, цикл будет запущен снова, рандомизируя массив для перестановки (скорее всего, другой, в зависимости от размера массива) и установив flag в упорядоченный статус. опять таки. Если случайная перестановка находится в правильном порядке, тогда flag устанавливается в значение true, цикл while завершается и bogosort завершается.

Те из вас, кто знаком с богосортом, возможно, заметили, что моя реализация богосорта не настолько эффективна, насколько это возможно (очевидно). Я имею в виду самое начало самого метода богосорта; отсутствует одна важная проверка:

public static void bogoSort(int[]a){
    // What's missing here?  
    boolean flag = false;

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

Две комбинации реализаций и тестовых примеров могут позволить завершить bogosort за O (n) времени, предполагая, что большой O был ограничен доменом лучшего случая:

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

Ключевое различие между этими двумя реализациями заключается в том, что вторая реализация требует проверки inOrder в начале bogosort:

public static void bogoSort(int[]a){
    if (inOrder(a) == true) return;  // previously missing
    boolean flag = false;

Здесь пустой оператор return работает аналогично оператору break в цикле. В этой реализации bogosort распознает, задан ли ему отсортированный массив, и завершит работу, если это так.

С другой стороны, первая реализация не особо заботится о том, дан ли ей упорядоченный массив. Он немедленно перейдет в цикл while, рандомизируя и проверяя порядок.

Однако есть еще один способ реализовать проверку inOrder на подлинность ввода - поместить его в начало цикла:

public static void bogoSort(int[]a){
    boolean flag = false;
    while (!flag){
        if (inOrder(a)) return;  // check built into loop
        // randomize
        flag = inOrder(a);
    }

Этот метод может показаться немного более неэффективным, поскольку дополнительный вызов inOrder означает добавление тега O (n) во время выполнения, но с n! на картинке, и большие коэффициенты падения O, в конечном итоге значимой разницы нет.

Зная эти небольшие расхождения между реализациями, в чем разница в среде выполнения большого O? Прежде чем мы начнем производить какие-либо вычисления, давайте приписываем несколько римских цифр трем различным реализациям. Первый (который не проверяет порядок во входных данных) будет называться I. Второй (который проверяет порядок во входных данных один раз) будет называться II. Третий (который проверяет порядок во входных данных один раз, а затем продолжает проверять его при каждой итерации цикла) будет называться III.

Глядя на bogosort I, мы видим, что есть два фрагмента кода, которые вызывают доступ к массиву - самую дорогостоящую операцию, которую мы будем рассматривать для нашего большого вычисления О. Во-первых, это операция подкачки, которая поначалу может показаться, что она занимает O (n) временных затрат, но на самом деле она гораздо менее эффективна. Это связано с тем, что цикл for, который вызывает метод подкачки, заключен в цикл while, который проверяет упорядоченный статус массива. Это означает, что операция подкачки связана с временной сложностью O (n!) из-за общего числа возможных перестановок данного массива. Это также подводит нас ко второй части кода, который выполняет доступ к массиву, и к вызову inOrder, который в худшем случае (большой O формирует верхнюю границу) примет O (n-1) время, которое можно просто сократить до O (n).

Вы могли заметить, что временная сложность вызовов подкачки O (n!) на самом деле не совсем точна. В конце концов, функция подкачки делает намного больше обращений к массиву, чем предполагает наш расчет O (n!). Но это утверждение о неточности также можно сказать о нашем большом вычислении O для inOrder, которое занимает O (n-1) времени, но сокращается до O (n), поскольку при большом O отбрасываются незначительные члены и коэффициенты - отсюда и временная сложность O (n!) для рандомизированной сортировки, которую выполняет bogosort. Это оставляет нам большое время работы O, равное O (n! * n) для bogosort I.

Теперь давайте посмотрим на bogosort II, который очень похож. Фактически, единственная разница между bogosort I и II заключается в том, что последний имеет проверку inOrder перед циклом while. Поскольку вызов inOrder находится вне цикла while и, следовательно, не зависит от перестановок, через которые проходит bogosort, в конечном итоге он оказывается добавлением к вычислению большого O, а не умножением. Другими словами, этот вызов inOrder происходит один раз при каждом вызове bogosort II, в то время как вызов inOrder внутри цикла while происходит for каждый раз, когда цикл while выполняется. Если что-то выполняется для каждый раз, когда что-то еще, то вы знаете, что это связано с умножением. Та же логика может быть применена к вычислению количества перестановок для массива. Например, мы знаем, что количество перестановок массива длиной 7 равно 7 !, но как рассчитывается это значение? Представим, что создается новый пустой массив длиной 7. В этом массиве мы протестируем различные перестановки нашего набора данных. В первом слоте у нас есть 7 вариантов. Записываем 7 в свои заметки. Переходим к следующему слоту. Зная, что один из наших вариантов был удален, теперь у нас есть 6 вариантов на выбор. Так что записываем 6. Постой. Что находится между 7 и 6? Конечно же, символ умножения! Если вы задумаетесь о том, как формируются перестановки, количество вариантов каждого слота равно для каждого из предыдущих вариантов. В этом случае есть 6 вариантов для каждого из 7 вариантов, что означает, что мы должны умножить два. Перемещая вперед еще один слот, мы использовали другой вариант, а это означает, что нам нужно умножить 5 на наш текущий продукт и так далее, и так далее. Отсюда и появился факториал (!).

Итак, большой O богосорта II не сильно отличается от богосорта I, и после сокращения вы увидите, что он точно такой же. Мы знаем, что часть нашего большого вычисления O будет O (n! * N), но мы также должны отметить O (n) для одного дополнительного вызова inOrder, поэтому у нас есть O (n! * n + n). Но это не наш окончательный ответ, поскольку O (n) совершенно несущественно по сравнению с величиной факторного члена. Наше последнее большое время работы O для bogosort II - O (n! * n).

Наконец, у нас есть большая буква O богосорта III (у меня есть скрытое подозрение, что время работы большого O будет таким же, как и у предыдущих…). Единственная разница между bogosort III и I заключается в том, что первый имеет дополнительную проверку inOrder в цикле while. Поскольку один вызов inOrder в цикле while умножает n на n!, добавление еще одного n просто означает, что мы получим O ( n! * 2n), который можно упростить до O (n! * n). Фактически, это снижение коэффициента было сделано для всех больших вычислений O для предыдущих реализаций bogosort - все обращения к массиву, выполняемые с помощью подкачки, просто умножают n на некоторую константу, которую мы назовем z. В итоге мы получим O (n! * Zn), что снижает коэффициент z, чтобы получить O (n! * N ) для нашего большого времени работы O Богосорта III.

Посмотрев на все три реализации bogosort и не обнаружив значимой разницы во времени работы между ними, мы можем сделать вывод, что bogosort - наименее эффективный алгоритм, верно? Как мы можем победить O (n! * N)?

Богобогосорт

Я думаю, вы уже знаете, к чему это идет. Богобогосорт, который я для простоты назову BBS, представляет собой рекурсивную версию bogosort, которая превращает и без того неэффективный алгоритм сортировки в еще более неэффективный алгоритм сортировки. Есть несколько разных способов реализовать богобогосорт, и все они крайне неэффективны. Здесь только несколько:

Постепенно произвольно сортируйте все большие и большие подмножества набора данных, пока сам набор данных не будет отсортирован: Для массива {1, 2, 3, 4, 5}, например, bogosort {1}, затем bogosort { 1, 2}, затем bogosort {1, 2, 3}, затем bogosort {1, 2, 3, 4} и, наконец, bogosort {1, 2, 3, 4, 5}. Способ, которым разработан этот богобогосорт, даже не логически обоснован (ну, с чего бы это могло быть?), Поскольку чудовищные виды меньших подмножеств даже не помогают окончательному богосорту закончить работу быстрее. В конце концов, этот последний bogosort - единственный, который имеет значение - все bogosort предыдущих подмножеств просто существуют, чтобы существенно замедлить время выполнения.
Постепенно произвольно сортируйте все большие и большие подмножества набора данных до тех пор, пока сам набор данных не будет отсортирован, НО, начните заново, если сортируемые данные не в порядке в какой-либо момент: Хорошо, это довольно плохо. Этот алгоритм будет постоянно вызывать такую функцию, как inOrder, на протяжении всего неэффективного процесса сортировки, и тот факт, что он так часто перезапускается, делает его ужасно медленным. Чтобы уточнить, богосортировка сбрасывается только в том случае, если сортируемые данные не в порядке в какой-либо момент. Если бы богосортировка была перезапущена для всего набора данных, вышедшего из строя, алгоритм никогда не завершился бы для любых неупорядоченных входов размера 2 или больше.
Эзотерический богобогосорт: https://www.dangermouse.net/esoteric/bogobogosort.html Я настоятельно рекомендую прочитать это; алгоритм даже не завершился для набора данных размером 7!

В качестве задачи попробуйте вычислить большое О всех этих богобогосортов! На странице эзотерической ссылки bogobogosort довольно много математики, которую вы можете использовать для вдохновения. Найдя большую букву O для bogobogosort, вы скоро поймете, почему люди говорят, что он не закончится ни для одного значительного списка перед тепловой смертью Вселенной, которая длится около 10¹⁰⁰ лет.

Однако мы не закончили деоптимизировать наши алгоритмы сортировки. Для следующих нескольких «алгоритмов» сортировки нам, возможно, придется немного изменить правила.

Сортировка с помощью альфа-частиц, внутреннего порядка и разрушения вселенной

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

Чудесная сортировка

Чудо-сортировка именно такая, как следует из названия. Сначала проверьте упорядоченный статус набора данных. Если что-то не так, подождите немного. Тогда проверьте еще раз. Повторить.

На первый взгляд кажется, что чудо-сортировка не работает ни с одним неупорядоченным набором данных, но это не всегда так. Miracle Sort не выполняет сортировку по коду или тому, что мы можем назвать программным обеспечением. Miracle Sort использует оборудование для сортировки. Компьютеры не являются полностью статичными - альфа-частицы, переворачивающие биты в микросхемах памяти, в конечном итоге должны привести к успешной сортировке. Другими словами, если микросхема полупроводниковой памяти сталкивается с ионизирующей частицей, возможно, что состояние микросхемы изменится, и, таким образом, изменятся данные. Теоретически, достаточное количество этих событий должно привести к сортировке данных.

Интеллектуальная сортировка по дизайну

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

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

Как ни странно, Intelligent Design Sort очень эффективен и ужасно неэффективен. По собственным стандартам, он полностью оптимален, занимает время O (1) и выполняет сортировку на месте, поэтому не требует дополнительного выделения памяти. Однако по нашим собственным стандартам сортировки на это требуется время O (∞), поскольку неупорядоченные наборы данных никогда не будут отсортированы алгоритмом. Код для Intelligent Design Sort на самом деле вообще не был бы кодом. В конце концов, это зависит от высших существ. Мы, простые люди, ничего не знаем о том, что означает «отсортированный».

Эвереттовская сортировка (также известная как квантовый богосорт)

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

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

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

Это довольно круто. По крайней мере, мне так кажется.