С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 4
Текст из файла (страница 4)
> 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. Соответствующее неравенство из Глава . Сложности алгоритмов как функции числовых аргументовчисла| f (n) | ¾ c1 | g(n) |,| f (n) | ¶ c2 | g(n) |,c1 | g(n) | ¶ | f (n) | ¶ c2 | g(n) |(.)тоже, в соответствии с определением, должно выполняться лишьдля n, больших некоторого N. Заметим, однако, что если f (n) и g(n)определены для всех n ∈ N+ и принимают при 1 ¶ n ¶ N ненулевыезначения, то можно считать, что соответствующее неравенство из перечисленных в (.) выполняется для всех n, так как, положивm = min1¶n¶ N| f (n) |,| g(n) |M = max1¶n¶ N| f (n) |,| g(n) |мы можем заменить c1 , c2 в (.) на c′1 = min{c1 , m}, c′2 = min{c2 , M}.Это замечание в некоторых случаях будет для нас полезным.Вернемся к примеру ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
