Нижняя граница сложности класса алгоритмов определяется не един­ственным образом. Например, f (n ) = 0 всегда является нижней гра­ницей, равно как и любая отрицательная функция. Чем больше най­денная нижняя граница, тем она нетривиальнее и ценнее. Сигналом о том, что мы не сможем построить нижнюю границу большую, чем

ПО Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

уже имеющаяся у нас нижняя граница f (n ), может служить, напри­мер, наличие A е .s4, для которого T A (n) = f(n). С такой ситуацией мы сталкиваемся в предыдущем параграфе в примерах 14.1 и 14.3. Извест­ный нам алгоритм поиска наименьшего элемента и алгоритм бинар­ного поиска места элемента в упорядоченном массиве имеет каждый сложность, совпадающую с найденной нижней границей. Эти алго­ритмы являются оптимальными в смысле следующего определения.

Определение 15.1. Пусть .s4 - класс алгоритмов решения неко­торой задачи. Пусть принято соглашение о том, в чем измеряются затраты алгоритмов и что считается размером входа, и пусть n -обо­значение размера входа. Алгоритм A е .s4 называется оптимальным в j4, если T A (n) является нижней границей сложности алгоритмов из j4.

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

Предложение 15.1. Функция f (n ) = Г 2 n 1 - 2 является нижней границей сложности алгоритмов одновременного выбора наибольшего и наименьшего элементов массива длины n c помощью сравнений.

Доказательство. Каждый этап выполнения произвольного алго­ритма V, основанного на сравнениях и предназначенного для поиска наибольшего и наименьшего элементов массива, может быть охарак­теризован четверкой (A, B, C, D) подмножеств множества исходных элементов {x г, x 2 , ■ ■ ■, x n }, где

A состоит из всех тех элементов, которые вообще не сравнива­лись;

B состоит из всех тех элементов, которые участвовали в некоторых сравнениях и всегда оказывались большими;

C состоит из всех тех элементов, которые участвовали в некото­рых сравнениях и всегда оказывались меньшими;

D состоит из всех тех элементов, которые участвовали в некото­рых сравнениях, иногда оказываясь большими, а иногда - мень­шими.

Пусть a, b,c,d - количества элементов множеств A, B, C, D соответ­ственно. Исходная ситуация характеризуется равенствами a = n, b = = c = d = 0. После завершения алгоритма должны выполняться равен-

§ 15 . Оптимальные алгоритмы

ства а = 0, b = c = 1, d = n-2. После первого сравнения на протяже­нии всего выполнения алгоритма постоянно будут иметь место нера­венства Ъ^1,с^1.

Все сравнения, совершаемые при выполнении алгоритма V, мож­но разбить на типы, обозначаемые AA,AB,AC,AD, BB,BC,BD,CC, CD,DD, например: сравнение принадлежит типу АВ , если один из сравниваемых элементов берется из А , другой-из В , и т. д. Исходя из этого, можно выписать все возможные изменения четверки (а, Ь , с , d ) под действием сравнений разных типов.

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

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

Заметим, что при замещении приходится дважды передавать страницу между основной и вторичной памятью. Процесс замещения может быть оптимизирован за счет использования бита модификации (один из атрибутов страницы в таблице страниц). Бит модификации устанавливается компьютером, если хотя бы один байт был записан на страницу. При выборе кандидата на замещение проверяется бит модификации . Если бит не установлен, нет необходимости переписывать данную страницу на диск , ее копия на диске уже имеется. Подобный метод также применяется к read-only -страницам, они никогда не модифицируются. Эта схема уменьшает время обработки page fault .

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

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

Эффективность алгоритма обычно оценивается на конкретной последовательности ссылок к памяти, для которой подсчитывается число возникающих page faults . Эта последовательность называется строкой обращений (reference string ). Мы можем генерировать строку обращений искусственным образом при помощи датчика случайных чисел или трассируя конкретную систему. Последний метод дает слишком много ссылок, для уменьшения числа которых можно сделать две вещи:

• для конкретного размера страниц можно запоминать только их номера, а не адреса, на которые идет ссылка;
• несколько подряд идущих ссылок на одну страницу можно фиксировать один раз.

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

Рассмотрим ряд алгоритмов замещения страниц.

Алгоритм FIFO. Выталкивание первой пришедшей страницы

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

Аномалия Билэди (Belady)

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

Система с тремя кадрами (9 faults) оказывается более производительной, чем с четырьмя кадрами (10 faults), для строки обращений к памяти 012301401234 при выборе стратегии FIFO .

Рис. 10.1.

Оптимальный алгоритм (OPT)

