Затраты алгоритма для данного входа, алгебраическая сложность

Сложность в худшем случае

Как функции числовых аргументов.

Сложности алгоритмов

Наиболее часто используемые обозначения

Сд(х), Сд(х)—временные и пространственные затраты алгоритма А для входа (входных данных) х;

\\х\\— размер входах;

T_A{s), S_A (s)—значения временной и пространственной сложности ал­горитма А для значения s размера входа;

А(п)—количество цифр в двоичной записи неотрицательного цело­го п (битовая длина п);

Я* (п) — количество единиц в двоичной записи неотрицательного це­лого п;

[а] —наибольшее целое, меньшее или равное вещественному а;

\а] —наименьшее целое, большее или равное вещественному а;

N, N⁺—множества неотрицательных и положительных целых чисел;

Z—множество (кольцо) целых чисел;

Z_k — кольцо вычетов по модулю к;

Q, Ж, С — множества (поля) рациональных, вещественных и ком­плексных чисел;

П_п —множество всех перестановок чисел 1, 2,..., п;

□—конец доказательства.

Глава 1

Пусть по входным данным (входу) х алгоритм А вычисляет результат (выход) у. Такое вычисление связано с затратами времени и памя­ти. Допустим, что достигнуто соглашение о том, как измеряются эти затраты, тогда можно рассмотреть функции затрат

С\{х), C^s_A{x),

где верхний индекс Т указывает на временные затраты ^г, S — на пространственные затраты (затраты памяти и пространственные за­траты— это синонимы), соответствующие вычислениям, связанным с применением А к входу х; буквы Т и S возникают из английских слов time — время и space — пространство. Вид этих функций может быть очень непростым; их трудно исследовать методами математи­ческого анализа, потому что аргумент х не является, вообще говоря, числом и не принадлежит какому-либо метрическому пространству. Можно ввести некоторую неотрицательную числовую характеристику ||х|| возможных входов алгоритма и оценивать функции затрат с по­мощью функций, зависящих не от х, а от ||х||:

C^T_A{x)^Lp{\\x\\), C^s_A{x)^^{\\x\\). (1.1)

Если ц> и -ф не слишком быстро растут при возрастании (числового) аргумента, то эти оценки могут обнадеживать автора или потреби­теля алгоритма А.

¹ Здесь и далее имеется в виду временные (связанные с расходованием времени), а не временные (непостоянные, краткосрочные) затраты. Аналогично — временная сложность и т.д.

10 Глава 1. Сложности алгоритмов как функции числовых аргументов

Избираемую нами величину || • || принято называть размером вхо­да. В соответствии с нашим замыслом размер входа должен харак­теризовать «громоздкость» исходных данных; то, что || x || является числом, позволяет говорить о росте ip, ip и исследовать этот рост. Выбор размера входа —существенный этап оценивания функций за­трат; нужна, во всяком случае, уверенность, что оценки вида (1.1) будут нести полезную информацию.

