Что такое «Большой О»?

Он описывает асимптотический характер системы по мере роста входных данных. Обычно мы описываем время выполнения алгоритма, но его также можно использовать для описания космической сложности или даже систем за пределами области информатики. Здесь я предполагаю, что он описывает время выполнения алгоритма, если не указано иное. Асимптотический анализ означает, что вы сосредотачиваетесь на том, как время выполнения алгоритма растет по мере увеличения входных данных и приближения к бесконечности. Вход обычно обозначается как n. По мере того, как наши наборы данных становятся больше, именно функция роста будет доминирующим фактором времени выполнения. Например, O (n) предполагает, что среда выполнения изменяется линейно с вводом n. O (n ^ 2) предполагает, что время выполнения изменяется пропорционально размеру входного квадрата. Для больших наборов данных обычно достаточно информации, чтобы сказать вам, какой из них будет быстрее.

Когда вы анализируете асимптотические характеристики функции, вы хотите дисконтировать добавленные константы, а также коэффициенты отбрасывания и члены более низкого порядка. Например, f (n) = 100 * n * lg (n) + n + 10000 описывается как O (n * lg (n)), потому что, когда n стремится к бесконечности, константа и коэффициент становятся несущественными. Посмотрите на эти графики:

Как вы можете видеть, в небольших наборах данных большая нотация O может не рассказать всей истории, но даже переход от 50 до 500 точек данных на приведенном выше графике заставил асимптотический характер функций взять верх.

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

Хотя кажется, что в просторечии «большой-О» используется для обозначения асимптотической среды выполнения, которая описывает «жесткую асимптотику» функции (т.е. описывает как верхнюю, так и нижнюю границы), на самом деле это неточно. Формальные определения асимптотической среды выполнения кратко описаны ниже [1]:

Большой ϴ (тета):

Формально для ϴ (g (n)) для описания функции f (n) существуют положительные константы c1, c2 и n_o такие, что 0 <= c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n_o

Чтобы уточнить: представьте, что у вас есть алгоритм, который определяется сложным уравнением f (n). Вы можете охарактеризовать f (n) в нотации big-theta с помощью очень простого уравнения g (n), в котором отброшены все константы, коэффициенты и члены более низкого порядка, ЕСЛИ вы можете повторно добавить 2 произвольные константы к g (n), которые могут «Сэндвич» исходного уравнения f (n) с определенным размером входных данных n_o.

Пример: допустим, ваше f (n) = 100*n^2 + 4*n*lg(n). Мы можем показать, что n ^ 2 может соответствовать этому определению с помощью следующих уравнений и графика

Теперь, если мы попытаемся совместить нашу f (n) с nlgn, мы увидим, что верхняя граница неизбежно переходит f (n) по мере роста n, независимо от константы, которую мы установили:

Итак, технически каждый раз, когда я называл функцию big-O выше, я должен был сказать, что это big-theta, то есть ϴ (n) вместо O (n).

Big-O:

Big-O обеспечивает только асимптотическую верхнюю границу в отличие от верхней и нижней границы, обеспечиваемой обозначением ϴ. Формально для O (g (n)) для описания функции f (n) существуют положительные константы c и n_o такие, что 0 <= f(n) <= c*g(n) for all n >= n_0

Итак, на самом деле правильно сказать, что алгоритм, определенный f(n) = 3*n + 100, равен O (n ^ 3), даже если это ϴ (n).

Также существуют другие менее используемые обозначения, определенные аналогично приведенным выше:

  • Запись Ω (big-omega) определяет только асимптотическую нижнюю границу
  • Обозначение o (little-o) определяет верхнюю границу, которая НЕ является асимптотически жесткой (например, в приведенном выше примере, где мы описываем функцию ϴ (n) как O (n³) - это асимптотически непостоянное определение, и вы могли бы, следовательно, , скажем, это тоже o (n³). o (n) было бы неверно)
  • Обозначение ω (мало-омега) определяет нижнюю границу, которая НЕ должна быть асимптотически точной.

