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

11

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

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

11x11=n 1x1 = 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-¹⁾. Для 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 значение этой функции не превосходит LanJ - 1, и най­дутся сколь угодно большие n, для которых ее значение равно L-s/nJ-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

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

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