В дальнейшем, однако, предметом нашего изучения будут не функ­ции затрат, а некоторые другие функции, о которых мы скажем по­сле ряда примеров. Предварительно условимся о некоторых обычных для литературы по сложности алгоритмов обозначениях. Пусть a el, т.е. a — вещественное число. Значение |_ a j есть результат округле­ния a до целого в меньшую сторону: 1.3,14J = 3, |_-3,14| = -4 (эту величину — целую часть a — записывают и как [ a ]). Соответствен­но, \a] есть результат округления a до целого в большую сторону: [3,141=4, [-3,141 = -3. Если a — целое, то [a\ = \a]=a.

Рассмотрим три простых примера.

Пример 1.1. Исходя из определения произведения матриц, мы по­лучаем алгоритм умножения двух квадратных матриц порядка n, тре­бующий n ³ операций умножения. Этот алгоритм далее будет обозна­чаться буквами MM, от английских слов matrix multiplication — мат­ричное умножение.

Пример 1.2. Один из очевидных алгоритмов распознавания про­стоты данного n eN⁺, который мы будем называть алгоритмом проб­ных делений, состоит в выяснении того, имеется ли среди чисел 2, 3,..., LV n J хотя бы одно, делящее n. Количество проверок дели­мости n на те или иные целые числа (для краткости можно гово­рить о «числе делений») колеблется от 1 до La n J - 1. Этот алго­ритм далее будет обозначаться буквами TD, от английских слов trial divisions —пробные деления.

Пример 1.3. При сортировке простыми вставками число сравне­ний¹ колеблется от n - 1 до —-—, в зависимости от входного мас­сива x ₁ ,x₂,...,x_n. Если интересоваться числом перемещений элемен-

¹ Основные алгоритмы сортировки и поиска приводятся в приложении A. Обсуждая конкретные алгоритмы сортировки, мы для краткости иногда будем опускать само сло­во «алгоритм», говоря, например, не об алгоритме сортировки простыми вставками, а просто о сортировке простыми вставками и т. д. Все сортировки, которые мы рассмат­риваем, являются сортировками с помощью сравнений, т. е. никаких других операций, кроме сравнений и перемещений (присваиваний или обменов), над элементами мас­сива производиться не может, — исключение составляет пример 29.1. Элементы сор-

§ 1. Затраты алгоритма для данного входа

тов (операций обмена <->), то оно колеблется от 0 до n ⁽ n ₂ ^1}. Эта сортировка далее будет обозначаться буквой I, от английского слова insert—вставка.

В этих примерах уже фактически сказано, что считается разме­ром входа и затратами. В примере 1.1 размер входа — целое неотри­цательное n —это порядок матриц. В примере 1.2 размер входа — са­мо входное число (сам вход) n. В примерах 1.1, 1.2 количество ис­следуемых операций однозначно определяется по n. Столь жесткая зависимость затрат от размера входа может и не иметь места, как это следует из примера 1.3, где размер входа — это длина n массива. В связи с этим примером остановимся пока на операциях сравнения.

Количество сравнений ^{n (} n ~¹⁾, требуемое в худшем случае, характе­ризует рассматриваемый алгоритм среди всех алгоритмов сортировки как «имеющий квадратичную сложность». Для придания этим словам точного смысла должно быть, прежде всего, определено само понятие сложности.

Определение 1.1. Пусть на возможных входах x алгоритма A опре­делена неотрицательная числовая функция || x || (размер входа). Пусть также определены целочисленные неотрицательные функции C_A(x), C_A (x) временных и пространственных затрат алгоритма A. Тогда вре­менной и пространственной сложностями A называются функции числового аргумента

T_AЛn) = шах C^TЛx), SJn) = maxC^SAx) (1.2)

11 x 11 = n 1 x 1 = n

(областью изменения n как аргумента функций T_A{n) и S_A{n) явля­ется множество значений размера || • ||). Более полно каждая такая сложность именуется сложностью в худшем случае.

Вместо T_A{n),S_A{n) мы иногда будем писать просто T{n),S{n), ес­ли ясно, о каком алгоритме идет речь.

Два примечания к определению 1.1.

1) Значение C_A^T{x) есть в подавляющем большинстве случаев число каких-то операций, а C^S_A{x) —число хранимых величин какого-то ти­па, поэтому предположение о целочисленности значений этих функ­ций вполне естественно. Без этого предположения в (1.2) пришлось

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

12 Глава 1. Сложности алгоритмов как функции числовых аргументов

бы использовать sup вместо max, что сделало бы многие рассуждения о сложности более тяжеловесными.

2) Видимо, вместо «сложность в худшем случае» правильнее бы­ло бы сказать «сложность как затраты в худшем случае», но такова принятая здесь терминология. Мы пока (до § 5) не рассматриваем сложность в среднем, и поэтому, не опасаясь путаницы, будем назы­вать сложность в худшем случае просто сложностью.

Вернемся к алгоритмам MM, TD, I из примеров 1.1, 1.2, 1.3. Рас­смотрим вначале временные сложности T _мм(n), T _TD(n), T (n). Получа­ем T_мм(n) = n³ и T^n) = ^{n (} n -¹⁾. Для T _TD(n) у нас нет столь простой формулы. Заметим, например, что для значений n от 111 до 120 мы имеем

n: 111 112 113 114 115 116 117 118 119 120 T_TD(n): 2 19 14 12 16 1

Изменение этой функции при n -> оо можно охарактеризовать так: для любых n значение этой функции не превосходит La n J - 1, и най­дутся сколь угодно большие n, для которых ее значение равно L-s/ n J-L

В примерах 1.2 и 1.3 не возникает необходимости в хранении больших объемов величин сверх объема входа (сортировка просты­ми вставками не требует дополнительного массива). Дополнительная память, если и нужна, — это несколько дополнительных переменных (ячеек), используемых алгоритмом.

Поэтому можно считать, что S^n)S^n) ограничены константа­ми. В примере 1.1 нам требуется дополнительная матрица, в которой будет формироваться результат; имеем S_MM(n) = n².

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

for i = l to n do... od