При описании алгоритмов чаще всего используется понятие ϴ-нотации, и оно обычно передается как O-нотация.

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

  1. Легче рассчитать время выполнения для наихудшего случая, чем среднее время выполнения (меньшее количество факторов, которые необходимо учитывать)
  2. Анализ наихудшего случая - гарантия того, что мы никогда больше не будем
  3. Нередко наихудший сценарий часто случается при реализации.

Оказывается, lgn (сокращение от log base 2 of n) важен для многих дискуссий во время выполнения. Быстрый обзор логарифмов:

Логарифм описывает, до какой степени необходимо довести базу, чтобы создать определенное число. Например, поскольку наша база равна 2, если мы хотим найти lg (8), мы спрашиваем себя: «В какой степени я могу взять 2, чтобы получить ответ 8?». В этом случае, поскольку мы знаем, что 2³ равно 8, мы знаем, что lg (8) = 3. Вы как бы «разбираете» экспоненту. Это важная концепция, потому что, если мы можем создать алгоритм, определяемый журналом, он будет расти очень медленно! На самом деле он растет так же медленно, как быстро растут экспоненты, а это много.

Представьте, что у вас есть набор данных размером 262144, и вы выполняете алгоритм со средой выполнения f (n) = n. Если набор данных вырастет до 524288, вы выполните еще 262144 операции! Но если ваш f (n) = n², вы выполняете БОЛЬШЕ операций на 68719476736! Если ваш f (n) = lg (n), вы выполняете еще 1 операцию. Если ваш f (n) = lg (n), каждый раз, когда ваш набор данных удваивается, вы выполняете 1 дополнительную операцию.

Почему это важно?

Когда вы работаете с большим набором данных или набором данных, который может увеличиваться по мере того, как вы набираете пользователей или собираете дополнительную информацию, время выполнения будет определяться его асимптотическим ростом. Как описано выше, константы, коэффициенты и члены более низкого порядка имеют относительно меньшее значение по сравнению с компонентом высшего порядка. Разница между алгоритмом O (n * lg (n)) и алгоритмом O (n²) может легко отличать хорошо работающее приложение от абсолютно непригодного для использования.

Как вы практически используете O-нотацию?

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

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

  • Просмотрите свои петли. Если вы выполняете итерацию по коллекции один раз, у вас, скорее всего, есть алгоритм ϴ (n). Если у вашего цикла есть внутренний цикл, который повторяет все ваши данные (или n-1 каждый раз), у вас, скорее всего, есть алгоритм ϴ (n²), что очень опасно.
  • Поймите «закулисный» код, который возникает, когда вы вызываете функцию, которую вы не писали сами или которая является родной для языка. Может быть более подходящий способ сделать что-то, и непонимание сути вызываемых вами методов может очень затруднить оптимизацию.
  • Просмотрите свой код на предмет функций, связанных с размером входных данных, и не обращайте внимания на константы или повторение этого кода, которые не зависят от размера данных. Это поможет вам легче определить свой ϴ (g (n))

Примите мышление разделяй и властвуй

Разделай и властвуй состоит из следующих шагов:

  1. Разделите проблему на более мелкие
  2. Решайте подзадачи рекурсивно, пока они не станут достаточно маленькими, чтобы найти простое решение.
  3. Объедините решения подзадач, чтобы создать общее решение.

По сути, если вы можете продолжать делить свою проблему на равные половины (что обычно является точкой разделения), пока она не станет достаточно маленькой, чтобы ее было легко решить. Затем вы сможете решить эту небольшую простую задачу и объединить эти простые ответы в полный ответ. Вполне возможно, что вы только что изменили свой алгоритм с времени выполнения ϴ (n²) на ϴ (nlgn).