Одним из последствий открытия аномалии Билэди стал поиск оптимального алгоритма, который при заданной строке обращений имел бы минимальную частоту page faults среди всех других алгоритмов. Такой алгоритм был найден. Он прост: замещай страницу, которая не будет использоваться в течение самого длительного периода времени.

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

Этот алгоритм легко описать, но реализовать невозможно. ОС не знает, к какой странице будет следующее обращение. (Ранее такие проблемы возникали при планировании процессов - алгоритм SJF ).

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

Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU

Одним из приближений к алгоритму OPT является алгоритм, исходящий из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего.

Ключевое отличие между FIFO и оптимальным алгоритмом заключается в том, что один смотрит назад, а другой вперед. Если использовать прошлое для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение самого долгого времени. Такой подход называется least recently used алгоритм (LRU ). Работа алгоритма проиллюстрирована на рис. рис. 10.2 . Сравнивая рис. 10.1 b и 10.2, можно увидеть, что использование LRU алгоритма позволяет сократить количество страничных нарушений .

LRU - хороший, но труднореализуемый алгоритм. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут хранится недавно использованные страницы. Причем этот список должен обновляться при каждом обращении к памяти. Много времени нужно и на поиск страниц в таком списке.

В [Таненбаум, 2002 ] рассмотрен вариант реализации алгоритма LRU со специальным 64-битным указателем, который автоматически увеличивается на единицу после выполнения каждой инструкции, а в таблице страниц имеется соответствующее поле, в которое заносится значение указателя при каждой ссылке на страницу. При возникновении page fault выгружается страница с наименьшим значением этого поля.

Как оптимальный алгоритм, так и LRU не страдают от аномалии Билэди . Существует класс алгоритмов, для которых при одной и той же строке обращений множество страниц в памяти для n кадров всегда является подмножеством страниц для n+1 кадра. Эти алгоритмы не проявляют аномалии Билэди и называются стековыми (stack) алгоритмами.

Выталкивание редко используемой страницы. Алгоритм NFU

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

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

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

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

Таким образом появляется возможность сравнить производительность осуществимых алгоритмов с наилучшим из возможных. Если операционная система достигает производительности, скажем, на 1 % хуже, чем у оптимального алгоритма, то усилия, затраченные на поиски более совершенного алгоритма, дадут не более 1 % улучшения.

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

