Формулировка сортировки списка как чисто математической задачи

Существует несколько математических исследований алгоритмов сортировки, начиная с библии Кнута [3] по этой теме. Справочник [2] также предлагает строгий подход к алгоритмам и дает ряд ссылок.

Я не буду пытаться резюмировать в нескольких строках 790 страниц тома Кнута, но вот некоторые моменты, которые следует учитывать при математическом подходе к сортировке.

1. Вам дан полностью упорядоченный$n$-набор элементов$S = \{a_1 < a_2 < \ldots < a_n\}$. Первоначально массив, который нужно отсортировать,$(a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)})$, где$\sigma$является перестановкой$\{1, \ldots, n\}$.
2. Обычно сложность (время) измеряет количество сравнений, необходимых для сортировки массива. Никакие другие параметры не учитываются. Таким образом, сравнения вида «есть$a < b$?" - единственные рассматриваемые базовые операции. Таким образом, проблема полностью не зависит от реализации.
3. Существует несколько показателей сложности, включая временную сложность (включая временную сложность в худшем случае ), среднюю временную сложность , пространственную сложность (которая измеряет объем памяти, используемый вашим алгоритмом), не говоря уже о более поздней амортизированной вычислительной сложности . В вашем вопросе вас, кажется, интересует наихудшая временная сложность.
4. [EDIT] Минимальное количество сравнений , необходимое для сортировки$n$элементами является последовательность OEIS A036604 . См. [4] для недавнего вклада по этой теме.

В комментарии вы утверждаете, что

если список представляет собой массив чисел в памяти компьютера, перемещение элемента в позицию$j$в положение$i$требует перемещения большого количества данных в памяти (поскольку многие элементы в массиве должны быть сдвинуты на одну позицию).

Это неправда. Например, вы можете поиграться с указателями в C (или ссылками в Java). Кроме того, ряд алгоритмов сортировки основан на перестановке двух позиций.$i$и$j$, который не нуждается ни в каком сдвиге. Чтобы ознакомиться с алгоритмами, [1] является одним из стандартных справочников, но есть и много других.

[1] Кормен, Томас Х., Лейзерсон, Чарльз Э., Ривест, Рональд Л. и Стейн, Клиффорд. Введение в алгоритмы. Третье издание. MIT Press, Кембридж, Массачусетс, 2009. xx+1292 стр. ISBN: 978-0-262-03384-8

[2] Гоннет, Гастон Х. и Баеза-Йейтс, Р., Справочник по алгоритмам и структурам данных . 2-е изд. (английский) Международная серия компьютерных наук. Бонн и др.: Издательство Addison-Wesley Publishing Company. XIV, 424 с. (1989).

[3] Кнут, Дональд Э. Искусство компьютерного программирования . Том. 3. Сортировка и поиск . Второе издание. Аддисон-Уэсли, Рединг, Массачусетс, 1998. xiv+780

[4] Печарски, Марцин (3 августа 2011 г.). На пути к оптимальной сортировке 16 элементов . Acta Universitatis Sapientiae 4 (2): 215–224.

Общие проблемы с определением алгоритмов на основе сравнения как чисто математической задачи

Ознакомьтесь с обсуждениями алгоритмов, основанных на сравнении (класс алгоритмов, включающий большинство алгоритмов сортировки) [0]. Это хорошая отправная точка для формализации, хотя определение этих алгоритмов в литературе остается слишком расплывчатым, чтобы удовлетворить чистого математика.

Ответ на ваш вопрос о том, что представляет собой алгоритм и каковы его основные операции, вы найдете в [0] и [4]. Для императивных языков программирования базовыми операциями обычно являются операции более низкого уровня, выполняемые конструкциями более высокого уровня (такими как циклы, условные операторы и т. д.). Их можно указать с самого начала при указании языка.