Причина, по которой происходит это преобразование, заключается в том, что если вы разбиваете свой код на равные половины, вы можете сделать это деление lgn раз (т.е. сколько раз я могу умножить на 2, чтобы получить размер данных n?). Каждый раз, когда вы делите свою проблему на 2, мы перебираем наши данные, чтобы что-то с ней сделать, отсюда n * lgn. Примеры этого будут показаны в приведенных ниже алгоритмах сортировки.

Сортировка

Это простое приложение с большой буквой O, и каждый программист должен иметь базовые представления о нем.

Почему это важно?

Большинство языков имеют встроенные алгоритмы сортировки, но все же важно понимать, как работает сортировка. Почему?

  1. У него много важных вариантов использования. Возможно, самым большим применением является увеличение скорости поиска по массиву с O (n) до O (lgn) - огромное улучшение. (т.е. возможность использовать бинарный поиск). Кроме того, довольно распространена доставка данных пользователю в определенном формате (от высокой до низкой). Также обычно приходится манипулировать данными в зависимости от их местоположения в отсортированном списке (т. Е. Отображать самые последние сообщения).
  2. Об этом спрашивают в технических интервью
  3. Алгоритмы сортировки могут иметь существенно разное время выполнения в зависимости от данных, на которых они выполняются. Хотя многие заданные алгоритмы сортировки довольно хорошо работают с большинством данных, важно знать, какие различные алгоритмы могут работать лучше для вашего варианта использования. Возможно, это не лучший выбор - просто использовать стандартный алгоритм сортировки языка.
  4. Наконец, и, возможно, самое главное, это поможет вам понять, почему так важна большая буква O и как решать проблемы более элегантно, чем решение методом грубой силы.

Как можно запрограммировать алгоритм сортировки, с какой временной сложностью?

Заявление об ограничении ответственности:

Эти примеры ориентированы на временную сложность, и пространственная сложность не принимается во внимание.

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

Алгоритмы

Пузырьковая сортировка

Характеристики

  • ϴ (n²) наихудший и средний случай
  • // → Обратите внимание на вложенные циклы, указывающие время выполнения ϴ (n²)
  • ϴ (n) лучший случай

Описание

  • Пройдитесь по списку, проверяя каждый элемент с соседним с ним элементом. Поменяйте их местами, если они вышли из строя. Повторяйте это, пока все не поменяете местами. В качестве оптимизации вы можете каждый раз перебирать n минус i элементов, где i - это количество уже выполненных итераций. Это связано с тем, что после первой развертки вы гарантировали, что наименьшее число «выскочило» вверх (или наибольшее число упало вниз, в зависимости от направления вашей итерации), поэтому вам нужно только проверить индексы ниже (выше).

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

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

Вставка сортировки

Характеристики:

  • ϴ (n²) наихудший и средний случай.
  • ϴ (n) лучший случай
  • Этот лучший сценарий происходит, когда список уже отсортирован (или очень близок к сортировке).

Описание:

  • Представьте, что ваша коллекция разбита на две части. Самый дальний индекс слева (то есть индекс 0) - это «отсортированный массив» из одного элемента. Остальной массив представляет собой несортированный беспорядок. Мы можем идти один за другим в нашу несортированную правую часть и правильно вставлять этот элемент в левую часть массива, чтобы сохранить отсортированную левую сторону и чтобы отсортированная сторона увеличивалась на единицу. К тому времени, когда мы дойдем до конца массива, вся левая часть (то есть весь массив) будет отсортирована.
  • Это ϴ (n²), потому что для каждого индекса на нашей несортированной стороне мы должны искать его правильное местоположение на отсортированной стороне. Не только это, но мы должны перемещать каждый элемент по пути, чтобы освободить место для нашей вставки, что также является дорогостоящим.
  • // → Важно отметить как количество сравнений, так и количество свопов.
  • // → Для каждого индекса в правой части массива мы ищем от 1 до n других элементов в левой части для правильной позиции вставки. Суммирование от 1 до n имеет порядок ϴ (n ^ 2).

Мы можем оценить этот алгоритм с помощью «инварианта цикла»:

