С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 3

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

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

Рассмотрим вначале временные сложности TMM (n), TTD (n), TI (n). Получаn(n − 1). Для TTD (n) у нас нет столь простойем TMM (n) = n3 и TI (n) =2формулы. Заметим, например, что для значений n от  до  мыимеемn:TTD (n):Изменение этой функции при n → ∞ можно охарактеризоватьтак:pдля любых n значение этой функции не превосходит ⌊ n⌋ − 1, и найдутся сколь угодно большие n, для которых ее значение равноp⌊ n⌋ − 1.В примерах . и . не возникает необходимости в хранениибольших объемов величин сверх объема входа (сортировка простыми вставками не требует дополнительного массива). Дополнительнаяпамять, если и нужна, — это несколько дополнительных переменных(ячеек), используемых алгоритмом.Поэтому можно считать, что SI (n), STD (n) ограничены константами.

В примере . нам требуется дополнительная матрица, в которойбудет формироваться результат; имеем SMM (n) = n2 .Во всех этих примерах мы, как легко заметить, принимаем вовнимание лишь часть затрат и в соответствии с этим определяемсложность алгоритма. В примере . учитывались только умножениякак более дорогие (доминирующие по затратности) операции. В примере . мы рассматриваем либо сравнения, либо обмены. И во всехпримерах мы игнорировали затраты по выполнению управляющихоператоров, хотя, скажем, при выполнении простейшего операторациклаfor i = 1 to n do ... odтратится время на изменение параметра цикла, проверку условияпродолжения цикла и т.

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

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

Пусть функция C AT (x) в определении . отражает затраты на выполнение лишь какого-то одного типа операцийв предположении, что все эти операции требуют одинакового времени выполнения, не зависящего от вида и размера операндов, и этовремя равно 1. Тогда соответствующая функция TA (n) — это сложность по числу операций рассматриваемого типа. Привлечение в качестве C AS (x) функции, отражающей только количество хранимых дополнительных величин того или иного фиксированного типа, приводит к пространственной сложности S A (n) по числу величин рассматриваемого типа.Такую сложность называют алгебраической сложностью по числу операций или числу величин рассматриваемого типа, подчеркиСм., например, []. Глава . Сложности алгоритмов как функции числовых аргументоввая этим предположение о равнозатратности всех рассматриваемыхопераций и равнообъемности всех учитываемых величин.

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

В силу разных причин не всегда этот размер легкои естественно может быть введен так, что сложность алгоритма возрастает при увеличении размера входа. Но, по крайней мере, функция k · k должна обеспечивать определенность значений TA (n), S A (n)для всех достаточно больших n — иначе было бы невозможно говорить о поведении TA (n), S A (n) при n → ∞.Заведомо неудачный размер входа — это, скажем, число строк nданной матрицы, если речь идет об алгоритмах вычисления произведения всех элементов и если матрица не обязательно являетсяквадратной: при выбранном таким образом размере входа мы имеемтождественное равенство TA (n) = ∞ для сложности по числу умножений любого такого алгоритма A, так как при фиксированном числестрок число столбцов и число элементов могут быть сколь угоднобольшими.Другие возможные осложнения, вызванные неудачным выборомразмера входа, будут обсуждаться в § .Достаточно очевидно, что если алгоритм A состоит в последовательном (друг за другом) выполнении алгоритмов U и V , то мы, вообще говоря, не можем утверждать, что TA (n) = TU (n) + TV (n), так как,например, размер входа алгоритма U может существенно отличаться,как в большую, так и в меньшую сторону, от размера его выхода.Пусть A и B — некоторые алгоритмы.

Как можно заметить, из выполнения для всех n неравенства TA (n) < TB (n) не следует, что C AT (x) << C BT (x) для всех возможных входов x (достаточно вспомнить сортировку слияниями и пузырьковую сортировку; последняя выполняетсябыстрее первой, коль скоро массив задан уже в упорядоченном виде).Аналогично дело обстоит с пространственными сложностью и затратами.§ . Затраты алгоритма для данного входаВ некоторых случаях алгоритму сопоставляют несколько сложностей. Итоговые временные затраты сортировки массива с помощью сравнений складываются из затрат на сравнение и на перемещение элементов.

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

В приложении D мы тщательно исследуем мультипликативную и аддитивную сложности алгоритмов вычисления значения полинома при заданном значении аргумента.Пусть некоторому алгоритму A сопоставлены две, скажем, временные сложности TA′ (n) и TA′′ (n). Например, TA′ (n) и TA′′ (n) могут бытьсложностями по разным операциям. Если операции первого и второго вида предполагаются имеющими одинаковую затратность, тоэто еще не дает оснований считать, что сложность TeA (n), которуюмы определим, рассматривая совместно операции обоих видов, будет равна TA′ (n) + TA′′ (n), потому что максимумы этих двух видов затрат могут достигаться на разных входах одного и того же размера.Можно только утверждать, чтоTeA (n) ¶ T ′ (n) + T ′′ (n).AAПример ..

Чтобы проиллюстрировать указанное обстоятельство,мы вновь обратимся к сортировке простыми вставками, которая может рассматриваться в двух вариантах 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 > ...

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

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