Распространенное «определение» состоит в том, что алгоритмы, основанные на сравнении, — это алгоритмы, для которых каждая базовая операция (перестановка, присвоение и т. д.) должна основываться на предшествующем сравнении (или последовательности сравнений). В этом определении алгоритмов, основанных на сравнении, есть пробел. (не единственный) Что действительно важно, так это то, что основные операции определяются на основе транзитивного замыкания результатов предшествующих сравнений.

Второй вопрос, на который следует обратить внимание, — это взаимосвязь между алгоритмами, основанными на сравнении, и производством частичного заказа (это поможет ответить на ваш вопрос о нижних границах). Это редко прописано в учебниках. Производство частичного порядка — это (среди прочего) подход к установлению более общих нижних границ для алгоритмов, основанных на сравнении, которые не обязательно должны быть алгоритмами сортировки[1]. Производство частичного порядка включает топологическую модель сортировки, обсуждаемую ниже.

Третьей проблемой (для математиков) является спецификация задействованных операций. Самой подробной презентацией будет третий том Кнута о сортировке и поиске (The Art of Computer Programming, Vol III), превосходный ресурс, уже упомянутый ранее. Даже при таком уровне точности чистый математик захочет абстрагироваться от деталей, что само по себе является проблемой. См. ниже противоречие между кодом и математикой.

Четвертая проблема — различие между неявными структурами данных [2] и явными. Для сортировки кучи обычно используется структура данных списка (массива). Однако неявная структура данных — это структура кучи, которая находится в уме программиста при написании кода, даже если структуры данных кучи не используются в коде явно (используются только массивы).

Наконец, существует статус анализа алгоритмов в целом, который остается смесью чистой и прикладной математики. Многие методики приспособлены к рассматриваемому алгоритму. Единого подхода нет. TAOCP Vol III Кнута будет содержать самую подробную информацию о формальном подходе (будь то с методами, адаптированными к различным алгоритмам). Работу Флажоле по анализу алгоритмов можно рассматривать как путь к унификации (хотя операции, используемые время от времени, отклоняются от широко используемых операций в информатике, чтобы гарантировать возможность применения производящих функций. Это, как всегда, создает напряженность между информатикой и математикой из-за код, чтобы соответствовать математике). Я написал книгу на эту тему, посвященную объединяющей теории, оставаясь ближе к стандартным вычислениям [3].

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

Похоже, ваши вопросы также относятся к тому, что происходит на аппаратном уровне. Я бы рекомендовал A Guide to Experimental Algorithmics [4]. Эта область находится на полпути между чисто экспериментальным алгоритмическим анализом (слишком машинно-зависимым) и теоретическим анализом (машинно-независимым, но в некоторых отношениях слишком далеким от практики). Он использует методы, аналогичные контролируемой лабораторной среде в области компьютерных наук.

Приведенные выше наброски показывают, почему формальное определение алгоритмов, основанных на сравнении, является сложной задачей. Это может быть сделано. Например, [3] делает это для ограниченного класса (специально направленного на реализацию модульной синхронизации в среднем случае). [1] считает, что все алгоритмы, основанные на сравнении, имеют вычисления, которые (для списков фиксированного размера$n$) можно смоделировать с помощью деревьев решений. Следовательно, [1] придерживается мнения, что алгоритмы отождествляются с деревьями (т. е. алгоритмы для производства частичного порядка в [1] просто считаются деревьями решений с определенными свойствами). Как только этот скачок сделан, возникает чисто математический контекст, основанный на деревьях решений и топологических сортировках. Он обходит ваш вопрос формальной структурой, в которой общие вычисления, основанные на сравнении, формулируются таким образом, который удовлетворяет чистого математика (или, скажем, теоретика-компьютерщика). Я считаю, что это, безусловно, можно сделать, т. е. должна существовать логика, в которой фиксируются вычисления, основанные на сравнении. Я не знаю ссылки, которая делает это (и было бы интересно, если бы у кого-нибудь она была).

Отправная точка для решения чисто математической формулировки [1,3,5]