Инвариант цикла - это способ доказать правильность алгоритма, выполняющего повторяющиеся задачи. Чтобы сделать это правильно, мы должны показать оператор инварианта цикла (LI) правильный для:

  • Инициализация - ваш оператор LI верен до первого цикла
  • Обслуживание - ваш оператор LI верен на протяжении каждого последующего цикла
  • Завершение - ваш оператор LI находится в конце программы и дает возможность «доказать» правильность вашего алгоритма.

В этом случае можно указать инвариант цикла (перефразированный из [1]): «В начале каждой итерации нашего цикла for подмассив от 0 до j-1 (включительно) состоит из элементов, изначально находящихся в этом диапазоне индексы, но теперь в отсортированном порядке »

  • Инициализация: поскольку левая часть представляет собой единственный элемент (т. е. от 0 до j = 1–1 = 0 включительно), он сортируется по определению.
  • Обслуживание: каждый раз при выполнении цикла вы вставляете элемент с неотсортированной стороны в правильное положение на отсортированной стороне. Затем вы обновляете свои индексы, чтобы знать, где находится этот разрыв. Ваша отсортированная сторона больше на единицу и все еще отсортирована. Перед циклом и после цикла подмассив от 0 до j-1 сортируется, но в конце цикла j на одну единицу больше, чем раньше.
  • Завершение: ваш цикл завершается, когда j равно длине вашего массива минус 1. Итак, мы знаем, что массив от 0 до (длина массива - 1) включительно сортируется. Это каждый индекс в нашем массиве. Весь наш массив отсортирован.

Как вы увидите ниже, хотя в большинстве случаев сортировка вставкой выполняется очень медленно, она отлично справляется с сортировкой почти отсортированных данных.

Сортировка слиянием

Характеристики

  • ϴ (n * lgn) лучший случай, худший случай и средний случай

Описание

Алгоритм разделяй и властвуй:

  • Разделите задачу пополам, пока размер массива не станет равным 1.
  • Решите проблему сортировки, когда размер равен единице - это уже сделано за вас, потому что есть только один элемент. Это даст вам первый возврат из функции merge_sort вместо рекурсии. Этот возврат всегда будет отсортированным массивом (либо длиной 1, либо merged в отсортированный массив) и позволяет вам продолжить работу с алгоритмом, просто сохраняя «отсортированный» статус этих массивов, когда вы combine их.
  • Объедините ваши две меньшие половинки, которые имеют размер 1 (и отсортированы) вместе, путем сравнения, чтобы создать отсортированный массив длиной 2.
  • // → На один уровень выше рекурсия теперь будет иметь 2 массива размером 2, которые отсортированы. Объедините их вместе, чтобы создать новый отсортированный массив длиной 4, и так далее, пока весь ваш массив не будет отсортирован.

Инвариант цикла слияния [1] (ссылка на приведенный ниже код):

  • Оператор: в начале цикла while merged_arr будет содержать наименьшие (i + j) элементы из массивов left и right в отсортированном порядке. left[i] и right[j] будут содержать наименьшие числа в своих соответствующих массивах для индексов больше i и j соответственно.
  • Инициализация: merged_arr пусто, а i + j = 0. left и right - отсортированные массивы, поэтому оба их нулевых элемента будут наименьшими во всех массивах.
  • Обслуживание: меньшее из двух чисел из left[i] и right[j] добавляется в конец merged_arr. Поскольку оба массива находятся в отсортированном порядке, а i и j увеличиваются с 0, мы гарантируем, что каждая итерация цикла while учитывает только числа, добавляемые к merged_arr, которые больше или равны числам, уже добавленным к merged_arr, и меньше, чем или равно номерам более высокого индекса, остающимся в left и right. Это обеспечивает отсортированное состояние merged_arr. Когда элемент добавляется к merged_arr из left, только i увеличивается на 1, а когда элемент добавляется к merged_arr из right, только j увеличивается на 1. Это гарантирует, что merged_arr.length равно i + j, что значения merged_arr находятся в отсортированный порядок и следующие два числа left[i] и right[j] больше или равны всем числам в merged_arr и меньше или равны всем другим значениям, оставшимся в соответствующих массивах. IE, это два наименьших значения, которые могут предложить их массивы, которые еще не были помещены в merge_arr.
  • Завершение: цикл прерывается, когда один из массивов «пуст». Мы знаем, что в этот момент merged_arr находится в отсортированном порядке и имеет все значения расширенного массива и все значения другого массива до индекса i или j. Это завершение великолепно, но требует лишь небольшой очистки. Теперь вы должны поместить оставшуюся часть массива со значениями, оставшимися до конца merge_arr. Вы знаете, что можете просто вставить их в конец, потому что массив с оставшимися значениями уже отсортирован, а его наименьшее значение было определено как большее или равное наибольшему значению в другом массиве.

