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

13

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

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

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

Определение 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 (достаточно вспомнить сорти­ровку слияниями и пузырьковую сортировку; последняя выполняется быстрее первой, коль скоро массив задан уже в упорядоченном виде). Аналогично дело обстоит с пространственными сложностью и затра­тами.