Предположим, что все искажения в канале строго детерминированы и случайным является только гауссовский аддитивный шум n(t), который вначале полагаем белым, со спектральной плотностью N 0 . Это значит, что при передаче сигнала u i (t) (символа b i (i = 0,1,...,m-1) приходящий сигнал можно описать моделью (3.38):

z(t) = s i (t) + n(t), (0≤t≤T), (6.17)

где все s i (t) = ku i (t-τ) (i = 0, 1,..., m-1) известны. Неизвестны лишь реализация помехи и индекс i действительно переданного сигнала, который и должна определить решающая схема.

Будем также считать, что все s i (t) являются финитными сигналами, длительность которых Т. Это имеет место, если передаваемые сигналы u i (t) финитны и имеют одинаковую длительность (система синхронная), а в канале нет ни многолучевого распространения, ни линейных искажений, вызывающих увеличение длительности сигнала (либо они скорректированы).

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

Определим в этих условиях алгоритм работы оптимального (т. е. основанного на правиле максимального правдоподобия) демодулятора, анализирующего сигнал на тактовом интервале 0-Т. Для этого необходимо найти отношения правдоподобия для всех m возможных сигналов относительно нулевой гипотезы (s(t)=0; z(t) = n(t)).

Задача затрудняется тем, что ширина спектра сигнала бесконечна (поскольку он финитный), а поэтому пространство сигналов бесконечномерное L 2 (Т). Для таких сигналов (или бесконечномерных векторов), как отмечалось, не существует плотности вероятностей. Однако существуют "-мерные плотности вероятностей для любых n сечений сигнала (см. § 2.1).

Заменим вначале белый шум квазибелым, имеющим ту же одностороннюю спектральную плотность мощности N 0 , но только в некоторой полосе частот F = n/2T, где n>>1. Рассмотрим вначале дополнительную гипотезу, т. е. будем считать что Z(t) - шум. Возьмем на тактовом интервале n равноотстоящих сечений через Δt = 1/2F = T/n. Отсчеты Z 1 ,...., Z n в этих сечениях для квазибелого гауссовского шума независимы в соответствии с (2.49). Поэтому n-мерная плотность вероятностей для взятых отсчетов

где σ 2 = N 0 F - дисперсия (мощность) квазибелого шума.

При гипотезе, что передавался символ b i , согласно (6.17) n(t) = z(t) - s i (t). Следовательно, условная n-мерная плотность вероятности сечений Z(t) определится такой же формулой, как и (6.18), если z(t k) заменить разностью z(t k)-s i (t k), представляющей при этой гипотезе шум:

Отношение правдоподобия для сигнала s i (относительно дополнительной гипотезы), вычисленное для n сечений:

Заменим дисперсию σ 2 ее выражением: σ 2 = N 0 F = N 0 /(2Δt). Тогда

По правилу максимума правдоподобия в случае квазибелого шума решающая схема должна выбирать значение i, обеспечивающее максимум Λ i [n] . Вместо максимума Λ i можно отыскивать максимум его логарифма:

Второй член в (6.22) не зависит от t и его можно при сравнении гипотез не учитывать. Тогда правило решения о том, что передавался символ b i , согласно (6.10) можно выразить системой неравенств

Вернемся теперь к исходной задаче для белого шума. Для этого будем расширять полосу F, тогда число сечений п стремится к бесконечности, а Δt - к нулю. Суммы в (6.22) обратятся в интегралы, и травило решения определится так:

Выражение (6.24) определяет те операции (алгоритм работы), которые должен совершать оптимальный приемник над входным колебанием z(t).

На рис. 6.2 для m = 2 показана структурная схема приемного устройства, работающего в соответствии с алгоритмом (6.24).

Здесь "-" - вычитающие устройства; Γ 0 , Γ 1 - генераторы опорных сигналов s 0 (t), s 1 (t); "KB" - квадраторы; ∫ - интеграторы; РУ - решающее устройство, определяющее в моменты времени, кратные Т (при замыкании ключей), номер ветви с минимальным сигналом.

При m>2 в схеме рис. 6.2 и других нижеприведенных схемах растет соответственно число ветвей обработки сигнала, попадающих на РУ.

В пространстве Гильберта

определяет норму разности векторов z и s или расстояние между ними * . Поэтому алгоритм (6.24) можно записать в виде

||z - s i ||

и придать ему простую геометрическую интерпретацию: оптимальный демодулятор должен регистрировать тот из сигналов s i (t) (соответствующий символу b i), который "ближе" к принятому колебанию z(t). В качестве примера на рис. 6.3 показано оптимальное разбиение двумерного пространства принимаемых сигналов z(t) при передаче сигналов s 1 (t) и s 0 (t). Области принятия решения в пользу символов 0 или 1 расположены по обе стороны от прямой 0-0, перпендикулярной отрезку, соединяющему точки сигналов и делящих его пополам.

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

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

приходим к алгоритму приема:

где E j - энергия ожидаемого сигнала s j (t) :

Для двоичной системы алгоритм (6.25) сводится к проверке одного неравенства

Устройство, непосредственно вычисляющее скалярное произведение

называют активным фильтром, или коррелятором, поэтому приемник, реализующий алгоритм (6.25), называют корреляционным.

* (Для n-мерного пространства Евклида эта норма равна )

На рис. 6.4 показана структурная схема приемного устройства, работающего в соответствии с (6.27). Здесь блоки × - перемножители; Γ 0 , Γ 1 - генераторы опорных сигналов s 0 (t) s 1 (t); ∫ - интеграторы; "-" - вычитающие устройства; РУ - решающее устройство, определяющее в моменты времени, кратные Т (при замыкании ключа), i = 0, 1 - номер ветви с максимальным сигналом.

Если сигналы u i (t) выбраны таким образом, что все их реализации (а следовательно, и все реализации s i (t) имеют одинаковые энергии (E i = const), алгоритм приема (6.25) (и соответственно его реализация) упрощается (отпадает необходимость в вычитающих устройствах) и принимает вид

Из (6.29) видно, что правило решения не изменится, если сигнал z(t), поступающий на вход демодулятора, умножить на любое число. Поэтому система, в которой все реализации сигнала имеют равную энергию, отличается тем, что оптимальный алгоритм приема в ней не требует знания "масштаба" приходящего сигнала или, другими словами, знания коэффициента передачи k канала. Эта важная особенность обусловила широкое распространение систем сигналов с равной энергией, которые обычно называют системами с активной паузой. Это особенно важно для каналов с замираниями, в которых коэффициент передачи флуктуирует (см. §6.7).

Заметим, что для двоичной системы неравенство (6.27) можно представить в более простом виде:

где s Δ (0 = s 1 (t) - s 0 (t) - разностный сигнал; λ = 0,5(E 1 -Е 0) - пороговый уровень. Для системы с активной паузой Х=0, что значительно облегчает реализацию оптимальной схемы.

При выполнении неравенства (6.30) регистрируется символ 1, в противном случае - 0. Для реализации (6.30) в схеме рис. 6.4 требуется лишь одна ветвь.

На рис. 6.5,а показана схема, реализующая алгоритм (6.30) для двоичной системы передачи однополярными импульсами (с пассивной паузой): s 1 (t) = a, s 0 (t) = 0. При этих сигналах s Δ (t) = s 1 (t) = a, Е 1 = а 2 Т, E 0 = 0, λ = а 2 T/2 и (6.30) примет следующий, вид:

Рассмотренную систему двоичных сигналов используют в простейших устройствах проводной связи. В радиоканалах, а также в современных кабельных каналах применяют высокочастотные сигналы. Наиболее простыми двоичными системами с гармоническими сигналами являются системы с амплитудной (AM), фазовой (ФМ) и частотной (ЧМ) манипуляцией.

В двоичной AM s 1 (t) = acos(ω 0 t + φ), s 0 (t) = 0. Все входящие сюда постоянные (а, ω 0 , φ) в этом параграфе полагаем известными. Поскольку здесь s Δ (t) = s 1 (t), Е 1 = а 2 Т/2 и E 0 = 0, правило (6.30) запишется так:

Оно реализуется схемой рис. 6.5,6, которая отличается от рис. 6.5,a блоком перемножения приходящего сигнала с опорным сигналом cos(ω 0 t + φ). Пороговый уровень λ̇ в этом случае равен aT/(4RC).

При двоичной ФМ системе s 0 (t) = a cos(tω 0 + φ), s 0 (t) = а cos (tω 0 + φ + π) = -s 1 (t). Это - система с активной паузой, и поэтому в (6.30) λ = 0. Легко убедиться, что правило решения сводится при этом к следующему:

и реализуется той же схемой рис. 6.5,6 при λ̇ = 0. В этом случае РУ играет роль дискриминатора полярностей.

Рис. 6.6. Оптимальный демодулятор с обеляющим фильтром при гауссовском "окрашенном" шуме

Рассмотрим вкратце случай, когда гауссовский шум в канале не белый и не квазибелый, а "окрашенный", т. е. имеет неравномерную плотность мощности G(f) в полосе спектра сигнала. Пропустим приходящую на вход демодулятора сумму сигнала и шума через фильтр с передаточной функцией k(i2πf), такой чтобы в полосе спектра сигнала произведение G(f) |k(i2πf)| 2 было постоянной величиной N 0 . Из всех возможных фильтров с k(i2πf), удовлетворяющих этому условию и различающихся только фазо-частотной характеристикой, можно выбрать минимально фазовый, который является обратимым. Очевидно, что на выходе фильтра шум окажется квазибелым: G вых (f)=N 0 . Поэтому такой фильтр называется обеляющим.

Сигнал s i (t) после прохождения через обеляющий фильтр превратится в некоторый другой сигнал, который обозначим s" i (t). Вид его можно определить, зная s i (t) и k(i2πf). Если теперь подать колебания с выхода обеляющего фильтра на демодулятор, являющийся оптимальным для приема сигналов s" i (t) (i = 0, 1, ..., m-1), то получим схему рис. 6.6, которая, очевидно, является оптимальной для сигналов s i (t) при окрашенном шуме.

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

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

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

В ответ вы должны спросить: «А для какого случая выбирается оптимальная по времени сортировка?» И лишь тогда, когда будут озвучены условия, можно смело перебирать имеющиеся варианты.

Существуют:

• алгоритмы сортировки O(n 2) вроде сортировки вставками, пузырьком и выбором, которые используются в особых случаях;
• быстрая сортировка (общего назначения): в среднем O(n log n) обменов, но худшее время – O(n 2) , если массив уже отсортирован, или элементы равны;
• алгоритмы O(n log n) , такие как сортировка слиянием и кучей (пирамидальная сортировка), которые также являются хорошими алгоритмами сортировки общего назначения;
• O(n) или линейные алгоритмы сортировки (выбор, выбор с обменом, выбор с подсчетом) для списков целых чисел, которые могут быть подходящими в зависимости от характера целых чисел в ваших списках.

Если все, что вы знаете, – это отношение общего порядка между элементами, то оптимальные алгоритмы будут иметь сложность О(n log n) . Для линейных алгоритмов нужна дополнительная информация о структуре элементов.

Оптимальность алгоритма тесно зависит от типа списков/массивов, которые вы собираетесь сортировать, и даже от модели ЭВМ. Чем больше информации в вашем распоряжении, тем более точным будет выбор. При очень слабых предположениях о факторах оптимальной сложностью худшего случая может быть О(n!) .

Данный ответ касается только сложностей. Фактическое время выполнения алгоритмов зависит от огромного количества факторов.

Тестирование

Итак, какая же сортировка самая быстрая?

Визуализация

Неплохая визуализация сортировок продемонстрирована в этом видео:

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