Обратите внимание, что иногда два «часовых» помещаются в конце left и right и получают значение бесконечности. Затем цикл while заменяется циклом for, который выполняется left.length + right.length - 2 раз, так что остаются только два бесконечных контрольных значения. В Ruby вы можете представить бесконечность с помощью Float::INFINITY, в Python float("inf"), в Javascript Infinity и в Java Double.POSITIVE_INFINITY.

Код (раскомментируйте, чтобы увидеть его в действии - это полезно, чтобы увидеть, как работает сортировка)

Быстрая сортировка

Характеристики

  • ϴ (n * lgn) лучший случай, средний случай
  • ϴ (n²) худший случай (когда почти отсортировано)
  • // → Если вы посмотрите на приведенный ниже код, вы увидите, что это связано с тем, что точка поворота в отсортированном случае разделяет проблему на два размера n -1 и 1 вместо n / 2 и n / 2. Для рандомизированного массива более вероятно, что значение точки поворота будет ближе к среднему значению. Подробнее об этом будет сказано ниже.

Описание

Разделяй и властвуй

  • Разделить. Выберите «точку поворота» в качестве последнего индекса в массиве. Итерируйте по массиву и переключайте значения, которые находятся на «неправильной стороне» значения поворота, пока все значения, большие или равные, чем точка поворота, не окажутся справа от некоторого индекса, а все меньшие значения не будут находиться слева от этого же индекса. показатель. Разделите массив на этот индекс, чтобы создать две подзадачи меньшего размера.
  • Conquer Когда размеры достаточно малы (например, 1 или 2), эта процедура разделения приведет к сортировке подмножеств. Группировка чисел по большему или меньшему повороту в крупном масштабе гарантирует, что алгоритм, выполненный на меньшем массиве из 2 (что фактически вызывает сортировку массива), выполняется в том месте в массиве, которое вызовет общий массив быть отсортированными, а не просто иметь скопления локализованных отсортированных данных.
  • Объединить Так же, как Завоевание алгоритма сортировки слиянием было тривиальным, потому что вся работа выполнялась с помощью сортировки слиянием Объединить, Объединить быстрой сортировки тривиально, потому что вся работа выполняется на шаге Разделить. После того, как массив разделен на наборы по 1 и 2, он сортируется по месту. И алгоритм прекратит рекурсию, когда размер подмассива станет равным или меньше нуля.