тратится время на изменение параметра цикла, проверку условия продолжения цикла и т.д.

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

§ 1. Затраты алгоритма для данного входа

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

Отметим еще, что, вообще говоря, время выполнения операции зависит от размеров ее операндов, это относится и к арифметиче­ским операциям, и к операции сравнения (например, длинные чис­ла сравнивать труднее, чем короткие и т.д.). Аналогично дело об­стоит с пространственными затратами и соответственно с простран­ственной сложностью; здесь, прежде чем находить сложность, надо решить, что является «единицей хранения»: скажем, при умножении двух матриц мы можем получить матрицу с элементами, которые за­писываются более длинно, чем элементы исходных матриц. Однако довольно часто считается, что результат операции всегда умещается в одной ячейке.

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

Определение 1.2. Пусть функция С^Т_А(х) в определении 1.1 отра­жает затраты на выполнение лишь какого-то одного типа операций в предположении, что все эти операции требуют одинакового време­ни выполнения, не зависящего от вида и размера операндов, и это время равно 1. Тогда соответствующая функция Т_А(п) —это слож­ность по числу операций рассматриваемого типа. Привлечение в ка­честве Сд(х) функции, отражающей только количество хранимых до­полнительных величин того или иного фиксированного типа, приво­дит к пространственной сложности S_A(n) по числу величин рассмат­риваемого типа.

Такую сложность называют алгебраической сложностью по чис­лу операций или числу величин рассматриваемого типа, подчерки-

См., например, [25].

14 Глава 1. Сложности алгоритмов как функции числовых аргументов

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

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

Формулы (1.2) вновь заставляют вспомнить о важности понятия размера входа. В силу разных причин не всегда этот размер легко и естественно может быть введен так, что сложность алгоритма воз­растает при увеличении размера входа. Но, по крайней мере, функ­ция || • || должна обеспечивать определенность значений T_A{n), S_A{n) для всех достаточно больших n — иначе было бы невозможно гово­рить о поведении T_A{n), S_A{n) при n —> <х>.

Заведомо неудачный размер входа — это, скажем, число строк n данной матрицы, если речь идет об алгоритмах вычисления про­изведения всех элементов и если матрица не обязательно является квадратной: при выбранном таким образом размере входа мы имеем тождественное равенство T_A{n) = оо для сложности по числу умноже­ний любого такого алгоритма A, так как при фиксированном числе строк число столбцов и число элементов могут быть сколь угодно большими.

Другие возможные осложнения, вызванные неудачным выбором размера входа, будут обсуждаться в § 13.

Достаточно очевидно, что если алгоритм A состоит в последова­тельном (друг за другом) выполнении алгоритмов U и V, то мы, вооб­ще говоря, не можем утверждать, что T_A{n) = TU{n) + T_V{n), так как, например, размер входа алгоритма U может существенно отличаться, как в большую, так и в меньшую сторону, от размера его выхода.

Пусть A и B —некоторые алгоритмы. Как можно заметить, из вы­полнения для всех n неравенства T_A{n) < T_B{n) не следует, что C^T_А{x) < <CB (x) для всех возможных входов x (достаточно вспомнить сорти­ровку слияниями и пузырьковую сортировку; последняя выполняется быстрее первой, коль скоро массив задан уже в упорядоченном виде). Аналогично дело обстоит с пространственными сложностью и затра­тами.

§ 1. Затраты алгоритма для данного входа

В некоторых случаях алгоритму сопоставляют несколько слож­ностей. Итоговые временные затраты сортировки массива с помо­щью сравнений складываются из затрат на сравнение и на пере­мещение элементов. Без учета типа элементов массива нельзя ска­зать, какая из операций является более дорогой. Поэтому для ал­горитмов сортировки используются две сложности: с одной сторо­ны—по числу сравнений, а с другой —по числу перемещений эле­ментов, т.е. присваиваний (:=) или обменов (<->). Если же рассмат­ривается некоторый арифметический алгоритм, то, исследовав его мультипликативную сложность, можно дополнительно интересовать­ся, в качестве уточнения, аддитивной сложностью (числом сложений и вычитаний в худшем случае) и т. д. В приложении D мы тщатель­но исследуем мультипликативную и аддитивную сложности алгорит­мов вычисления значения полинома при заданном значении аргу­мента.