Следующий подход можно рассматривать как чисто математическую постановку задачи. Это связано с подходом Яо в ​​[1], а также с подходом в [3], где оба используют топологическую сортировку для моделирования вычислений на основе сравнения. Вместо того, чтобы сосредотачиваться на коде, основное внимание уделяется функциям ввода-вывода, связанным с выполняемыми операциями. в коде (подход в стиле семантики).

Правило взаимодействия дизайнера: транзитивное закрытие

Общее определение алгоритмов, основанных на сравнении, заключается в том, что каждая базовая операция (перестановка, присвоение и т. д.) должна основываться на предшествующем сравнении или последовательности сравнений. В этом определении есть досадный пробел. Что действительно важно, так это то, что основные операции определяются на основе транзитивного замыкания результатов предшествующих сравнений. Позволять$k \geq 2$.

Для алгоритма сортировки, такого как пузырьковая сортировка, каждый обмен между элементами списка является прямым результатом сравнения между этими двумя элементами. Для быстрой сортировки два элемента$a, b$можно сравнить с поворотным элементом$p$, и может быть заменен на том основании, что$a > p$и$p > b$Несмотря на то$a$и$b$никогда не сравнивались напрямую. Обмен выполняется на основе транзитивного замыкания информации, полученной при упорядочении элементов до этой точки вычисления. На этом этапе вычислений разработчик алгоритма знает все отношения порядка между сравниваемыми парами меток, а также любые законно выведенные отношения порядка, т.е. полученные посредством транзитивного замыкания. Именно этот набор отношений, и только этот набор, поддерживает решения разработчика о включении выполнения основных кодовых операций.

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

Обратите внимание, что от дизайнера не требуется, чтобы свопы соответствовали заданному порядку. Разработчик должен убедиться, что алгоритм выдает правильные результаты. Приблизят ли выполненные свопы алгоритм к этой цели или нет — это решение, которое должно быть принято, но не решение, которое навязывается. Единственное требование состоит в том, чтобы в конце был достигнут «целевой» порядок (указанный как часть спецификаций алгоритма). Чтобы установить целевой порядок, который должен быть достигнут в конце, вводится модель топологической сортировки.

Фильтрация информации о заказе и соответствующая перестановка данных

Каждое сравнение, сделанное во время вычисления на основе сравнения, определяет, встречаются ли две метки по порядку или не по порядку . Каждое сравнение отфильтровывает один дополнительный бит информации о данных: 0 для неупорядоченной пары и 1 для правильной пары.

Когда сравнение было сделано между двумя ярлыками$a$и$b$установив, что$a \leq b$в линейном порядке по меткам мы ссылаемся на пару$(a,b)$как отфильтрованная пара . В случае$a \geq b$установлено, мы ссылаемся на пару$(b,a)$как отфильтрованная пара .

Установленный порядок ввода

Для любого выполнения алгоритма сравнения на входе$I$и любое сравнение, сделанное в этом выполнении, установленный входной порядок (до этого момента вычисления) является частичным порядком, полученным путем транзитивно-рефлексивного закрытия отфильтрованных пар, полученных во время вычисления до этого сравнения включительно.

Порядок ввода — это частичный порядок ввода, достигнутый при производстве вывода для$I$, т.е. установленный порядок ввода для последнего сделанного сравнения.

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

Алгоритмы на основе сравнения выполняются:

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

Процесс фильтрации

Процесс фильтрации неявным образом собирает дополнительную информацию о линейном порядке входных данных на метках. Эта информация фиксируется установленным порядком ввода. Процесс фильтрации также разделяет входные данные на наборы, удовлетворяющие установленному порядку ввода.

Рассмотрите любую сортировку на основе сравнения и любой входной список$L$размера$n$хранение, для простоты, отдельных элементов. После первого сравнения определяется порядок между двумя элементами списка.$L[i]$и$L[j]$с$i < j$, возможные входы, для которых будет принято это решение, уменьшаются вдвое (от$n!$к$\frac{n!}{2}$списки). Эти входные данные теперь относятся только к спискам, для которых$L[i]< L[j]$если это был результат сравнения, или списки, для которых$L[j] > L[i]$в противном случае.

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

