Билет 17. Вопрос 1.

Размер задачи. Конечная временная сложность алгоритма как функция размера задачи.

1. Понятие о критериях сравнения качества различных алгоритмов.

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

Например, при сортировке массивов данных можно перегруппировывать элементы массива внутри самого массива, но можно и создать вспомогательный массив той же размерности, куда заносить уже отсортированные элементы. В первом случае требуется значительно меньше памяти ЭВМ, чем во втором. То же касается и быстродействия компьютера. Каждая операция алгоритма, исполняемого на ЭВМ, имеет вполне конкретную длительность, т.е. время исполнения. Зная длительность основных операций в ЭВМ и подсчитав число основных операций алгоритма, можно оценить общее время исполнения данного алгоритма.

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

Разрешимость этой задачи в теоретическом смысле очевидна. Если мы имеем грузов, то возможных комбинаций этих грузов будет . Действительно, если обозначить через присутствие конкретного груза на машине, а через 0 – его отсутствие, то этой ситуации будет соответствовать двоичный набор , где . Но число двоичных наборов длины равно . Проверив все варианты, можно узнать, есть ли среди них комбинация , полностью загружающая машину. А сейчас оценим число операций, необходимых для решения. Возьмем . Тогда . Это значит, что нужно перебрать около вариантов. Пусть в нашем распоряжении есть компьютер, который выполняет один миллиард () операций в секунду и пусть на проверку одного варианта решения задачи уходит одна операция. А это значит, что понадобится не менее секунд для решения указанной задачи перебором вариантов. Если учесть, что 1час = 3600 сек, 1 сутки = 86400 сек, а один год 86400·365=31536000»315×10⁵сек, то лет.

Это значит, что для полного перебора вариантов решения задачи нужно 3,1×10¹³ лет. Т.о., алгоритм полного перебора с практической точки зрения полностью непригоден.

2. Размер задачи.

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

Но предварительно нужно ввести некоторую характеристику задачи, которая выражала бы меру количества входных данных. Такую характеристику называют размером задачи. Например, размером задачи на умножение матриц может быть наибольший порядок матриц-сомножителей, при работе с одномерным массивом размером является число элементов массива, при нахождении НОД двух чисел – разрядность меньшего числа, при вычислении значений многочлена – его степень и т.д.

Пусть имеется некоторый класс задач и пусть – размерность конкретной задачи. Пусть также мы располагаем алгоритмом , который решает задачи из заданного класса. Тогда можно ввести функцию в качестве верхней границы максимального числа операций алгоритма .

3 Сложность алгоритма.

Поскольку длительность основных операций известна, то можно рассматривать как временную сложность алгоритма . В качестве ищут такую неотрицательную функцию простого вида, что , где – некоторая константа. Тогда говорят, что алгоритм имеет сложность “порядка ”. Если использовать специальный символ (О-большое), то можно записать . Покажем на простом примере нахождение.

Пусть имеется полином .

Необходимо оценить сложность вычисления значения этого полинома. Выполним следующие преобразования.

при

Если теперь в качестве взять , то получим

, то есть .

Часто вместо временной сложности используют термин “вычислительная сложность”.

Итак, вычислительная сложность – это время, затраченное алгоритмом для нахождения решения, как функция размера задачи.

Поведения функции в пределе при называют асимптотической сложностью. Именно асимптотическая сложность алгоритма определяет в конечном итоге размер задач, которые можно решать данным алгоритмом.

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

С точки зрения алгоритмического решения все задачи можно разделить на три класса:

1. Задачи, которые имеют алгоритмы решения полиноминальной сложности. Именно такие алгоритмы называют эффективными.

Алгоритмы сортировки, поиска, нахождения НОД и т.п. относятся к классу эффективных алгоритмов.

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

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

3. Задачи, которые не имеют алгоритмического решения. Такие задачи называют алгоритмически неразрешимыми. К ним, в частности, относят нахождения корней алгебраических уравнений степени выше четвертой, задачу нахождения решения диофантова уравнения от двух и более переменных, классическую задачу трисекции угла и т.д.