Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Чтобы проиллюстрировать указанное обстоятельство,мы вновь обратимся к сортировке простыми вставками, которая может рассматриваться в двух вариантах I1 и I2 : для вставки элементаxi+1 в уже упорядоченную часть x1 , x2 , ..., xi элементы этой упорядоченной части просматриваются либо в порядке xi , xi−1 , ..., либо в порядке x1 , x2 , ... В первом варианте максимум числа сравнений достигается тогда, когда входной массив имеет обратную к требуемойупорядоченность: x1 > x2 > ... > xn , и на этом же входе достигаетсямаксимум числа обменов; имеем TeI1 (n) = TI′1 (n) + TI′′1 (n) = n(n − 1), гдеTI′1 (n), TI′′1 (n) суть сложности по числу сравнений и обменов.Во втором варианте максимум числа сравнений достигается, когдамассив уже упорядочен так, как требуется: x1 < x2 < ...

< xn , а максимум числа обменов — когда x1 > x2 > ... > xn . Если i > 1, то при вставкеэлемента xi+1 в уже упорядоченную часть x1 , x2 , ..., xi потребуется темменьше обменов, чем больше потребуется сравнений. Если элемент Глава . Сложности алгоритмов как функции числовых аргументовзаймет место с номером k, то это потребует i − k + 1 обменов. Числоже сравнений равно k, если k ¶ i, и равно k − 1, если k = i + 1.

Суммарное число сравнений и обменов равно i + 1, если k ¶ i, и равно i,если k = i + 1. Поэтому максимум общего числа сравнений и обменов достигается, например, на входном массиве, имеющем обратнуюк требуемой упорядоченность: x1 > x2 > ... > xn . Легко устанавливает(n + 2)(n − 1).ся, что TeI (n) =22Рассматривая сложности TeI1 (n), TeI2 (n) первого и второго вариантов сортировки простыми вставками по общему числу сравненийи обменов, мы имеемTeI1 (n) = n(n − 1),(n + 2)(n − 1)TeI2 =,2(.)и, таким образом, TeI1 (n)/TeI2 (n) → 2 при возрастании n.Обладающий большей общей сложностью TeI1 первый вариант алгоритма рассматривается в литературе значительно чаще второго, нев последнюю очередь из-за того, что его запись несколько проще: мыможем со всеми подробностями записать первый вариант с помощьюпсевдокодаfor i = 2 to n dok := i ;while k > 0 and xk > xk+1 do xk ↔ xk+1; k := k − 1 odod(предполагается, что если k ¶ 0, то булево выражение, имеющее видконъюнкцииk > 0 and xk > xk+1 ,принимает значение 0, т.

е. «ложь», даже если при этом, например,значение xk не определено, и, следовательно, не определено значениевторого члена конъюнкции).Второй вариант будет иметь вид:for i = 2 to n dok := 1;while k < i and xk < xi do k := k + 1 od;for j = i − 1 downto k do x j ↔ x j +1 ododВ первом варианте используется на один оператор цикла меньше,но с точки зрения вычислительной сложности это не является пре-§ .

Затраты алгоритма для данного входаимуществом, — важным является число лишь учитываемых операцийпри выполнении алгоритма. Хотя обычно для каждой сортировки рассматривают сложности по сравнениям и перемещениям раздельно,но, тем не менее, если эти сложности совпадают с соответствующимисложностями другой сортировки, то совместное рассмотрение обоихтипов операций может оказаться небезынтересным.Заметим попутно, что среди сортировок с квадратичной сложностью по числу сравнений чрезвычайно низкой сложностью по числуперемещений, а именно сложностью, равной n − 1, обладает сортировка выбором.В некоторых случаях к учитываемым операциям относят операциивесьма разнородные, и время выполнения каждой из них считаютравным 1 — пример ., как и некоторые другие, даст соответствующую иллюстрацию.

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

Поместив в ячейку результат каких-то вычислений или считав содержимое некоторойячейки, машина обращается еще к какой-то ячейке и т. д. Относительно этого процесса предполагается, что сам переход от ячейки к ячейке не связан с какими-либо затратами. Этот принцип лежит в основемодели вычислений, называемой РАМ («равнодоступная адресная машина» — довольно неуклюжий, но принятый термин; имеется в видумашина с равнодоступными ячейками памяти)  . Модель РАМ существенно отличается в этом смысле от другой известной модели вычислений — машины Тьюринга (МТ), где время перехода от однойячейки ленты к другой зависит от расстояния между ячейками; приэтом одна ячейка ленты МТ содержит один символ фиксированногоконечного алфавита  .В литературе на английском языке — RAM (random-access machine).Раньше в литературе по вычислительной математике и программированию слово «машина» употреблялось как обозначение некоторого реального вычислительногоустройства; устойчивым словосочетанием было, например, «электронная вычислительная машина» (ЭВМ).