Процесс фильтрации входных данных, не удовлетворяющих установленному порядку, является неявным. Это не часть кода. Однако это часть задуманного программистом проекта алгоритма.

Процесс перестановки

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

После каждого сравнения каждый алгоритм сортировки на основе сравнения имеет возможность переставлять метки данных, чтобы соответствовать предполагаемому порядку сортировки выходных списков. Например, если перечислены элементы$L[i]$и$L[j]$определяются как происходящие не по порядку с помощью сортировки на основе сравнения, т.е.$L[j]> L[i]$где$i<j$, то можно произвести замену, чтобы установить их относительный порядок, соответствующий вычисляемому отсортированному выводу.

Для любой сортировки на основе сравнения объединенный процесс фильтрации ввода и перестановки ввода имеет следующий эффект:

• К моменту вычисления выходных данных возможные входные данные были отфильтрованы до единого списка.

• Процесс перестановки, выполняемый алгоритмом на этом входе, т. е. составление набора свопов, выполненных до этой точки на входе, дает отсортированный результат.

Это естественным образом приводит к следующей математической модели, фиксирующей «исходный» и «целевой» порядки для вычислений на основе сравнения.

Модель топологической сортировки

Математическая модель

Математическая модель алгоритмов сравнения [1] и [3] состоит из двух частей:

(а) моделирование структур данных как частично упорядоченных конечных множеств;

(б) моделирование данных о них по топологическим сортам;

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

Пример 1: (неупорядоченные) входные списки размера 2 алгоритма сортировки моделируются топологическими сортировками дискретного порядка размера 2 по набору элементов$\{x_1,x_2\}$:

$$\{(x_1: 1,x_2:2),(x_1:2,x_2:1)\}$$

Значения функции$s(x_1) = 2$и$s(x_2) = 1$скажем, топологического типа$s = (x_1:2,x_2:1)$(по дискретному порядку размера 2) называются метками и соответствуют, в случае структуры данных списка, элементам списка. Местонахождение$i$этикетки$a$для которого$s(x_i) = a$называется индексом метки и соответствует положению элемента в списке. Список$(2,1)$содержит элемент 2 в позиции 1 (т.е. индекс$x_1$) и элемент 1 в позиции 2 (т.е. индекс$x_2$). Мы говорим, что индекс метки 2 равен 1, а индекс метки 1 равен 2 для этой топологической сортировки. 2! топологические сорта$\{(x_1: 1,x_2:2),(x_1:2,x_2:1)\}$состоят из 2 перестановок, представляющих неупорядоченные списки$(1,2)$и$(2,1)$. Эти топологические сортировки формируют корневые состояния, в которых могут встречаться списки размера 2 (с различными элементами). Действительно, список размера 2 либо отсортирован, представлен$(1,2)$, или отсортированный в обратном порядке, представленный$(2,1)$. Вместе эти топологические сорта образуют пространство состояний . Пространство состояний интуитивно служит для представления равномерного распределения по данным: каждый из бесконечного множества возможных входных списков$(a,b)$Предполагается, что размер 2 (с различными элементами) возникает с равной вероятностью в одном из двух корневых состояний пространства состояний. Эта интерпретация служит основой для традиционного анализа сложности алгоритмов, отправной точкой которого является равномерное распределение.

Пример 2: Тривиальная сортировка списков размера 2

Вычисления преобразуют топологические сортировки в новые топологические сортировки. Все расчеты будут основаны на сравнениях. Например, рассмотрим алгоритм сортировки, пусть даже очень примитивный, который работает только со списками размера 2 и выполняет однократное сравнение двух элементов списка (меток соответствующей топологической сортировки). За этим сравнением следует замена меток в случае, если эти метки вышли из строя. Такой алгоритм оставляет топологическую сортировку$(x_1: 1,x_2:2)$без изменений и преобразовать топологическую сортировку$(x_1:2,x_2:1)$через один своп на топологическую сортировку$(x_1:1,x_2:2)$. Сортировка в этой модели производит уникальную топологическую сортировку в линейном порядке.