Пусть некоторому алгоритму А сопоставлены две, скажем, времен­ные сложности Т'_А{п) и Т'_А\п). Например, Т'_А{п) и Т'_А\п) могут быть сложностями по разным операциям. Если операции первого и вто­рого вида предполагаются имеющими одинаковую затратность, то это еще не дает оснований считать, что сложность Т_А{п), которую мы определим, рассматривая совместно операции обоих видов, бу­дет равна Т'_А(п) + Т'_А{п), потому что максимумы этих двух видов за­трат могут достигаться на разных входах одного и того же размера. Можно только утверждать, что

Т_А{п)^Г_А{п) + Г_А\п).

Пример 1.4. Чтобы проиллюстрировать указанное обстоятельство, мы вновь обратимся к сортировке простыми вставками, которая мо­жет рассматриваться в двух вариантах \_г и 1₂: для вставки элемента x_i+1 в уже упорядоченную часть х_г,х₂,...,x_t элементы этой упорядо­ченной части просматриваются либо в порядке x_h х_{-_ъ..., либо в по­рядке х_г,х₂,... В первом варианте максимум числа сравнений до­стигается тогда, когда входной массив имеет обратную к требуемой упорядоченность: х_г > х₂ >... > х_п^ и на этом же входе достигается максимум числа обменов; имеем \ (п) = Т^ (п) + Т{[(п) = п{п- 1), где Т{^п),Т{^п) суть сложности по числу сравнений и обменов.

Во втором варианте максимум числа сравнений достигается, когда массив уже упорядочен так, как требуется: х_г <х₂ <... <х_п, а макси­мум числа обменов—когда х_г > х₂ >... > х_п. Если i > 1, то при вставке элемента x_i+1 в уже упорядоченную часть х_г, х₂,..., х_{ потребуется тем меньше обменов, чем больше потребуется сравнений. Если элемент

16 Глава 1. Сложности алгоритмов как функции числовых аргументов

займет место с номером к, то это потребует i-k + 1 обменов. Число же сравнений равно к, если к s= i, и равно к - 1, если k = i + l. Сум­марное число сравнений и обменов равно i + 1, если к s= i, и равно i, если k = i + l. Поэтому максимум общего числа сравнений и обме­нов достигается, например, на входном массиве, имеющем обратную к требуемой упорядоченность: х_г > х₂ >... > х_п. Легко устанавливает-

?. (п + 2)(п-1)
ся, что 7]₂(п) =----------------------.

Рассматривая сложности 7] (п), 7] (п) первого и второго вариан­тов сортировки простыми вставками по общему числу сравнений и обменов, мы имеем

7\(n) = n (n -l), f_h = ⁽" ^{+ 2)}₂⁽" - ^1}, (1.3)

и, таким образом, Г] (п) / ^ (п)—»2 при возрастании п.

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

for i = 2 to п do

k:=i;

while k > 0 and x_k >x_k+1 do x_k <-> x_k+1; k:=k-l od od

(предполагается, что если k ^ 0, то булево выражение, имеющее вид конъюнкции

к > 0 and х_к > х_к+ъ

принимает значение 0, т. е. «ложь», даже если при этом, например, значение х_к не определено, и, следовательно, не определено значение второго члена конъюнкции).

Второй вариант будет иметь вид:

for i = 2 to n do

fc:=l;

while k<i and x_k<x_t do k:=k + l od;

f or j = i - 1 downto к do Xj^x_j+1 od od

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

§ 1. Затраты алгоритма для данного входа

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

Заметим попутно, что среди сортировок с квадратичной сложно­стью по числу сравнений чрезвычайно низкой сложностью по числу перемещений, а именно сложностью, равной п - 1, обладает сорти­ровка выбором.

В некоторых случаях к учитываемым операциям относят операции весьма разнородные, и время выполнения каждой из них считают равным 1 — пример 3.1, как и некоторые другие, даст соответству­ющую иллюстрацию. При нахождении каждой такой «смешанной» сложности затраты для каждого конкретного входа учитываются ра­зом все вместе.

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

¹ В литературе на английском языке —RAM (random-access machine).

² Раньше в литературе по вычислительной математике и программированию сло­
во «машина» употреблялось как обозначение некоторого реального вычислительного
устройства; устойчивым словосочетанием было, например, «электронная вычислитель­
ная машина» (ЭВМ). Сейчас в этом значении в основном употребляется слово «ком­
пьютер», а слово «машина» часто используется при обсуждении абстрактных вычисли­
тельных устройств: машин Тьюринга, равнодоступных адресных машин и т. д.

18 Глава 1. Сложности алгоритмов как функции числовых аргументов

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

Далее мы будем еще неоднократно обращаться к понятию модели вычислений; всюду до главы 5 без оговорок подразумевается модель РАМ.

Дата добавления: 2014-01-11