Сейчас в этом значении в основном употребляется слово «компьютер», а слово «машина» часто используется при обсуждении абстрактных вычислительных устройств: машин Тьюринга, равнодоступных адресных машин и т. д. Глава . Сложности алгоритмов как функции числовых аргументовУпотребление слова «модель» в этом контексте подчеркивает тообстоятельство, что реальные вычислительные устройства (компьютеры) работают на тех или иных специфических принципах, но приисследовании вычислительной сложности алгоритмов этой спецификой можно до известного предела пренебрегать и исходить из упрощающей системы допущений.Далее мы будем еще неоднократно обращаться к понятию моделивычислений; всюду до главы  без оговорок подразумевается модельРАМ.§ .

Асимптотические оценки (формализм)Для характеристики роста сложности по числу сравнений сортировки простыми вставками первого и второго типа мы можем использовать известный из математического анализа символ O и написатьT(n) = O(n2 ) (здесь и далее n → ∞). Мы можем также выделить главные по росту слагаемые в (.):TeI1 (n) = n2 + O(n),1TeI2 (n) = n2 + O(n),2(.)хотя в этом и нет ощутимого практического смысла в силу простотыфункций TeI1 (n), TeI2 (n).

В то же время, как это хорошо известно, асимптотическая формула f (n) = O(g(n)) является удобным средством оценивания нетривиально устроенной функции f (n) с помощью болеепростой функции g(n); столь же полезными оказываются и оценкивида f (n) = o(g(n)). Но когда мы говорим, что сортировка выбором,пузырьковая сортировка и сортировка простыми вставками имеютквадратичные сложности, мы имеем в виду не только то, что соответствующие сложности допускают оценку O(n2 ), но что эти сложностиявляются величинами порядка n2 ; в математическом анализе это иногда записывается как T(n) ≍ n2 , где T(n) — рассматриваемая функция,в данном случае — сложность. В последние годы в теории сложностиалгоритмов вместо f (n) ≍ g(n) стали писать f (n) = Θ(g(n)).Определение .. Функции f (n) и g(n) имеют одинаковый порядок(пишут f (n) = Θ(g(n))) тогда и только тогда, когда найдутся положительные c1 , c2 , N такие, что неравенстваc1 | g(n) | ¶ | f (n) | ¶ c2 | g(n) |(.)выполнены для всех n > N.Без труда проверяется, что отношение «иметь одинаковый порядок» является отношением эквивалентности на множестве функций,§ .

Асимптотические оценки (формализм)определенных для всех достаточно больших значений n (в нашем случае эти значения целые). Несимметричность записи f (n) = Θ(g(n))в сравнении с записью f (n) ≍ g(n) ( f (n) и g(n) как бы не равноправны в первой записи, хотя имеем дело с отношением эквивалентности) объясняется тем, что обычно эту запись используют, когда g(n)проще, чем f (n).Итак, для сложности T(n) по числу сравнений для любого из упомянутых алгоритмов сортировки мы имеем T(n) = Θ(n2 ).

Это болеесильное утверждение, чем T(n) = O(n2 ), так как T (n) = O(n2 ) являетсялишь асимптотической верхней оценкой: в соответствии с известнымиз математического анализа определениемf (n) = O(g(n)) ⇐⇒ ∃c,N >0 ∀n>N | f (n) | ¶ c| g(n) |,например, n = O(n2 ), но неверно, что n = Θ(n2 ). Здесь и далее, пользуясь кванторами ∃, ∀, мы записываем связываемые ими переменные,равно как и условия, определяющие множества значений этих переменных, в виде индексных выражений при кванторах.

Это частопозволяет обходиться без дополнительных скобок и облегчает чтениеформул.Иногда бывают полезными нижние асимптотические оценки.Определение .. Соотношение f (n) = Ω(g(n)) имеет место тогдаи только тогда, когда найдутся положительные c, N такие, что длявсех n > N выполнено | f (n) | ¾ c| g(n) |.Следующее предложение выводится из определений символов O, Ωи Θ.Предложение .. Соотношение f (n) = Θ(g(n)) имеет место тогдаи только тогда, когда одновременно f (n) = O(g(n)) и f (n) = Ω(g(n));помимо этого, f (n) = Ω(g(n)) тогда и только тогда, когда g(n) == O( f (n)).Если размер входа является целым положительным числом, то возникающие функции являются последовательностями.

Для единообразия мы, как правило, будем говорить о функциях, подразумевая, ноне упоминая специально, что каждая такая функция определена лишьдля целых положительных значений аргумента (возможно даже, только для достаточно больших целых положительных значений аргумента). Итак, при n → ∞ оценки вида f (n) = Λ(g(n)), где Λ — один изсимволов Ω, O, Θ, предполагают, что функции f (n), g(n) определены для всех достаточно больших n.

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

Список файлов лекций