Часть (а) описания модели предусматривает, что мы используем конечные частичные порядки для представления структур данных. Этот порядок может быть явно или неявно представлен в структуре выходных данных в зависимости от реализации. Например, в случае формирования кучи из неупорядоченного входного списка вычисление может установить кучу явно путем преобразования входного списка в структуру данных двоичного дерева, удовлетворяющую свойству кучи, и представляет собой кучу де-факто. В качестве альтернативы алгоритм может взять входной список и сохранить структуру данных списка для своих выходов. Элементы входного списка будут реорганизованы на месте, то есть будет создан новый список, элементы которого удовлетворяют структуре кучи. Древовидная структура, лежащая в основе этой кучи, остается «неявной» частью реализации. Алгоритм для всех целей использует структуру кучи, задуманную программистом, но структура данных всегда остается списком во время вычислений. это, например, случай для процесса Heapify в традиционной (на месте) Heapsort. В этом случае мы называем структуру кучи неявной структурой данных , а структуру данных списка — явной структурой данных . Они могут совпадать или не зависеть В нашем контексте частичные заказы моделируют неявную структуру данных.

Базовый пример вычислительной модели: алгоритмы сортировки

Мы иллюстрируем (a), (b) модели алгоритма сортировки, работающего со списками размера$n$.

Для алгоритмов сортировки входными данными являются структуры данных списка, представленные конечными дискретными порядками. Элементы порядка помечены положительными целыми числами, взятыми из линейно упорядоченного набора меток.$\mathcal{L}$, что в данном случае является обычным линейным порядком положительных целых чисел. Единственное требование к этой маркировке состоит в том, что ее комбинация с дискретным порядком образует топологический сорт.

Можно работать со списками, содержащими повторяющиеся элементы. Они должны быть смоделированы топологическими сортировками, для которых условия смягчены, чтобы можно было повторять метки. См. [3] для обсуждения того, как повторяющиеся метки могут быть обработаны посредством назначения случайных прерывателей связи. Стандартной практикой в ​​алгоритмическом анализе является проведение анализа в первую очередь для списков без повторяющихся элементов — подход, принятый здесь.

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

Алгоритмы сортировки представляют собой ограничительный тип алгоритма, основанного на сравнении. Входные данные представляют собой неупорядоченные списки размера$n$которые происходят в$n!$возможные состояния. Выходы происходят ровно в одном состоянии, отсортированный список выходов$[1,2, 3, \ldots, n]$.

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

Источник и цель алгоритма

Рассмотрим последовательность$\alpha = (\alpha_n)_n$конечных частично-множественных множеств размера$n$и последовательность$\beta= (\beta_n)_n$уточнений$(\alpha_n)_n$, т.е.$\alpha_n$уточняет порядок$\beta_n$для каждого$n$. Пара$(\alpha,\beta)$называется уточнением с источником $\alpha =(\alpha_n)_n$и цель $\beta = (\beta_n)_n$.

Алгоритм$A$ осуществляет уточнение $(\alpha,\beta)$в случае:

входы размера$n$, рассматриваемые как множество, образуют пространство состояний над исходным порядком$\alpha$. Напомним, что для любого конечного ч.у.м.$\alpha$, пространство состояний$\Sigma(\alpha)$множество всех топологических сортов с метками в$\{1,\ldots,n\}$где$n = |\alpha|$.

соответствующие выходы, рассматриваемые как набор, образуют пространство состояний$\Sigma(\beta_n)$.

$\Sigma(\alpha_n)$называется исходным пространством (для входных данных размером$n$).

$\Sigma(\beta_n)$называется целевым пространством (для входных данных размера$n$).