Инвариант цикла разделения (см. код ниже)

  • Заявление: все значения arr от исходного значения аргумента lo до текущего значения lo меньше или равны значению поворота. Значения arr от исходного значения аргумента hi до текущего значения hi больше или равны значению поворота.
  • Инициализация lo и hi инициализируются на единицу меньше и больше своих начальных значений соответственно. Находясь вне массива и не связанный со значениями, вы тривиально выполняете требование, чтобы связанные значения arr были такими, как указано в LI.
  • Обслуживание После одиночного цикла значение индексаlo увеличивается на все индексы, значение которых меньше, чем точка поворота. Когда цикл, наконец, прерывается, lo, следовательно, гарантированно будет зафиксирован на индексе, значение которого больше или равно значению поворота, при этом все значения слева от него гарантированно будут меньше значения поворота (или равны значению поворота). значение, если оно было переставлено слева от lo). 'hi' уменьшается таким же образом, останавливаясь на индексе, значение которого меньше или равно значению pivot, гарантируя, что все значения справа от 'hi' больше, чем значение pivot (или равны значению pivot если он был переставлен справа от hi). Если hi ›lo, мы меняем их местами, потому что мы знаем, что внутренние циклы остановились на значениях, которые должны быть связаны с« другой стороной »или« серединой »массива, разделенными на значение поворота, и мы еще не достигли значения« середина'. Это означает, что новое значение для arr[lo] должно соответствовать требованию для прерывания цикла arr[hi] (т. Е. <= pivot), а новое значение для arr[hi] должно соответствовать требованию прерывания цикла arr[lo] (т. Е. >= pivot). Таким образом, предполагается, что все значения в индексе lo и ниже либо меньше, чем точка поворота (если они были переданы циклом), либо меньше или равны значению поворота (если они были заменены из точки, ранее находящейся в индексе hi ). Другими словами, все они меньше или равны опорному значению. И наоборот, поддерживается, что все значения с индексом «hi» и выше либо больше, чем значение поворота, либо равны значению поворота.
  • Прекращение действия. Если lo ›= hi, мы знаем, что попали в то место в массиве, которое численно делится на значение поворота. Мы возвращаем более высокий из двух индексов, что позволяет нам создать подразделение массива, в котором все значения ниже partition_index - 1 меньше или равны оси поворота, а все значения выше partition больше или равны оси поворота. Кроме того, разделяя массив так, как мы это делаем в quicksort!, мы предотвращаем бесконечный цикл, предотвращая разделение индекса раздела на пустой массив и исходный массив. Когда подмассив имеет размер 1 или 2, partition приводит к отсортированному разделу подмассива, который также находится в правильном положении относительно всего массива.

Код

Время выполнения алгоритма на рандомизированных и почти отсортированных данных

Вывод случайных чисел:

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

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

QuickSort: как избежать наихудшего случая

Когда я попытался запустить QuickSort в наиболее часто отсортированном списке, программа вылетела из строя, пока я не уменьшил размер набора данных с 1 миллиона до примерно 15 000.

На этом этапе время выполнения для этих 15000 отсортированных элементов было таким же, как и для QuickSort, работающего на 1 МИЛЛИОНЕ рандомизированных элементов, и хотя количество рекурсий быстрой сортировки было меньше, количество циклов, возникающих в методе разделения, было значительно больше.

Как описано выше, это происходит потому, что точка поворота находится в конце массива, поэтому все остальные элементы в arr меньше точки поворота! Вместо того, чтобы делать две четные подзадачи для достижения времени выполнения nlgn, мы создаем 2 подзадачи размера 1 и n-1. Суммирование от 1 до n равно ϴ (n ^ 2). Подумайте о суммировании от 1 до 10. Это (10 + 1) * (10 / 2) = 55. Замена 10 на n, (n + 1) * (n/2) = (n^2 )/2 + n/2. Отбросьте коэффициенты и члены более низкого порядка, чтобы получить n^2.

Чтобы решить эту проблему времени выполнения ϴ (n²) для почти отсортированного списка, мы можем грамотно выбрать элемент сводной таблицы. Если я запускаю optimize_pivot, чтобы выбрать точку поворота, я нахожу среднее значение между значениями индексов low, hi и med в подмассиве. Затем я переключаю это значение на arr[hi] и продолжаю использовать hi в качестве основного индекса. Если массив уже отсортирован, я теперь использую среднее значение списка, а не крайнее значение, и могу достичь времени выполнения ϴ (n * lgn) в отсортированном списке, потому что я вернулся к тому, чтобы разбить свою проблему пополам, а не вычитать одно из размер.

Улучшенный код быстрой сортировки

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

Ресурсы

[1] Введение в алгоритмы, Cormen, Leiserson, Rivest, Stein