С некоторым злоупотреблением терминологией: если$\alpha = (\alpha_n)_n$является источником такого алгоритма, основанного на сравнении$A$и мы рассматриваем входы размера$n$, затем$\alpha_n$также упоминается как «источник».

Алгоритм на основе сравнения можно рассматривать как алгоритм, который выполняет основные операции исключительно на основе транзитивного закрытия предыдущих сравнений, фильтрации и перестановки на каждом этапе, так что для данного источника$\alpha$и цель переработки$\beta$, алгоритм реализует уточнение. В качестве альтернативы можно абстрагироваться от кода и полностью сосредоточиться на деревьях решений [1].

Пример: для алгоритма сортировки на основе сравнения$A$источник - это последовательность$\Delta = (\Delta_n)_n$дискретных порядков размера$n$и целью является последовательность$L = (L_n)_n$линейных порядков размера$n$.

Для основанного на сравнении алгоритма heapify, который преобразует неупорядоченные списки размера$n$к кучам, источником является последовательность дискретных порядков$\Delta = (\Delta_n)_n$. Целью является последовательность$H = (H_n)_n$где$H_n$является помножеством, определяемым диаграммой Хассе кучи размера$n$.

Модель топологической сортировки поддерживает нижние границы сложности для общих алгоритмов, основанных на сравнении (т. е. алгоритмов, которые не обязательно должны быть сортировками).

Энтропийное отношение

Если$A$представляет собой основанный на сравнении алгоритм с входными данными размера$n$происходит$k$состояния и выходы, происходящие в$l$состояния, то исходная энтропия (т.е. входная энтропия)$H^{s}_{A}(n) = log_2{k}$и целевая энтропия$H^{t}_{A}(n) = log_2(l)$.

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

Рассмотрим алгоритм, основанный на сравнении$A$с входами с корневыми состояниями над источником$\alpha_n$и выводит с корневыми состояниями над целью$\beta_n$. Позволять$k = |\Sigma(\alpha_n)|$обозначают размер исходного пространства и$l = |\Sigma(\beta_n)|$размер целевого пространства.

Коэффициент энтропии - это разница между исходной и целевой энтропиями, обозначаемая как$\Delta H_{A}$:

$$\Delta H_{A}(n) = H^{s}_{A} (n)- H^{t}_{A}(n) = log_{2}(\frac{k}{l})$$ в$log_2$отношения размера исходного пространства к размеру целевого пространства.

Теорема (см. [1], [5]) (нижняя граница ER): рассмотрим алгоритм, основанный на сравнении$A$с источником$\alpha$и цель$\beta$, а с входами$A$размера$n$происходит в$k$корневые состояния и выходы, происходящие в$l$корневые состояния, т.е.$A$имеет коэффициент энтропии$\Delta H_{A} = log_2{\frac{k}{l}}$.

Следующие нижние границы времени сравнения в наихудшем и среднем случаях справедливы для каждого алгоритма, основанного на сравнении.$A$такого характера:

$$T^{W}_{A}(n) \geq \Delta H_{A} \mbox{ and }\overline{T}_{A}(n) \geq \Delta H_{A}$$

Нижняя граница для алгоритмов сортировки на основе сравнения$A$

Нижняя граница

$$\Delta H_{A}(n) = log_{2}(\frac{n!}{1}) =log_2(n!)$$ ER в этом случае представляет собой обычную теоретико-информационную нижнюю границу, т. е. энтропию входных данных, обеспечивающую нижнюю границу для наихудшего и среднего времени.

Нижняя граница для построения идеальных куч размера$7$Рассмотрим алгоритм, основанный на сравнении$H^{*}$построение идеальных куч из неупорядоченных списков размера$7$. Есть$\frac{7!}{63}$идеальные кучи размера$7$. Следовательно

$$\Delta H_{H^{*}}(7) = log_{2}(\frac{7!}{\frac{7!}{63}}) = 63$$

Модель топологической сортировки из [1] является наиболее близким подходом к чисто математической постановке задачи для вычислений на основе сравнения. Он не углубляется в синтаксис (код) алгоритмов, но идентифицирует алгоритмы, основанные на сравнении, с деревьями решений, моделирующими пути их вычислений.

[0] Искусство компьютерного программирования, Том III, Сортировка и поиск, Д. Кнут, Аддисон-Уэсли, 1998.

[1] О сложности продукции частичного порядка, Эндрю Чи-Чи Яо, SIAM J. COMPUT. Том. 18, № 4, стр. 679-689, Общество промышленной и прикладной математики, 1989.

[2] Манро, Дж. Ян; Суванда, Хендра; «Неявные структуры данных для быстрого поиска и обновления». Журнал компьютерных и системных наук. 21 (2): 236–250, 1980.

[3] Шеллекенс, М.; Модульное исчисление средней стоимости структурирования данных, 2008 г.

[4] МакГеог, Кэтрин С.; Руководство по экспериментальной алгоритмике, CUP. 2012.

[5] Schonhage, A. (1976), Производство посетов, Asterisque 38-39:229-246.

Сортировки сравнения часто определяются без ссылки на алгоритмы.

Определение : сортировка сравнением$n$elements представляет собой корневое двоичное дерево, в котором

• каждый узел$v$помечен набором перестановок$P(v) ⊆ S_n$,
• каждый внутренний узел$v$помечен парой различных индексов$1 ≤ i_v < j_v ≤ n$,
• для корневого узла$v$, у нас есть$P(v) = S_n$,
• для любого листового узла$v$, у нас есть$|P(v)| ≤ 1$,
• для любого внутреннего узла$v$, его левый и правый потомки$v_<$и$v_>$удовлетворить $$P(v_<) = \{σ ∈ P(v) \mid σ_{i_v} < σ_{j_v}\}, \quad P(v_>) = \{σ ∈ P(v) \mid σ_{i_v} > σ_{j_v}\}.$$

Например, вот сравнительная сортировка по 3 элементам:

(Вы можете — но не обязаны — думать о сортировке сравнением как о дереве решений алгоритма, где на каждом шаге$P(v)$представляет набор возможных порядков; алгоритм выбирает индексы$i_v$и$j_v$и сравнивает элементы по этим индексам, чтобы сузить набор возможностей.)

Теорема: высота любой сортировки сравнением на$n$элементы$Ω(n \lg n)$.

Доказательство: бинарное дерево высоты$h$имеет не более$2^h$листья, но сортировка сравнением имеет по крайней мере$n!$, так$h ≥ \lg n! = Ω(n \lg n)$. ∎

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

Defn: Пусть набор$A = \{ a_i \}_{0 \le i \le n}$. Позволять$\sigma: A \rightarrow A$быть отсортированной по возрастанию картой, такой что$\sigma(a_i)=a_k$со следующим ограничением

1. Если$i < j$затем$\sigma(a_i) \le \sigma(a_j)$(возрастающая карта)
2. Пусть «карты алгоритмов» будут семейством функций$f_{t}: \{[0,1], \sigma\} \rightarrow \{ A, B_t \cup \{a_{k+1}\}, B_1 \}$где$B_t = \{a_k\}_{k \le n} \subseteq A$такое, что... (1) выполняется для$B_t$и$\sigma(a_i) = a_i$если$i > k$.$f(0, \sigma) = A$,$f(1, \sigma) = B_1$и$k=n$. Вовремя$t$ $f(t, \sigma) = B_{t} \cup \{ a_{k+1} \}$и существует такой$k$и$B_t$.

Самая быстрая карта алгоритма$f_t$где$t$минимальна. Это не зависит от модели, такой как Тьюринг или ОЗУ и т. д. Это сродни определениям «ретракции деформации» из алгебраической топологии, например,

Тем не менее, я бы сказал, что в математике все еще есть некоторые «глаголы», такие как «вращение» или групповая операция, например, которые невольно вводят физический мир. ИМХО их должно быть как можно меньше